Python 中树的中序遍历

Fariba Laiq 2023年1月30日 2022年7月18日
  1. 树的中序遍历
  2. Python 中的中序树遍历实现
Python 中树的中序遍历

树是一种分层数据结构,由由边连接的节点组成。遍历树意味着只访问树的每个节点一次。

我们出于不同目的遍历树,例如显示节点、查找最大和最小节点、搜索、排序等。在本文中,我们将学习和实现 Python 中的 inorder 遍历树。

树的中序遍历

Inorder 遍历是一种深度优先遍历。假设我们有以下树。

二叉树

如果我们应用 inorder 遍历,我们将对每个节点执行以下步骤。

  1. 首先,我们应该访问左子树的所有节点。
  2. 然后,我们访问父节点。
  3. 然后,我们访问右子树中的所有节点。

我们将按照 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
Author: Fariba Laiq
Fariba Laiq avatar Fariba Laiq avatar

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