|
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,data
class
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的不爽。。。
。。。再了一下。想了一下午的问题。为什么说起来就是这么简单呢。。还是说我本来就很水呢。。哎。。。。。。。。。。。。。。。。。。。。