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:
	//前序遍历
	vector<int> preorderTraversal(TreeNode* root) {
		stack<TreeNode*> st; //辅助栈
		vector<int> 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:
	//中序遍历
	vector<int> inorderTraversal(TreeNode* root) {
		stack<TreeNode*> st; //辅助栈
		vector<int> 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:
	//后序遍历
	vector<int> postorderTraversal(TreeNode* root) {
		stack<TreeNode*> st; //辅助栈
		vector<int> 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++ 非递归实现二叉树的前中后序遍历的文章就介绍到这了,更多相关二叉树前中后序遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 二叉树遍历 非递归 C++实现代码

    二叉树的非递归遍历 二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的.对于二叉树,有前序.中序以及后序三种遍历方法.因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁.而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现.在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点. 一.前序遍历 前序遍历按照"根结点-左孩子-右孩子"的顺序进行访问. 1.递归实现 复制代码 代码

  • 一波二叉树遍历问题的C++解答实例分享

    题目一: 输入一颗二元树,从上往下按层打印树的每个节点,同一层按照从左往右的顺序打印. 输入样例: 8 / / 6 10 / / / / 5 7 9 11 输出样例: 复制代码 代码如下: 8 6 10 5 7 9 11 思路分析: 把一颗二叉树抽象成三个节点:根节点.左节点.右节点. 先序遍历即可得到按行输出的效果. 对于左子树只要保存其根节点,既保存了整个左子树.(右子树一样) 对于根节点之外的两个子树来说说,始终是先访问左子树的根节点,再访问右子树的根节点. 因此可以使用队列存储. 代码实

  • C++实现二叉树遍历序列的求解方法

    本文详细讲述了C++实现二叉树遍历序列的求解方法,对于数据结构与算法的学习有着很好的参考借鉴价值.具体分析如下: 一.由遍历序列构造二叉树 如上图所示为一个二叉树,可知它的遍历序列分别为: 先序遍历:ABDECFG 中序遍历:DBEAFCG 后序遍历:DEBFGCA 我们需要知道的是,由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树:由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树:但是如果只知道先序序列和后序序列,则无法唯一确定一棵二叉树. 二.已知二叉树的先序序列和中序序列,求后序

  • Java 二叉树遍历的常用方法

    采用前序遍历.中序遍历.后续遍历实现时,即便采用不同的实现方式(递归方式.非递归),它们的算法结构是有很大的相似性.因而针对前三种的遍历我们会总结出对应通用的解决框架,便于在解决二叉树问题时进行使用. 递归方式 递归方式遍历二叉树时,无论是 前序遍历.中序遍历 还是 后续遍历 的方式,它们最大的区别就是对节点数据的访问位置不同.除此之外其结构完全一致,因而我们总结出如下的框架结构: void traverse(TreeNode root) { //终止条件 if(root == null) re

  • java实现二叉树遍历的三种方式

    本文实例为大家分享了java实现二叉树遍历的具体代码,供大家参考,具体内容如下 二叉树如下: 遍历结果如下: 以下是实现代码: package binTree; import java.util.Stack; /** * @author bin.zhang * @version 2017年8月29日 上午10:22:01 */ public class BinTreeTraversal { public static void main(String[] args) { System.out.p

  • C++ 非递归实现二叉树的前中后序遍历

    目录 二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历 二叉树的前序遍历 在不使用递归的方式遍历二叉树时,我们可以使用一个栈模拟递归的机制.二叉树的前序遍历顺序是:根 → 左子树 → 右子树,我们可以先将二叉树的左路结点入栈,在入栈的同时便对其进行访问,此时就相当于完成了根和左子树的访问,当左路结点入栈完毕后再从栈顶依次取出结点,并用同样的方式访问其右子树即可. 具体步骤如下: 将左路结点入栈,入栈的同时访问左路结点. 取出栈顶结点top. 准备访问top结点的右子树. struct Tre

  • Java语言实现非递归实现树的前中后序遍历总结

    前言 三种遍历的递归写法都很好写,所以总结一下非递归写法. 先贴一张图复习一下三种遍历方式就进入正文啦~ [注:本文所有代码实现中树的结点定义如下: public class Node { int val; Node left; Node right; Node parent; Node() {} Node(int val) { this.val = val; } } 1.前序遍历 实现思路: 前序遍历的顺序是:根结点 -> 左孩子 -> 右孩子 借助一个栈结构先将根结点压入栈,然后循环每次取

  • java非递归实现之二叉树的前中后序遍历详解

    二叉树的前中后序遍历 核心思想:用栈来实现对节点的存储.一边遍历,一边将节点入栈,在需要时将节点从栈中取出来并遍历该节点的左子树或者右子树,重复上述过程,当栈为空时,遍历完成. 前序遍历 //非递归 //根 左 右 class Solution { public List<Integer> preorderTraversal(TreeNode root) { //用数组来存储前序遍历结果 List<Integer> list = new ArrayList<>(); i

  • Java数据结构最清晰图解二叉树前 中 后序遍历

    目录 一,前言 二,树 ①概念 ②树的基础概念 三,二叉树 ①概念 ②两种特殊的二叉树 ③二叉树的性质 四,二叉树遍历 ①二叉树的遍历 ②前序遍历 ③中序遍历 ④后序遍历 五,完整代码 一,前言 二叉树是数据结构中重要的一部分,它的前中后序遍历始终贯穿我们学习二叉树的过程,所以掌握二叉树三种遍历是十分重要的.本篇主要是图解+代码Debug分析,概念的部分讲非常少,重中之重是图解和代码Debug分析,我可以保证你看完此篇博客对于二叉树的前中后序遍历有一个新的认识!!废话不多说,让我们学起来吧!!

  • Java 数据结构中二叉树前中后序遍历非递归的具体实现详解

    目录 一.前序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现 二.中序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现 三.后序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现 一.前序遍历 1.题目描述 给你二叉树的根节点 root ,返回它节点值的 前序 遍历. 2.输入输出示例 示例 1: 输入:root = [1,null,2,3] 输出:[1,2,3] 示例2: 输入:root = [] 输出:[] 示例 3: 输入:root = [1

  • 二叉树递归迭代及morris层序前中后序遍历详解

    目录 分析二叉树的前序,中序,后序的遍历步骤 1.层序遍历 方法一:广度优先搜索 方法二:递归 2.前序遍历 3.中序遍历 4.后序遍历 递归解法 前序遍历--递归 迭代解法 前序遍历--迭代 核心思想: 三种迭代解法的总结: Morris遍历 morris--前序遍历 morris--中序遍历 morris--后序遍历: 分析二叉树的前序,中序,后序的遍历步骤 1.层序遍历 方法一:广度优先搜索   (以下解释来自leetcode官方题解) 我们可以用广度优先搜索解决这个问题. 我们可以想到最

  • C语言实现线索二叉树的前中后创建和遍历详解

    目录 1.结构 1.1初始化tag 2.基本操作 2.1先序创建二叉树 2.2.先序线索化 2.2.1.先序遍历 2.3.中序线索化 2.3.1中序遍历 2.4.后序线索化 2.4.1后序遍历 总结 1.结构 #include<stdio.h> #include<stdlib.h> #define false 0 #define true 1 using namespace std; typedef struct BTnode{ int data; struct BTnode *l

  • Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】

    本文实例讲述了Python二叉树的遍历操作.分享给大家供大家参考,具体如下: # coding:utf-8 """ @ encoding: utf-8 @ author: lixiang @ email: lixiang_cn@foxmail.com @ python_version: 2 @ time: 2018/4/11 0:09 @ more_info: 二叉树是有限个元素的集合,该集合或者为空.或者有一个称为根节点(root)的元素及两个互不相交的.分别被称为左子树和

  • Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】

    本文实例讲述了Java实现的二叉树常用操作.分享给大家供大家参考,具体如下: import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; //二叉树的建树,前中后 递归非递归遍历 层序遍历 //Node节点 class Node { int element; Node left; Node right; public Node() { } public Node(int element) { this.

  • 探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)

    如有不足之处,还望指正! 复制代码 代码如下: // BinaryTree.cpp : 定义控制台应用程序的入口点.//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include "stdafx.h"#include<iostream>#include<string>#include <stack>using namespace std;template<class T>struct BiNode{ T data; 

随机推荐