|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106 |
class
TreeNode: parent,leftChild,rightChild,data=None,None,None,0 def
__init__(self,data): self.parent,self.leftChild,self.rightChild,self.data=None,None,None,dataclass
BinaryTree: root=None def
__init__(self,data): self.root=TreeNode(data) def
insertValue(self,beginNode,data): self.add(beginNode,TreeNode(data)) def
add(self,beginNode,inNode): if
beginNode==None: raise
NameError,"beginNode is None" else: if
beginNode.data<inNode.data: if
beginNode.rightChild==None: inNode.parent=beginNode beginNode.rightChild=inNode else: self.add(beginNode.rightChild,inNode) else: if
beginNode.leftChild==None: inNode.parent=beginNode beginNode.leftChild=inNode else: self.add(beginNode.leftChild,inNode) def
maxValue(self,beginNode): if
beginNode.rightChild==None: return
beginNode.data else: return
self.maxValue(self,beginNode.rightChild) def
maxDepth(self,beginNode): if
beginNode==None: return
0 else: return
max(self.maxDepth(beginNode.rightChild),self.maxDepth(beginNode.leftChild))+1 def
judgeDirction(self,beginNode,searchedNode): if
searchedNode==beginNode: Direction="OnlySelf" elif
searchedNode==beginNode.leftChild: Direction="Left" elif
searchedNode==beginNode.rightChild: Direction="Right" else: Direction="Up" return
Direction def
nextNode(self,beginNode): returnNode,Direction=self.nextNodeByDirection(beginNode,"OnlySelf") if
Direction=="AllOver": return
None """ else: returnNode,Direction=self.nextNodeByDirection(searchedNode,"Left") Direction=self.judgeDirction(beginNode,returnNode) """ return
returnNode def
nextNodeByDirection(self,beginNode,searchedDirection="OnlySelf"): """ beginNode：求beginNode的下一个节点 searchedDirection:表示已经搜索过的方向：OnlySelf表示什么也没有搜索，Left,表示已经搜索了左孩子节点，Right表示已经 搜索右子树 思路： 1.如果什么都没有搜索，则返回左孩子，如果左孩子为空，进行步骤2 2.搜索右孩子点，返回右孩子，如果右孩子为空，进入步骤3 3.获取节点A的父节点parent,如果节点A是父节点parent的左孩子的话，设置已经搜索了"Left",设置parent节点为当前节点 此时就可以进入步骤2，如果节点A是父节点parent的右孩子的话，设置已搜索方法为"Right",设置parent节点为当前节点， 再进入节点3 什么时候可以退出呢？当返回方向为"AllOver"且返回的节点为None时，就可以退出了 """ if
searchedDirection=="OnlySelf": if
not beginNode.leftChild: return
self.nextNodeByDirection(beginNode,"Left") else: return
beginNode.leftChild,searchedDirection elif
searchedDirection=="Left": rightChildNode=beginNode.rightChild if
not rightChildNode: return
self.nextNodeByDirection(beginNode,"Right") else: return
rightChildNode,searchedDirection else: parentNode=beginNode.parent if
not parentNode: return
None,searchedDirection else: if
parentNode.leftChild==beginNode: return
self.nextNodeByDirection(parentNode,"Left") else: return
self.nextNodeByDirection(parentNode,"Right") def
printTree(self,beginNode): searchNode=None print
beginNode.data, searchNode=beginNode while
True: searchNode=self.nextNode(searchNode) if
not searchNode: break print
searchNode.data,if
__name__==‘__main__‘: ds=[5,6,4,10,8,7,2] BTree=BinaryTree(ds[0]) for
i in
ds[1:]: BTree.insertValue(BTree.root,i) BTree.printTree(BTree.root) |
今天先写到这里吧。。晕死了，想了一下午了。。。改了好多次。。好想念VS。。。。其余工具调试起来真TMD的不爽。。。
。。。再了一下。想了一下午的问题。为什么说起来就是这么简单呢。。还是说我本来就很水呢。。哎。。。。。。。。。。。。。。。。。。。。
原文：http://www.cnblogs.com/cangling20041616/p/3620297.html