|
用法: python treeWriter.py #輸出結(jié)果到tree.png python treeWriter.py <output_file_name> 注意需要安裝 graphviz 和 pygraphviz，安裝方法見前一篇隨筆。 當(dāng)前的實(shí)現(xiàn)需要用戶交互輸入二叉樹，默認(rèn)輸入-1作為子樹空。 如對應(yīng)上面的圖，可輸入 1 2 7 –1 –1 8 –1 –1 –1 3 4 1 –1 -1 2 –1 9 –1 –1 4 5 3 –1 –1 –1 6 –1 –1 可以有更好的輸入方法，待改進(jìn)。 以前寫過利用pyqt顯示二叉樹的隨筆，當(dāng)時(shí)用的已經(jīng)寫好的c++實(shí)現(xiàn)的二叉樹及相應(yīng)函數(shù)，用swig構(gòu)造一個(gè)python可調(diào)用的二叉樹模塊，這里也可以用同樣的方法，只要將treeWriter中相應(yīng) 如 root.left, root.elem改成相應(yīng)的c++函數(shù)轉(zhuǎn)換好的python可調(diào)用的二叉樹模塊中的接口函數(shù)名即可。 而且程序有很好的可擴(kuò)張性，借助graphviz方便而強(qiáng)大的布局功能，可選的頂點(diǎn)，邊參數(shù)，用戶可以方便的通過繼承定義自己的tree writer來繪制不同的二叉樹，如下圖繪制了一顆建立好的huffman tree. >>> l
來一個(gè)復(fù)雜一點(diǎn)，我利用繪制的二叉樹，來判斷壓縮過程中生成的huffmantree，以及解壓縮過程中寫文件后(序列化)之后從文件讀出重構(gòu)的huffmantree是否一致。由于’\n’沒有處理好：）暫時(shí)不顯示key value了，只對比下樹形。
1.binaryTree.py 簡單定義了二叉鏈表節(jié)點(diǎn)，和二叉樹類，給出了通過用戶交互輸入生成二叉樹的方法，及中序遍歷方法。  2 #support reference the same as c++ not pointer to pointer in python I think 3 4 #Author goldenlock_pku 5 ''' 6 Ilustrate the create binary tree with user input 7 inorder travel 8 ''' 9 class Node(): 10 ''' 11 node will be used in BinaryTree 12 ''' 13 def __init__(self,elem, left = None, right = None): 14 self.elem = elem 15 self.left = left 16 self.right = right 17 def __str__(self): 18 return str(self.elem) 19 20 class BinaryTree(): 21 def __init__(self,root = None): 22 self.root = root 23 24 def createTree(self, endMark = -1): 25 '''create a binary tree with user input''' 26 def createTreeHelp(endMark = -1): 27 elem = raw_input(); 28 if (elem == str(endMark)): 29 return None 30 root = Node(elem) 31 root.left = createTreeHelp(endMark) 32 root.right = createTreeHelp(endMark) 33 return root 34 print('Please input the binary tree data wit ' + str(endMark)\ 35 +' as endmark') 36 elem = raw_input() 37 self.root = Node(elem) 38 self.root.left = createTreeHelp(endMark) 39 self.root.right = createTreeHelp(endMark) 40 41 def inorderTravel(self): 42 def inorderTravelHelp(root): 43 if not root: 44 return 45 inorderTravelHelp(root.left) 46 print(root) 47 inorderTravelHelp(root.right) 48 inorderTravelHelp(self.root)
2.treeWriter.py 定義了利用pygraphviz生成dot 文件并進(jìn)一步生成二叉樹圖案輸出到文件。 繪制過程采用遞歸，深度優(yōu)先遍歷，利用了不可見節(jié)點(diǎn)和邊從而能夠始終確保能夠分清是左子樹還是又子樹，如果不采用 加入不可見節(jié)點(diǎn)，邊的方法則無法分清，如果繪制樹的話可以采用簡單的不加不可見節(jié)點(diǎn)的方法。 2 from binaryTree import * 3 import pygraphviz as pgv 4 ''' 5 treeWriter with func wite can write a binary tree to tree.png or user spcified 6 file 7 ''' 8 class treeWriter(): 9 def __init__(self, tree): 10 self.num = 1 #mark each visible node as its key 11 self.num2 = -1 #makk each invisible node as its key 12 self.tree = tree 13 14 def write(self, outfile = 'tree.png'): 15 def writeHelp(root, A): 16 if not root: 17 return 18 19 p = str(self.num) 20 self.num += 1 21 A.add_node(p, label = str(root.elem)) 22 q = None 23 r = None 24 25 if root.left: 26 q = writeHelp(root.left, A) 27 A.add_node(q, label = str(root.left.elem)) 28 A.add_edge(p,q) 29 if root.right: 30 r = writeHelp(root.right, A) 31 A.add_node(r, label = str(root.right.elem)) 32 A.add_edge(p,r) 33 34 if q or r: 35 if not q: 36 q = str(self.num2) 37 self.num2 -= 1 38 A.add_node(q, style = 'invis') 39 A.add_edge(p, q, style = 'invis') 40 if not r: 41 r = str(self.num2) 42 self.num2 -= 1 43 A.add_node(r, style = 'invis') 44 A.add_edge(p, r, style = 'invis') 45 l = str(self.num2) 46 self.num2 -= 1 47 A.add_node(l, style = 'invis') 48 A.add_edge(p, l, style = 'invis') 49 B = A.add_subgraph([q, l, r], rank = 'same') 50 B.add_edge(q, l, style = 'invis') 51 B.add_edge(l, r, style = 'invis') 52 53 return p #return key root node 54 55 self.A = pgv.AGraph(directed=True,strict=True) 56 writeHelp(self.tree.root, self.A) 57 self.A.graph_attr['epsilon']='0.001' 58 print self.A.string() # print dot file to standard output 59 self.A.layout('dot') # layout with dot 60 self.A.draw(outfile) # write to file 61 62 63 if __name__ == '__main__': 64 tree = BinaryTree() 65 tree.createTree(-1) 66 tree.inorderTravel() 67 writer = treeWriter(tree) 68 if len(sys.argv) > 1: 69 outfile = sys.argv[1] 70 writer.write(outfile) #write result to outfile 71 else: 72 writer.write() #write result to tree.png 73 74 |
|
|
