引入

我们从小学二年级开始,就学过二叉树了(bushi)

那么,如何用编程实现二叉树的遍历呢?

(这里使用c艹)

1
2
3
4
5
6
7

struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

二叉树的每个结点都是如此定义的

遍历方法

分为前序,中序,后序三种遍历方法。

前序是从根结点开始,访问到最左侧第一个叶子结点后,访问右侧叶子,然后返回上一级(不访问),访问同级右侧结点,然后往下按照先左后右的顺序访问,等左子树访问完毕后,访问右子树。

中序是从左侧第一个叶子结点开始,返回上一级(访问),下一级右侧,返回上上级,右侧最下方左侧结点,然后返回上一级(访问),以此类推。

后序是按从左到右的顺序,左侧第一个叶子结点开始,访问完上一级结点左侧后,去右侧,然后返回上一级。

每种遍历方法又分为递归和非递归两种

非递归方法

1. 前序遍历(非递归)

前序遍历的顺序是:根节点 -> 左子树 -> 右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result; // 存储遍历结果
if (!root) return result;

stack<TreeNode*> stk; // 辅助栈
stk.push(root); // 首先将根节点入栈

while (!stk.empty()) {
TreeNode* node = stk.top(); // 获取栈顶元素
stk.pop(); // 弹出栈顶元素
result.push_back(node->val); // 访问节点(加入结果)

// 先压右子节点,再压左子节点,保证左子节点先处理
if (node->right) stk.push(node->right);
if (node->left) stk.push(node->left);
}

return result;
}

2. 中序遍历(非递归)

中序遍历的顺序是:左子树 -> 根节点 -> 右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void inorderTraversal(TreeNode* root) {
std::stack<TreeNode*> stack;
TreeNode* current = root;

while (current != NULL || !stack.empty()) {
// 遍历到最左节点
while (current != NULL) {
stack.push(current);
current = current->left;
}
// 处理节点
current = stack.top();
stack.pop();
std::cout << current->val << " ";
// 转向右子树
current = current->right;
}
}

初始化:创建一个栈来存储节点,并将当前节点指向根节点。

遍历左子树:使用一个 while 循环,持续将当前节点的左子节点压入栈中,直到当前节点为 NULL。这一步实际上是在找到最左侧的节点。

处理节点:当当前节点为 NULL 且栈不为空时,弹出栈顶节点,输出该节点的值。这就是中序遍历的核心步骤。

转向右子树:将当前节点更新为弹出的节点的右子节点,继续上述过程。

结束条件:当当前节点为 NULL 且栈为空时,遍历结束。

3. 后序遍历(非递归)

后序遍历的顺序是:左子树 -> 右子树 -> 根节点。

后序遍历的非递归实现较复杂,可以使用两个栈来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if (!root) return result;

stack<TreeNode*> stk1, stk2;
stk1.push(root);

// 使用两个栈,stk1用于遍历,stk2用于存储结果
while (!stk1.empty()) {
TreeNode* node = stk1.top();
stk1.pop();
stk2.push(node);

// 左子节点和右子节点按顺序压入stk1
if (node->left) stk1.push(node->left);
if (node->right) stk1.push(node->right);
}

// 将stk2中的节点依次弹出到结果中
while (!stk2.empty()) {
result.push_back(stk2.top()->val);
stk2.pop();
}

return result;
}

这三种非递归遍历方法使用栈来模拟递归调用的过程,顺序不同是由于每种遍历访问节点的顺序不同。

递归方法

递归算法是一种非常常见且简单的二叉树遍历实现方式,它依赖函数调用栈的隐式机制来完成节点的访问。在二叉树的递归遍历中,递归函数会按照特定的顺序调用自身来遍历树的各个节点。

1. 前序遍历(递归)

定义

前序遍历的顺序是:先访问根节点,再访问左子树,最后访问右子树。

前序遍历顺序:

  • 根节点 -> 左子树 -> 右子树。

递归算法步骤

  1. 先访问当前节点(根节点)。
  2. 递归访问左子树。
  3. 递归访问右子树。

代码实现

1
2
3
4
5
6
7
void preorderTraversal(TreeNode* root, vector<int>& result) {
if (!root) return; // 递归终止条件:节点为空

result.push_back(root->val); // 访问根节点
preorderTraversal(root->left, result); // 递归遍历左子树
preorderTraversal(root->right, result); // 递归遍历右子树
}

过程说明

假设二叉树结构如下:

1
2
3
4
5
1
\
2
/
3
  • 首先访问根节点 1,然后递归访问它的右子节点 2
  • 访问 2 后,递归访问 2 的左子节点 3
  • 访问 3 后,没有更多节点,递归结束。

最终前序遍历的结果为 [1, 2, 3]


2. 中序遍历(递归)

定义

中序遍历的顺序是:先访问左子树,然后访问根节点,最后访问右子树。

中序遍历顺序:

  • 左子树 -> 根节点 -> 右子树。

递归算法步骤

  1. 递归访问左子树。
  2. 访问当前节点(根节点)。
  3. 递归访问右子树。

