-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathbinary_search_tree.py
More file actions
145 lines (109 loc) · 2.62 KB
/
Copy pathbinary_search_tree.py
File metadata and controls
145 lines (109 loc) · 2.62 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
141
142
143
144
145
#!/usr/bin/env python2.7
from stack.stack import Stack
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
self.p = None
def inorder_tree_walk(n):
s = Stack()
current = n
done = 0
while not done:
if current is not None:
s.push(current)
current = current.left
else:
if not s.is_empty():
current = s.pop()
print current.val,
current = current.right
else:
done = 1
def search_tree(n, k):
if k == n.val or n is None:
return n
elif k > n.val:
search_tree(n.right, k)
else:
search_tree(n.left, k)
def iterative_search_tree(n, k):
while n is not None and k != n.val:
if k < n.val:
n = n.left
else:
n = n.right
return n
def find_minimum(n):
while n.left is not None:
n = n.left
return n
def find_maximum(n):
while n.right is not None:
n = n.right
return n
def find_successor(r, n):
if n.right is not None:
return find_minimum(n.right)
while r is not None:
if n.val < r.val:
succ = r
r = r.left
elif n.val > r.val:
r = r.right
else:
break
return succ
def find_predecessor(root, node):
pass
def insert(root, key):
node = TreeNode(key)
if root is None:
return node
else:
x = root
while x is not None:
y = x
if node.val < x.val:
x = x.left
else:
x = x.right
if node.val < y.val:
y.left = node
else:
y.right = node
def transplant(root, u, v):
if u.p is None:
root = v
elif u == u.p.left:
u.p.left = v
else:
u.p.right = v
if v is not None:
v.p = u.p
def delete_node(root, key):
"""
Args:
root: the root node of the tree
key: the value of the node to be deleted.
Returns: None
"""
# Case 1: Node does not have any children, remove simply.
# Case 2: Node has only one child
# Case 3: Node has two children
pass
if __name__ == "__main__":
# root = TreeNode(6)
# root.left = TreeNode(5)
# root.right = TreeNode(7)
# root.left.left = TreeNode(2)
# root.left.right = TreeNode(5)
# root.right.right = TreeNode(8)
root = TreeNode(6)
insert(root, 5)
insert(root, 7)
insert(root, 2)
insert(root, 5)
insert(root, 8)
inorder_tree_walk(root)