Python 中树的中序遍历
树是一种分层数据结构，由由边连接的节点组成。遍历树意味着只访问树的每个节点一次。
我们出于不同目的遍历树，例如显示节点、查找最大和最小节点、搜索、排序等。在本文中，我们将学习和实现 Python 中的 inorder 遍历树。
树的中序遍历
Inorder 遍历是一种深度优先遍历。假设我们有以下树。
如果我们应用 inorder 遍历，我们将对每个节点执行以下步骤。
- 首先，我们应该访问左子树的所有节点。
- 然后，我们访问父节点。
- 然后，我们访问右子树中的所有节点。
我们将按照 4, 2, 5, 1, 6, 3, 7 的顺序获取节点。
Python 中的中序树遍历实现
有两种方法可以在 Python 中实现 inorder 遍历。递归和迭代方法。
递归方法
递归方法易于实现和理解。在下面的代码中，我们创建了一个类 Node 作为存储树的数据结构。
每个节点由一个值、它的左子节点和右子节点组成。inorder 遍历将递归地为左右子树工作。
对于每个节点，将通过访问其左节点、父节点和右节点来执行 inorder 遍历。
示例代码：
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.val = value
def inorder(root):
if root:
inorder(root.left)
print(str(root.val))
inorder(root.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)
输出：
Inorder traversal of the Tree
4
2
5
1
6
3
7
迭代方法
在迭代方法中，我们必须维护一个 stack 来存储我们稍后将访问的节点。我们在下面的代码中创建了类 Node，就像以前一样。
我们创建了一个空堆栈，并通过将其设为当前节点从根节点开始。如果当前节点存在，我们会将其压入栈中，并转到其左侧节点。
否则，如果节点不存在，我们将从堆栈中弹出一个元素并打印它。当不存在左节点时，我们将通过使其成为当前节点来转到右节点。
我们将迭代地重复相同的过程，直到堆栈和当前元素都为空。
示例代码：
from collections import deque
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.val = value
def inorder(root):
stack = deque()
curr = root
while stack or curr:
if curr:
stack.append(curr)
curr = curr.left
else:
curr = stack.pop()
print(curr.val)
curr = curr.right
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)
输出：
Inorder traversal of the Tree
4
2
5
1
6
3
7
I am Fariba Laiq from Pakistan. An android app developer, technical content writer, and coding instructor. Writing has always been one of my passions. I love to learn, implement and convey my knowledge to others.
LinkedIn