Breadth First Search的实现#
1class Node:
2 def __init__(self, value) -> None:
3 self.value = value
4 self.left = None
5 self.right = None
6
7 def __str__(self):
8 return str(self.value)
9
10
11class BinarySearchTree:
12 def __init__(self) -> None:
13 self.root = None
14
15 def insert(self, value):
16
17 new_node = Node(value)
18 if self.root is None:
19 self.root = new_node
20 return True
21
22 tmp_root = self.root
23
24 while True:
25
26 if new_node.value == tmp_root.value:
27 return False
28
29 elif new_node.value < tmp_root.value:
30
31 if tmp_root.left is None:
32 tmp_root.left = new_node
33 return True
34 tmp_root = tmp_root.left
35 else:
36 if tmp_root.right is None:
37 tmp_root.right = new_node
38 return True
39 else:
40 tmp_root = tmp_root.right
41
42 def bfs(self):
43 node_queue = []
44 results = []
45 current_node = self.root
46 node_queue.append(current_node)
47
48 while len(node_queue) > 0:
49 current_node = node_queue.pop(0)
50 results.append(current_node.value)
51 if current_node.left is not None:
52 node_queue.append(current_node.left)
53 if current_node.right is not None:
54 node_queue.append(current_node.right)
55 return results
56
57
58if __name__ == "__main__":
59
60 bst = BinarySearchTree()
61
62 for i in [8, 3, 10, 1, 6, 9, 14]:
63 bst.insert(i)
64
65 print(bst.bfs())