状态模式是怎样干掉 case&if 的
解决android插件Debug certificate过期问题

可视化完全二叉树

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")))

 

求一个结点的左、右结点使用下面的公式就能得到:

leftnode=node*2+1

rightnode=node*2+2

 

要转换某个数组时,就使用:(complete-binary-tree-to-dot-script [1 2 3 4 5]) 来进行转换。将得到的结果保存到一个文件,然后再用 dot 编译成 png 就搞定了!

 

dot  -Tpng tree.dot > tree.png

 

 

RBSE Model Paper 说:
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.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter