Depth 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 dfs_pre_order(self):
43 results = []
44
45 def traversal(current_node):
46 results.append(current_node.value)
47 if current_node.left is not None:
48 traversal(current_node=current_node.left)
49 if current_node.right is not None:
50 traversal(current_node=current_node.right)
51
52 traversal(self.root)
53
54 return results
55
56 def dfs_in_order(self):
57 results = []
58
59 def traversal(current_node):
60 if current_node.left is not None:
61 traversal(current_node=current_node.left)
62 results.append(current_node.value)
63 if current_node.right is not None:
64 traversal(current_node=current_node.right)
65
66 traversal(self.root)
67
68 return results
69
70 def dfs_post_order(self):
71 results = []
72
73 def traversal(current_node):
74 if current_node.left is not None:
75 traversal(current_node=current_node.left)
76 if current_node.right is not None:
77 traversal(current_node=current_node.right)
78 results.append(current_node.value)
79
80 traversal(self.root)
81
82 return results
83
84
85if __name__ == "__main__":
86
87 bst = BinarySearchTree()
88
89 for i in [8, 3, 10, 1, 6, 9, 14]:
90 bst.insert(i)
91
92 print(bst.dfs_post_order())