二叉树的遍历图解例题汇总

二叉树作为数据结构的一种，是计算机程序设计领域中广泛运用的一种数据类型。在很多算法中，二叉树的遍历是非常重要的一个步骤。本文将以“二叉树的遍历图解例题汇总”为主题，从多个角度分析二叉树的遍历相关内容，以期为读者提供全面的学习指导。

一、二叉树的基础概念

二叉树是由结点构成的有限集合，其中每个结点最多有两个子结点，分别称为左子结点和右子结点。如果两个子结点都为空，则该结点称为叶子结点。对于其它结点，有以下定义：

1.度：结点拥有的子树数目称为其度；

2.深度：节点从根节点开始到该节点所经过的边数量；

3.高度：节点从该节点开始到叶子结点所经过的边数量。

二、二叉树的遍历方法

二叉树的遍历分为三种方法，分别为前序遍历、中序遍历和后序遍历。

1.前序遍历：先输出根结点，再遍历左子树，最后遍历右子树。

2.中序遍历：先遍历左子树，然后输出根结点，最后遍历右子树。

3.后序遍历：先遍历左子树，然后遍历右子树，最后输出根节点。

其中，前序遍历的递归实现代码如下：

void pre_order_traversal(TreeNode* root) {

if (root == NULL) return;

cout << root->val << " ";

pre_order_traversal(root->left);

pre_order_traversal(root->right);

}

中序遍历的递归实现代码如下：

void in_order_traversal(TreeNode* root) {

if (root == NULL) return;

in_order_traversal(root->left);

cout << root->val << " ";

in_order_traversal(root->right);

}

后序遍历的递归实现代码如下：

void post_order_traversal(TreeNode* root) {

if (root == NULL) return;

post_order_traversal(root->left);

post_order_traversal(root->right);

cout << root->val << " ";

}

三、应用场景

二叉树的遍历应用场景较多，包括但不限于以下几个方面：

1.搜索二叉树（BST）：使用中序遍历可将BST中的节点按从小到大的顺序输出；

2.表达式求值：根据前、中、后序遍历，可以对数学表达式进行求值；

3.镜像反转：根据前、中、后序遍历，可以将一棵二叉树进行镜像反转，进而得到该二叉树的镜像。

四、应用案例

以下是一个基于前序遍历和中序遍历重构二叉树的例子：

假设原二叉树的前序遍历是[3, 9, 20, 15, 7]，中序遍历是[9, 3, 15, 20, 7]，则该二叉树的结构如下图所示。


读者可以通过代码实现，验证该二叉树的构建过程。以下是重构二叉树的代码实现：

TreeNode* buildTree(vector & preorder, vector & inorder) {

if (preorder.empty()) return NULL;

int root_val = preorder[0];

TreeNode* root = new TreeNode(root_val);

auto it = find(inorder.begin(), inorder.end(), root_val);

vector left_inorder(inorder.begin(), it);

vector right_inorder(it + 1, inorder.end());

vector left_preorder(preorder.begin() + 1, preorder.begin() + 1 + left_inorder.size());

vector right_preorder(preorder.begin() + 1 + left_inorder.size(), preorder.end());

root->left = buildTree(left_preorder, left_inorder);

root->right = buildTree(right_preorder, right_inorder);

return root;

}