forked from taizilongxu/interview_python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBST
More file actions
140 lines (127 loc) · 3.4 KB
/
BST
File metadata and controls
140 lines (127 loc) · 3.4 KB
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
class BinaryTree():
def __init__(self, val, parent = None, left = None, right = None):
self.parent = parent
self.value = val
self.left = left
self.right = right
def Recur_Search(root, val):
if root.value == None or root.value == val:
return root
if val < root.value:
return recur_search(root.left, val)
else:
return recur_search(root.right, val)
def Iter_Search(root, val):
while root.value != None and val != root.value:
if val < root.value:
root = root.left
else:
root = root.right
return root
def MinofTree(root):
while root.left != None:
root = root.left
return root
def Recur_MinofTree(root):
if root == None or root.left == None:
return root
else:
return Recur_MinofTree(root.left)
def MaxofTree(root):
while root.right != None:
root = root.right
return root
def Recur_MaxofTree(root):
if root == None or root.right == None:
return root
else:
return Recur_MaxofTree(root.right)
def InorderTreeWalk(root):
if root != None:
InorderTreeWalk(root.left)
print(root.value, end=' ' )
InorderTreeWalk(root.right)
# if the right subtree of node is nonempty, then the Successor
# of x is the leftmost node in the right subtree, if the right
# subtree of node is empty and x has a Successor y, then y is the
# lowest ancestor of x whose left child is also an ancestor of x
def Successor(root):
if root.right != None:
return MinofTree(root.right)
suc = root.parent
while suc != None and root == suc.right:
root = suc
suc = suc.parent
return suc
def Predecessor(root):
if root.left != None:
return MaxofTree(root.right)
pre = root.parent
while pre != None and root == pre.left:
root = pre
pre = pre.left
return pre
#def Recur_Insert(root, val):
# if root == None:
# key = BinaryTree(val)
# root = key
# elif val < root.value:
# Recur_Insert(root.left, val)
# print('left')
# print(root.left)
# else:
# Recur_Insert(root.right, val)
# print('right')
def TreeInsert(root, val):
key = BinaryTree(val)
p = None
while root != None:
p = root
if key.value < root.value:
root = root.left
else:
root = root.right
key.parent = p
if p == None:
root = key
elif key.value < p.value:
p.left = key
else:
p.right = key
def TreeDelete(root, val):
key = Iter_Search(root, val)
if key == None:
return None
d = None
if key.left == None or key.right == None:
d = key
else:
d = Successor(key)
if d.left != None:
cd = d.left
else:
cd = d.right
if cd != None:
cd.parent = d.parent
if d.parent == None:
root = cd
elif d == d.parent.left:
d.parent.left = x
else:
d.parent.right = x
if d != key:
key.value = d.value
return d
L = [3, 5, 6, 7, 10, 12, 13, 16, 18, 20, 23]
root = BinaryTree(15)
for i in L:
# Recur_Insert(root, i)
TreeInsert(root, i)
InorderTreeWalk(root)
print(root.left.value)
print(Successor(root.left).value)
print(Predecessor(root.left.right).value)
print(MinofTree(root).value)
print(MaxofTree(root).value)
print(Recur_MinofTree(root).value)
print(Recur_MaxofTree(root).value)