Python Data Structure 简明教程
Python - Binary Tree
树表示由边连接的节点。它是一种非线性数据结构。它具有以下属性：
Tree represents the nodes connected by edges. It is a non-linear data structure. It has the following properties −
-
One node is marked as Root node.
-
Every node other than the root is associated with one parent node.
-
Each node can have an arbiatry number of chid node.
我们通过使用前面讨论过的节点概念在 Python 中创建一个树数据结构。我们将一个节点指定为根节点，然后添加更多节点作为子节点。以下是创建根节点的程序。
We create a tree data structure in python by using the concept os node discussed earlier. We designate one node as root node and then add more nodes as child nodes. Below is program to create the root node.
Create Root
我们只创建一个 Node 类，并将一个值分配给节点。这将成为仅有一个根节点的树。
We just create a Node class and add assign a value to the node. This becomes tree with only a root node.
Inserting into a Tree
为了插入树中，我们使用上面创建的相同 Node 类，并向其添加一个插入类。插入类将节点的值与父节点的值进行比较，并决定将其添加为左节点还是右节点。最后，使用 PrintTree 类来打印树。
To insert into a tree we use the same node class created above and add a insert class to it. The insert class compares the value of the node to the parent node and decides to add it as a left node or a right node. Finally the PrintTree class is used to print the tree.
Example
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def insert(self, data):
# Compare the new value with the parent node
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.PrintTree()Traversing a Tree
可以通过决定一个顺序来访问每个节点来遍历树。我们可以清楚地看到，我们可以从一个节点开始，然后先访问左子树，再访问右子树。或者，我们也可以先访问右子树，再访问左子树。因此，这些树遍历方法有不同的名称。
The tree can be traversed by deciding on a sequence to visit each node. As we can clearly see we can start at a node then visit the left sub-tree first and right sub-tree next. Or we can also visit the right sub-tree first and left sub-tree next. Accordingly there are different names for these tree traversal methods.
Tree Traversal Algorithms
遍历是一个访问树的所有节点并可能也打印其值的过程。因为所有节点都通过边（链接）连接，所以我们总是从根（头）节点开始。也就是说，我们不能在树中随机访问一个节点。我们可以使用三种方式来遍历树。
Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree.
-
In-order Traversal
-
Pre-order Traversal
-
Post-order Traversal
In-order Traversal
在这种遍历方法中，首先访问左子树，然后访问根，最后访问右子树。我们应该始终记住，每个节点本身都可能表示一个子树。
In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself.
在下面的 Python 程序中，我们使用 Node 类来创建根节点以及左节点和右节点的占位符。然后，我们创建一个插入函数以将数据添加到树中。最后，通过创建空列表并首先添加左节点，然后添加根节点或父节点来实现中序遍历逻辑。
In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes. Then, we create an insert function to add data to the tree. Finally, the In-order traversal logic is implemented by creating an empty list and adding the left node first followed by the root or parent node.
最后，添加左节点以完成中序遍历。请注意，该过程将对每个子树重复，直到遍历所有节点。
At last the left node is added to complete the In-order traversal. Please note that this process is repeated for each sub-tree until all the nodes are traversed.
Example
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
else data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Inorder traversal
# Left -> Root -> Right
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))Output
执行上述代码后，将生成以下结果 −
When the above code is executed, it produces the following result −
[10, 14, 19, 27, 31, 35, 42]Pre-order Traversal
在这种遍历方法中，首先访问根节点，然后访问左子树，最后访问右子树。
In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.
在下面的 Python 程序中，我们使用 Node 类来创建根节点以及左节点和右节点的占位符。然后，我们创建一个插入函数来向树中添加数据。最后，通过创建一个空列表并首先添加根节点，然后添加左节点，实现了先序遍历逻辑。
In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes. Then, we create an insert function to add data to the tree. Finally, the Pre-order traversal logic is implemented by creating an empty list and adding the root node first followed by the left node.
最后，添加右节点以完成先序遍历。请注意，此过程会重复执行，直到遍历完所有节点为止。
At last, the right node is added to complete the Pre-order traversal. Please note that, this process is repeated for each sub-tree until all the nodes are traversed.
Example
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Preorder traversal
# Root -> Left ->Right
def PreorderTraversal(self, root):
res = []
if root:
res.append(root.data)
res = res + self.PreorderTraversal(root.left)
res = res + self.PreorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))Output
执行上述代码后，将生成以下结果 −
When the above code is executed, it produces the following result −
[27, 14, 10, 19, 35, 31, 42]Post-order Traversal
在此遍历方法中，根节点最后访问，因此得名。首先，我们遍历左子树，然后遍历右子树，最后遍历根节点。
In this traversal method, the root node is visited last, hence the name. First, we traverse the left subtree, then the right subtree and finally the root node.
在下面的 Python 程序中，我们使用 Node 类来创建根节点以及左节点和右节点的占位符。然后，我们创建一个插入函数来向树中添加数据。最后，通过创建一个空列表并先添加左节点，然后添加右节点，实现了后序遍历逻辑。
In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes. Then, we create an insert function to add data to the tree. Finally, the Post-order traversal logic is implemented by creating an empty list and adding the left node first followed by the right node.
最后，添加根节点或父节点以完成后序遍历。请注意，此过程会重复执行，直到遍历完所有节点为止。
At last the root or parent node is added to complete the Post-order traversal. Please note that, this process is repeated for each sub-tree until all the nodes are traversed.
Example
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
else if data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))