一文带你读懂C++实现二叉树的三种遍历

这篇文章给大家分享的是C++实现二叉树遍历的内容，包括二叉树的前序、中序和后序这三种遍历，对大家学习和理解二叉树遍历有一定的帮助，小编觉得挺实用的，因此分享给大家做个参考，文中示例代码介绍的非常详细，感兴趣的朋友接下来一起跟随小编看看吧。

二叉树的前序遍历

在不使用递归的方式遍历二叉树时，我们可以使用一个栈模拟递归的机制。二叉树的前序遍历顺序是：根 → 左子树 → 右子树，我们可以先将二叉树的左路结点入栈，在入栈的同时便对其进行访问，此时就相当于完成了根和左子树的访问，当左路结点入栈完毕后再从栈顶依次取出结点，并用同样的方式访问其右子树即可。

具体步骤如下：

1. 将左路结点入栈，入栈的同时访问左路结点。
2. 取出栈顶结点top。
3. 准备访问top结点的右子树。

struct TreeNode {
    
    int val;
    
    TreeNode *left;
    
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {
}

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

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

}
    ;

class Solution {
    
public:
	//前序遍历
	vectorint>
 preorderTraversal(TreeNode* root) {
    
		stackTreeNode*>
     st;
     //辅助栈
		vectorint>
     ret;
     //用于存放前序遍历的结果
		TreeNode* cur = root;

		while (cur || !st.empty())
		{

			//1、将左路结点入栈，入栈的同时访问左路结点
			while (cur)
			{
    
				st.push(cur);
    
				ret.push_back(cur->
    val);
    
				cur = cur->
    left;

			}
    
			//2、取出栈顶结点
			TreeNode* top = st.top();
    
			st.pop();
    
			//3、准备访问其右子树
			cur = top->
    right;

		}
    
		return ret;
 //返回前序遍历结果
	}

}
    ;

二叉树的中序遍历

二叉树的中序遍历顺序是：左子树 → 根 → 右子树，我们可以先将二叉树的左路结点入栈，当左路结点入栈完毕后，再从栈顶依次取出结点，在取出结点的同时便对其进行访问，此时就相当于先访问了左子树再访问了根，之后再用同样的方式访问取出结点的右子树即可。

具体步骤如下：

1. 将左路结点入栈。
2. 取出栈顶结点top并访问。
3. 准备访问top结点的右子树。

struct TreeNode {
    
    int val;
    
    TreeNode *left;
    
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {
}

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

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

}
    ;

class Solution {
    
public:
	//中序遍历
	vectorint>
 inorderTraversal(TreeNode* root) {
    
		stackTreeNode*>
     st;
     //辅助栈
		vectorint>
     ret;
     //用于存放中序遍历的结果
		TreeNode* cur = root;

		while (cur || !st.empty())
		{

			//1、将左路结点入栈
			while (cur)
			{
    
				st.push(cur);
    
				cur = cur->
    left;

			}
    
			//2、取出栈顶结点并访问
			TreeNode* top = st.top();
    
			st.pop();
    
			ret.push_back(top->
    val);
    
			//3、准备访问其右子树
			cur = top->
    right;

		}
    
		return ret;
 //返回中序遍历结果
	}

}
    ;

二叉树的后序遍历

二叉树的后序遍历顺序是：左子树 → 右子树 → 根，我们可以先将二叉树的左路结点入栈，当左路结点入栈完毕后，再观察栈顶结点，若栈顶结点的右子树为空，或栈顶结点的右子树已经被访问过了，则栈顶结点可以出栈并访问，若栈顶结点的右子树还未被访问，则用同样的方式访问栈顶结点的右子树，直到其右子树被访问后再访问该结点，这时的访问顺序遵循了二叉树的后序遍历所要求的顺序。

具体步骤如下：

1. 将左路结点入栈。
2. 观察栈顶结点top。
3. 若top结点的右子树为空，或top结点的右子树已经访问过了，则访问top结点。访问top结点后将其从栈中弹出，并更新上一次访问的结点为top。
4. 若top结点的右子树还未被访问，则准备访问其右子树。

struct TreeNode {
    
    int val;
    
    TreeNode *left;
    
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {
}

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

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

}
    ;

class Solution {
    
public:
	//后序遍历
	vectorint>
 postorderTraversal(TreeNode* root) {
    
		stackTreeNode*>
     st;
     //辅助栈
		vectorint>
     ret;
     //用于存放后序遍历的结果
		TreeNode* cur = root;
    
		TreeNode* prev = nullptr;
 //记录上一次访问的结点
		while (cur || !st.empty())
		{

			//1、将左路结点入栈
			while (cur)
			{
    
				st.push(cur);
    
				cur = cur->
    left;

			}
    
			//2、取出栈顶结点
			TreeNode* top = st.top();
    
			//3、若取出结点的右子树为空，或右子树已经访问过了，则访问该结点
			if (top->
    right == nullptr || top->
right == prev)
			{
    
				//访问top结点后将其从栈中弹出
				st.pop();
    
				ret.push_back(top->
    val);
    
				//更新上一次访问的结点为top
				prev = top;

			}

			else //4、若取出结点的右子树还未被访问，则准备访问其右子树
			{
    
				cur = top->
    right;

			}

		}
    
		return ret;
 //返回后序遍历结果
	}

}
    ;
    

注意： 看动图演示时请结合所给代码，动图是严格按照代码的逻辑制作的。

现在大家对于C++实现二叉树遍历的方法应该都有所了解了，希望大家阅读完这篇文章能有所收获。最后，想要了解更多二叉树遍历的内容，大家可以关注网络其它相关文章。

文本转载自PHP中文网

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！