可视化完全二叉树
obi
posted @ 2010年8月09日 06:12
in 未分类
, 3053 阅读
完全二叉树的特性:从根结点开始每一层都从左到右填充” 使得它可以用一维数组直接存储一棵树本身。这个数组虽然逻辑上已经是树型的了,但表现形式却还是一维的,看起来很费劲。因此我写了个脚本,把一个数组转换成png图像,就像下面这样:
array | {1, 2, 3, 4, 5} |
pic | ![]() |
直接将一个树显示为png文件是很麻烦的,因为不仅得需要知道使用生成png的相关api(svg就不用了),还得想办法画好各结点的间距、距离、连接线,这些都不是轻而易举能搞定的。不过有前人栽树,后人就好乘凉了,Graphviz 就是要乘凉的那棵树。
Graphviz 提供了一系列的工具,dot 就是其中之一。dot 的功能就能是:用专门的描述语言显示图形,比如上面的 {1,2,3,4,5} 树的 dot 源代码就是:
graph { 1 -- 2 1 -- 3 2 -- 4 2 -- 5 }
就这么简单。剩下的工作就更简单了,只需要把数组显示成上面的源代码就行了。
转换代码如下:
;; emacs lisp ;;;;;;;;;;;;;; (defun complete-binary-tree-to-dot-script (array) "convert complete binary tree to dot script language" (when (and (sequencep array) (> (length array) 1)) (let ((result "graph\n{\n") (i 0) (N (length array))) (while (< i N) (setq result (concat result (proc-left array i))) (setq result (concat result (proc-right array i))) (setq i (+ 1 i))) (concat result "}\n") ))) (defun proc-left (array p) (when (< (+ 1 (* 2 p)) (length array)) (concat (number-to-string (elt array p)) " -- " (number-to-string (elt array (+ 1 (* 2 p)))) "\n"))) (defun proc-right (array p) (when (< (+ 2 (* 2 p)) (length array)) (concat (number-to-string (elt array p)) " -- " (number-to-string (elt array (+ 2 (* 2 p)))) "\n")))
求一个结点的左、右结点使用下面的公式就能得到:
要转换某个数组时,就使用:(complete-binary-tree-to-dot-script [1 2 3 4 5]) 来进行转换。将得到的结果保存到一个文件,然后再用 dot 编译成 png 就搞定了!
dot -Tpng tree.dot > tree.png
2022年8月21日 13:42
Rajasthan Board Model Paper 2023 Pdf Download for School Education Ajmer & Jaipur Board Sample Model Question Paper for Class 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 & 12 Standard Theory, Objective (MCQ) and Bit Questions for Hindi Medium, English Medium, Urdu Medium and others. RBSE Model Paper New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.