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
| """
二叉树
Copyright ©conghaoyuan@gmail.comm
"""
class Node:
def __init__(self, data) -> None:
self.data = data
self.left = None
self.right = None
class BinaryTree:
def __init__(self) -> None:
self.root = None
def is_empty(self):
return self.root is None
def add(self, data):
node = Node(data)
if self.is_empty():
self.root = node
return
list_node = [self.root]
while list_node:
cur = list_node.pop(0)
if cur.left is None:
cur.left = node
return
else:
list_node.append(cur.left)
if cur.right is None:
cur.right = node
return
else:
list_node.append(cur.right)
def breadth_search(self):
lists = []
if self.is_empty():
return lists
list_node = [self.root]
while list_node:
cur = list_node.pop(0)
lists.append(cur.data)
if cur.left is not None:
list_node.append(cur.left)
if cur.right is not None:
list_node.append(cur.right)
return lists
def depth_search_pre(self, node):
lists = []
if node is None:
return lists
lists.append(node.data)
lists += self.depth_search_pre(node.left)
lists += self.depth_search_pre(node.right)
return lists
def depth_search_mid(self, node):
lists = []
if node is None:
return lists
lists = self.depth_search_mid(node.left)
lists.append(node.data)
lists += self.depth_search_mid(node.right)
return lists
def depth_search_last(self, node):
lists = []
if node is None:
return lists
lists = self.depth_search_last(node.left)
lists += self.depth_search_last(node.right)
lists.append(node.data)
return lists
if __name__ == '__main__':
btree = BinaryTree()
btree.add(5)
btree.add(3)
btree.add(7)
btree.add(2)
btree.add(4)
btree.add(6)
btree.add(8)
print(btree.breadth_search())
print(btree.depth_search_pre(btree.root))
print(btree.depth_search_mid(btree.root))
print(btree.depth_search_last(btree.root))
|
