-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathtree.py
More file actions
executable file
·93 lines (78 loc) · 2.36 KB
/
Copy pathtree.py
File metadata and controls
executable file
·93 lines (78 loc) · 2.36 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
from stack.stack import Stack
from stack.node import Node
class BinaryTree(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def is_leaf(self):
return (not self.left) and (not self.right)
def insert_left(self, node):
if isinstance(node, BinaryTree):
t = node
else:
t = BinaryTree(node)
if self.left is not None:
t.left = self.left
self.left = t
def insert_right(self, node):
if isinstance(node, BinaryTree):
t = node
else:
t = BinaryTree(node)
if self.right is not None:
t.right = self.right
self.right = t
def __repr__(self):
return '{}'.format(self.value)
def height(self):
if self is None:
return -1
else:
if self.left is not None:
left_height = self.left.height()
else:
left_height = 0
if self.right is not None:
right_height = self.right.height()
else:
right_height = 0
return 1 + max(left_height, right_height)
def traverse(self):
current_level = [self]
while current_level:
print(' '.join(str(node) for node in current_level))
next_level = list()
for n in current_level:
if n.left:
next_level.append(n.left)
if n.right:
next_level.append(n.right)
current_level = next_level
def dfs_traverse(tree):
level = 1
s = Stack()
s.push(Node([tree, level]))
while not s.is_empty():
node = s.pop()
key = node.data[0]
level = node.data[1]
if level == 1:
print str(key.value)
else:
print (level - 2) * "\t" + u'\u2514\u2500\u2500' + " " + str(key.value)
if key.left is not None:
s.push(Node([key.left, level + 1]))
if key.right is not None:
s.push(Node([key.right, level + 1]))
if __name__ == "__main__":
t = BinaryTree(7)
t.insert_left(3)
t.insert_right(9)
t.insert_right(10)
t.insert_right(14)
t.insert_left(5)
t.left.insert_right(4)
t.right.insert_left(22)
dfs_traverse(t)
#print "height: " + str(t.height())