代码实现

1
2
3
4
5
6
7
void inorderTraversal(TreeNode* root, vector<int>& result) {
if (!root) return; // 递归终止条件:节点为空

inorderTraversal(root->left, result); // 递归遍历左子树
result.push_back(root->val); // 访问根节点
inorderTraversal(root->right, result); // 递归遍历右子树
}

过程说明

假设二叉树结构如下:

1
2
3
4
5
1
\
2
/
3
  • 首先递归访问 1 的左子树,但为空,直接访问根节点 1
  • 然后递归访问右子树,从 2 开始,递归访问 2 的左子节点 3
  • 访问完 3,回到 2,访问 2

最终中序遍历的结果为 [1, 3, 2]


3. 后序遍历(递归)

定义

后序遍历的顺序是:先访问左子树,再访问右子树,最后访问根节点。

后序遍历顺序:

  • 左子树 -> 右子树 -> 根节点。

递归算法步骤

  1. 递归访问左子树。
  2. 递归访问右子树。
  3. 访问当前节点(根节点)。

代码实现

1
2
3
4
5
6
7
void postorderTraversal(TreeNode* root, vector<int>& result) {
if (!root) return; // 递归终止条件:节点为空

postorderTraversal(root->left, result); // 递归遍历左子树
postorderTraversal(root->right, result); // 递归遍历右子树
result.push_back(root->val); // 访问根节点
}

过程说明

假设二叉树结构如下:

1
2
3
4
5
1
\
2
/
3
  • 首先递归访问 1 的左子树,空节点返回。
  • 然后递归访问 1 的右子节点 2,继续递归访问 2 的左子节点 3
  • 访问 3 后返回,访问 2 后返回,最后访问根节点 1

最终后序遍历的结果为 [3, 2, 1]


递归遍历的工作原理

递归遍历的核心思想是利用系统调用栈隐式地保存当前节点的状态,并通过函数的自我调用完成对二叉树各个节点的遍历。在每一次递归调用时,栈帧会记录当前函数的上下文(包括参数和本地变量),当递归返回时,栈帧会恢复之前的状态。因此,递归算法中不需要显式地使用栈结构来保存节点状态,递归的函数调用本身就是栈的模拟。

通过遍历确定二叉树

首先,一种遍历是肯定不能的

前序遍历+后序也不能

但中序+任意就可以

下面是后序和中序的一个例子

给定二叉树的后序遍历中序遍历,可以确定这棵二叉树的结构。

  • 后序遍历dabec
  • 中序遍历debac

重建二叉树的步骤

  1. 后序遍历的特点:后序遍历的最后一个节点是根节点。因此,通过后序遍历可以找到二叉树的根节点。

    • 在后序遍历 dabec 中,最后一个元素 c 是二叉树的根节点。
  2. 在中序遍历中找到根节点:通过中序遍历,可以将二叉树分为左子树和右子树。

    • 中序遍历是 debac,根节点 c 在中序遍历中的位置是最后一位,因此 deba 是左子树,右子树为空。
  3. 递归构建左子树

    • 左子树的中序遍历是 deba,左子树的后序遍历是 dabe(从后序遍历中取去掉根节点的部分)。
    • 继续对 dabedeba 递归构建。
  4. 对左子树进行递归构建

    • 在后序遍历 dabe 中,最后一个元素 e 是左子树的根节点。
    • 在中序遍历 deba 中,根节点 e 的位置将 dba 分为左右子树,左子树为 d,右子树为 ba
  5. 递归构建左子树和右子树

    • 对左子树 d,中序遍历和后序遍历均为 d,因此它是叶子节点。
    • 对右子树 ba
      • 在后序遍历 ba 中,根节点是 a,剩下的 b 是它的左子树。
      • 对左子树 b,中序遍历和后序遍历均为 b,因此它是叶子节点。

最终二叉树的结构

将上述步骤的结果组合在一起,二叉树的形状如下:

1
2
3
4
5
6
7
    c
/
e
/ \
d a
/
b

详细解释

  • 根节点是 c,它的左子树是 e
  • 节点 e 的左子树是 d,右子树是 a
  • 节点 a 有一个左子树 b,而 bd 都是叶子节点。

通过后序遍历和中序遍历,我们成功地重建了这棵二叉树。


递归 vs. 非递归

  1. 递归遍历

    • 简洁且符合思维逻辑。
    • 利用系统调用栈来管理递归状态,不需要手动维护栈。
    • 如果树的深度较深,递归深度过大会导致栈溢出。
  2. 非递归遍历

    • 使用显式栈来模拟递归,避免了函数调用的开销。
    • 更加适合处理非常深的树,避免了递归栈溢出的问题。
    • 实现较为复杂,尤其是后序遍历,需要用到两个栈。

总结

递归遍历是通过系统调用栈隐式地实现节点状态的保存与恢复,而非递归遍历则通过显式的栈来模拟递归过程。选择递归或非递归方法通常取决于具体应用场景以及对性能和栈深度的要求。