【DataStructure In Python】Python模拟二叉树

浏览数：25 / 时间：2015年06月08日

使用Python模拟二叉树的基本操作，感觉写起来很别扭。最近做编译的优化，觉得拓扑排序这种东西比较强多。近期刷ACM，发现STL不会用实在太伤了。决定花点儿时间学习一下STL。Boost其实也很强大。关于Python最近没什么时间搞了，忙着复试了。不过，挺喜欢这语言的。复试完继续大战PythonChallenge。

  1 #! /usr/bin/env python
  2 # DataStrucure Tree
  3 
  4 import sys
  5 
  6 class BTNode:
  7     
  8     def __init__(self, data, lchild=None, rchild=None):
  9         self.data = data
 10         self.lchild = lchild
 11         self.rchild = rchild
 12 
 13     def __str__(self):
 14         print "root: %s  lchild: %s  rchild: %s" % (data, lchild.data, rchild.data)
 15     
 16 
 17 class BTree:
 18     
 19     def __init__(self, data=None, ldata=None, rdata=None):
 20         self.root = BTNode(data)
 21         self.root.lchild = BTNode(ldata)
 22         self.root.rchild = BTNode(rdata)
 23     
 24     def isEmpty(self):
 25         if self.root.data is None:
 26             return 1
 27         else:
 28             return 0
 29         
 30 
 31     def findNode(self, data):
 32         lst = []
 33         if self.isEmpty():
 34             print "The tree is empty."
 35             return None
 36         lst.append(self.root)
 37         while len(lst):
 38             BTemp = lst.pop(0)
 39             if BTemp.data == data:
 40                 return BTemp
 41             if BTemp.lchild is not None:
 42                 lst.append(BTemp.lchild)
 43             if BTemp.rchild is not None:
 44                 lst.append(BTemp.rchild)
 45         return None
 46     
 47     def addchilds(self, data, ldata=None, rdata=None):
 48         BTemp = self.findNode(data)
 49         if BTemp is None:
 50             print "Can‘t find Node: %s"    % data
 51             return 0
 52         else:
 53             BTemp.lchild = None if ldata is None else BTNode(ldata)
 54             BTemp.rchild = None if rdata is None else BTNode(rdata)
 55             return 1
 56 
 57     def levelorder(self):
 58         if self.isEmpty():
 59             print "Root is not initialized."
 60             return
 61         lst = []
 62         lst.append(self.root)
 63         while len(lst):
 64             BTemp = lst.pop(0)
 65             print "-> %s" % BTemp.data,
 66             if BTemp.lchild is not None:
 67                 lst.append(BTemp.lchild)
 68             if BTemp.rchild is not None:
 69                 lst.append(BTemp.rchild)
 70 
 71     def preorder(self, Node):
 72         if Node is not None:
 73             print "-> %s" % Node.data,
 74             self.preorder(Node.lchild)
 75             self.preorder(Node.rchild)
 76 
 77     def inorder(self, Node):
 78         if Node is not None:
 79             self.inorder(Node.lchild)
 80             print "-> %s" % Node.data,
 81             self.inorder(Node.rchild)
 82 
 83     def postorder(self, Node):
 84         if Node is not None:
 85             self.postorder(Node.lchild)
 86             self.postorder(Node.rchild)
 87             print "-> %s" % Node.data,
 88     
 89     def __str__(self):
 90         if self.isEmpty():
 91             print "Root is not initialized."
 92             return None        
 93         tmp = ""
 94         lst = []
 95         lst.append(self.root)
 96         while len(lst):
 97             BTemp = lst.pop(0)
 98             tmp += ("-> %s " % BTemp.data)
 99             if BTemp.lchild is not None:
100                 lst.append(BTemp.lchild)
101             if BTemp.rchild is not None:
102                 lst.append(BTemp.rchild)
103         return tmp
104 
105 if __name__ == "__main__":
106     tree = BTree(‘A‘)
107     tree.addchilds(‘A‘,‘B‘,‘C‘)
108     tree.addchilds(‘B‘,‘D‘,‘E‘)
109     tree.addchilds(‘C‘,‘F‘, None)
110     print "\n","-"*5,"    Find   ","-"*5
111     tmp = tree.findNode(‘B‘)
112     if tmp is not None:
113         print "Found ‘B‘, lchild is %s, rchild is %s." % (tmp.lchild.data, tmp.rchild.data)
114     else:
115         print "Not found ‘B‘."
116     print "\n","-"*5," Preorder  ","-"*5
117     tree.preorder(tree.root)
118     print "\n\n","-"*5,"  Inorder  ","-"*5
119     tree.inorder(tree.root)
120     print "\n\n","-"*5," Postorder ","-"*5
121     tree.postorder(tree.root)
122     print "\n\n","-"*5," Lvlorder  ","-"*5
123     tree.levelorder()
124     print "\n\n"