forked from ssjssh/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary_tree.py
More file actions
116 lines (93 loc) · 3.53 KB
/
Copy pathbinary_tree.py
File metadata and controls
116 lines (93 loc) · 3.53 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
# /usr/bin/env python
# -*- coding:utf-8 -*-
class Stack(object):
"""
实现上还是有些问题的，因为没有考虑栈空间不够的时候扩展的问题
"""
def __init__(self, cap):
super(Stack, self).__init__()
self.__cap = cap # 栈大小
self.__length = 0 # 栈长度
if self.__cap < 0:
raise ValueError("length of Stack can not be negtive")
self.__values = [0 for x in xrange(0, self.__cap)]
def empty(self):
return self.__length is 0
def push(self, x):
if self.__length >= self.__cap:
raise IndexError("stack is full, can not push any object")
self.__values[self.__length] = x
self.__length += 1
def pop(self):
if self.__length <= 0:
return None
self.__length -= 1
return self.__values[self.__length]
def __str__(self):
return "".join(["Stack, Value: ", str(self.__values), " cap: ", str(self.__cap),
" length:", str(self.__length)])
class Btree(object):
"""
实现一个通用的二叉树，这个二叉树并不包含任何别的性质
"""
class Node(object):
"""docstring for Node"""
def __init__(self, key, left, right):
self.key = key
self.left = left
self.right = right
def __str__(self):
return "".join(["key: ", str(self.key)])
def __init__(self, nodes, root_index=0):
"""
node是一个元祖列表，默认第一个是根节点，例如[(key=12,left=7,right=3),(key=15,left=8,right=None)]
"""
super(Btree, self).__init__()
self.__root, self.__nodes = self.build_tree(nodes, root_index)
self.__size = len(nodes)
def build_tree(self, nodes, root_index=0):
tree_nodes = [self.Node(ele[0], ele[1], ele[2]) for ele in nodes]
for node in tree_nodes:
node.left = tree_nodes[node.left] if node.left is not None else None
node.right = tree_nodes[node.right] if node.right is not None else None
return (tree_nodes[root_index], tree_nodes)
def depth_walk(self, f):
"""
使用栈实现深度遍历，每次都是把右节点放进栈里，这样的保证每次都是优先访问左节点
"""
result = []
stack = Stack(self.__size)
stack.push(self.__root)
while not stack.empty():
cur_node = stack.pop()
result.append(f(cur_node.key))
if cur_node.right is not None:
stack.push(cur_node.right)
if cur_node.left is not None:
stack.push(cur_node.left)
return result
def breadth_walk(self, f):
"""
使用堆实现广度遍历
"""
result = []
q = queue.Queue(maxsize=-1)
q.put(self.__root)
while not q.empty():
cur_node = q.get()
result.append(f(cur_node.key))
# 注意：这儿的顺序比较讲究，不能调换
if cur_node.left is not None:
q.put(cur_node.left)
if cur_node.right is not None:
q.put(cur_node.right)
return result
def __str__(self):
return "\t".join(self.depth_walk(lambda key: str(key)))
def main():
nodes = [(12, 6, 2), (15, 7, None), (4, 9, None), (10, 4, 8), (2, None, None), (18, 0, 3), (7, None, None),
(14, 5, 1), (21, None, None), (5, None, None)]
btree = Btree(nodes, 5)
print btree
if __name__ == '__main__':
main()