数据结构之二叉树

 1 # 树节点
 2 class structNode(object):
 3 
 4 
 5     def __init__(self,ele,lnode=None,rnode=None):
 6         self.data = ele
 7         self.lnode = lnode
 8         self.rnode = rnode
 9 
10 
11 class structTree(object):
12 
13     def __init__(self):
14         self.root = None
15         self.travesalNode = []
16 
17     def createTree(self, lis):
18         # 如何根据根节点保存左右节点
19         for i in lis:
20             res = i.split('.')
21             # 先实例化当前节点 然后判断是否存在左右节点
22             cur_node = structNode(res[0].strip(), res[1].strip(), res[2].strip())
23             if not self.root:
24                 self.root = cur_node
25                 self.travesalNode.append(self.root)
26             else:
27                 # 拿到父节点,当前父节点列表不为空
28                 node = self.travesalNode[0]
29                 while self.travesalNode:
30                     # 如果父节点的左节点存在并且这个值正好等于当前节点的值 说明该节点是该父节点的左节点
31                     if node.lnode and node.lnode == res[0]:
32                         node.lnode = cur_node
33                         self.travesalNode.append(cur_node)
34                         break
35                     #     当遍历完右子树的时候 就要删除当前父节点了
36                     if node.rnode and node.rnode == res[0]:
37                         node.rnode = cur_node
38                         self.travesalNode.append(cur_node)
39                         del self.travesalNode[0]
40                         break

41     # 前序遍历
42     def Ftravesal(self,root_node):
43 
44         if root_node:
45             print("根节点:",root_node.data)
46         if root_node.lnode:
47             self.Ftravesal(root_node.lnode)
48         if root_node.rnode:
49             self.Ftravesal(root_node.rnode)

50     # 中序遍历
51     def Mtraversal(self,root_node):
52         if root_node.lnode:
53             self.Mtraversal(root_node.lnode)
54         print("根节点:",root_node.data)
55         if root_node.rnode:
56             self.Mtraversal(root_node.rnode)

57     # 后序遍历
58     def Ltraversal(self,root_node):
59 
60         if root_node.lnode:
61             self.Ltraversal(root_node.lnode)
62         if root_node.rnode:
63             self.Ltraversal(root_node.rnode)
64         print(root_node.data)

65     # 层序遍历
66     def Dtraversal(self,root_node):
67 
68         tmp = [root_node]
69         while tmp:
70             node = tmp[0]
71             print(node.data)
72             if node.lnode:
73                 tmp.append(node.lnode)
74             if node.rnode:
75                 tmp.append(node.rnode)
76             del tmp[0]
77 
78 
79 if __name__ == '__main__':
80 
81     lis = ["1.2.3",
82            "2. .4", "3.5.6",
83            "4.7.8", "5.9.10", "6.11. ",
84            "7. . ", "8. .  ", "9. . ","10. . ","11. . "]
85 
86     tr = structTree()
87     tr.createTree(lis)
88     # tr.Ftravesal(tr.root)
89     tr.Dtraversal(tr.root)