Python -二叉树 创建与遍历算法(很详细）

树表示由边连接的节点。它是一个非线性的数据结构。它具有以下特性。

1. 一个节点被标记为根节点。
2. 除根节点之外的每个节点都与一个父节点关联。
3. 每个节点可以有一个arbiatry编号的chid节点。

我们使用前面讨论的os节点概念在python中创建了一个树数据结构。我们将一个节点指定为根节点，然后将更多的节点添加为子节点。下面是创建根节点的程序。

创建树

创建根

我们只需要创建一个节点类并向节点添加赋值。这就变成了只有根节点的树。

1 class Node:
 2 
 3     def __init__(self, data):
 4         self.left = None  #左节点
 5         self.right = None #右节点
 6         self.data = data  #值
 7 
 8     def PrintTree(self):
 9         print(self.data)
10 
11 root = Node(10) #创建节点
12 
13 root.PrintTree()

当执行上述代码时，将产生以下结果-

10

插入到树中

要插入到树中，我们使用上面创建的相同节点类，并向其添加一个插入类。insert类将节点的值与父节点的值进行比较，并决定将其添加为左节点或右节点。最后，PrintTree类用于打印树。

1 class Node:
 2     def __init__(self, data):
 3         self.left = None
 4         self.right = None
 5         self.data = data
 6 
 7     def insert(self, data):
 8     # 将新值与父节点进行比较
 9         if self.data:  # 非空
10             if data < self.data:            #新值较小，放左边
11                 if self.left is None:       #若空，则新建插入节点
12                     self.left = Node(data)
13                 else:                       #否则，递归往下查找
14                     self.left.insert(data)
15             elif data > self.data:          #新值较大，放右边
16                 if self.right is None:      #若空，则新建插入节点
17                     self.right = Node(data)
18                 else:                       #否则，递归往下查找
19                     self.right.insert(data)
20         else:
21             self.data = data                
22 
23     # 打印这棵树，中序遍历
24     def PrintTree(self):
25         if self.left:
26             self.left.PrintTree()
27         print( self.data),
28         if self.right:
29             self.right.PrintTree()
30 
31 # 使用insert方法添加节点
32 root = Node(12)
33 root.insert(6)
34 root.insert(14)
35 root.insert(3)
36 
37 root.PrintTree()

当执行上述代码时，将产生以下结果-

3 6 12 14

遍历树

可以通过决定访问每个节点的序列来遍历树。我们可以清楚地看到，我们可以从一个节点开始，然后首先访问左子树，然后访问右子树。或者我们也可以先访问右子树然后访问左子树。因此，这些树遍历方法有不同的名称。我们将在实现树遍历算法的章节中详细研究它们。

Python树遍历算法

遍历是一个访问树的所有节点的过程，也可以打印它们的值。因为，所有节点都是通过边(链接)连接的，所以我们总是从根(头)节点开始。也就是说，我们不能随机访问树中的节点。我们走过一棵树有三种方法

1. 先序遍历
2. 中序遍历
3. 后序遍历

顺序遍历

在这个遍历方法中，首先访问左子树，然后访问根，然后访问右子树。我们应该始终记住，每个节点都可以表示子树本身。
在下面的python程序中，我们使用Node类为根节点以及左右节点创建位置占位符。然后我们创建一个insert函数来向树中添加数据。最后，通过创建一个空列表并首先添加左节点，然后添加根节点或父节点来实现order遍历逻辑。最后添加左节点来完成order遍历。

1 class Node:
 2 
 3     def __init__(self, data):
 4 
 5         self.left = None
 6         self.right = None
 7         self.data = data
 8 # Insert Node
 9     def insert(self, data):
10 
11         if self.data:
12             if data < self.data:
13                 if self.left is None:
14                     self.left = Node(data)
15                 else:
16                     self.left.insert(data)
17             elif data > self.data:
18                 if self.right is None:
19                     self.right = Node(data)
20                 else:
21                     self.right.insert(data)
22         else:
23             self.data = data
24 
25 # Print the Tree
26     def PrintTree(self):
27         if self.left:
28             self.left.PrintTree()
29         print( self.data),
30         if self.right:
31             self.right.PrintTree()
32 
33 # 中序遍历
34 # Left -> Root -> Right
35     def inorderTraversal(self, root):
36         res = []
37         if root:
38             res = self.inorderTraversal(root.left)
39             res.append(root.data)
40             res = res + self.inorderTraversal(root.right)
41         return res
42 
43 root = Node(27)
44 root.insert(14)
45 root.insert(35)
46 root.insert(10)
47 root.insert(19)
48 root.insert(31)
49 root.insert(42)
50 print(root.inorderTraversal(root))

当执行上述代码时，将产生以下结果-

[10、14、19、27、31、35、42]

预购遍历

在这种遍历方法中，首先访问根节点，然后访问左子树，最后访问右子树。
在下面的python程序中，我们使用Node类为根节点以及左右节点创建位置占位符。然后我们创建一个insert函数来向树中添加数据。最后，通过创建一个空列表并首先添加根节点，然后添加左节点来实现预排序遍历逻辑。最后添加正确的节点来完成预定遍历。请注意，此过程对每个子树重复，直到所有t

1 class Node:
 2 
 3     def __init__(self, data):
 4 
 5         self.left = None
 6         self.right = None
 7         self.data = data
 8 # Insert Node
 9     def insert(self, data):
10 
11         if self.data:
12             if data < self.data:
13                 if self.left is None:
14                     self.left = Node(data)
15                 else:
16                     self.left.insert(data)
17             elif data > self.data:
18                 if self.right is None:
19                     self.right = Node(data)
20                 else:
21                     self.right.insert(data)
22         else:
23             self.data = data
24 
25 # Print the Tree
26     def PrintTree(self):
27         if self.left:
28             self.left.PrintTree()
29         print( self.data),
30         if self.right:
31             self.right.PrintTree()
32 
33 # 先序遍历
34 # Root -> Left ->Right
35     def PreorderTraversal(self, root):
36         res = []
37         if root:
38             res.append(root.data)
39             res = res + self.PreorderTraversal(root.left)
40             res = res + self.PreorderTraversal(root.right)
41         return res
42 
43 root = Node(27)
44 root.insert(14)
45 root.insert(35)
46 root.insert(10)
47 root.insert(19)
48 root.insert(31)
49 root.insert(42)
50 print(root.PreorderTraversal(root))

当执行上述代码时，将产生以下结果-

[27, 14, 10, 19, 35, 31, 42]

后序遍历

在这个遍历方法中，根节点最后访问，因此得名。首先遍历左子树，然后遍历右子树，最后遍历根节点。

在下面的python程序中，我们使用Node类为根节点以及左右节点创建位置占位符。然后我们创建一个insert函数来向树中添加数据。最后，通过创建一个空列表并先添加左节点后添加右节点来实现后序遍历逻辑。最后添加根节点或父节点来完成后序遍历。请注意，此过程将对每个子树重复，直到遍历所有节点。

1 class Node:
 2 
 3     def __init__(self, data):
 4 
 5         self.left = None
 6         self.right = None
 7         self.data = data
 8 # Insert Node
 9     def insert(self, data):
10 
11         if self.data:
12             if data < self.data:
13                 if self.left is None:
14                     self.left = Node(data)
15                 else:
16                     self.left.insert(data)
17             elif data > self.data:
18                 if self.right is None:
19                     self.right = Node(data)
20                 else:
21                     self.right.insert(data)
22         else:
23             self.data = data
24 
25 # Print the Tree
26     def PrintTree(self):
27         if self.left:
28             self.left.PrintTree()
29         print( self.data),
30         if self.right:
31             self.right.PrintTree()
32 
33 # 后序遍历
34 # Left ->Right -> Root
35     def PostorderTraversal(self, root):
36         res = []
37         if root:
38             res = self.PostorderTraversal(root.left)
39             res = res + self.PostorderTraversal(root.right)
40             res.append(root.data)
41         return res
42 
43 root = Node(27)
44 root.insert(14)
45 root.insert(35)
46 root.insert(10)
47 root.insert(19)
48 root.insert(31)
49 root.insert(42)
50 print(root.PostorderTraversal(root))

当执行上述代码时，将产生以下结果-

[10、19、14、31、42、35、27]