二叉树的非递归遍历(前序、中序和后序)_realwongp的博客-程序员信息网_前向遍历和后向遍历二叉树

技术标签: 二叉树  遍历  

最近有小伙伴面试的时候被问到写循环遍历二叉树,虽然我面了几次还没被问到相关的,但是想着也是该会的东西,就花了点时间写了点代码,废话不多说,上菜。


我的二叉树的声明如下:
这个节点是在offer这个包里面的,所以下面的代码都会 import offer.TreeNode

package offer;

/**
 * @author WangPan 
 * @date 2019/2/25 19:44
 * @description
 **/
public class TreeNode {
    
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x){
     val = x;}
}

前序遍历

我一般对三种遍历方式的记法就是看“根”的位置,遍历的前中后其实就是对应的根节点的遍历顺序,前序遍历即:根左右
思路:循环遍历,这里使用一个栈,栈先入后出,因此循环先弹出栈顶节点,再将该栈顶节点的右节点和左节点入栈。代码如下:

package binaryTree;

import java.util.Stack;
import offer.TreeNode;
/**
 * @author WangPan
 * @date 2019/4/20 17:01
 * @description 二叉树的前序遍历,非递归版本
 **/
public class preorder {
    

    public static void pre(TreeNode root){
    
        if(root == null)
            return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
    
            TreeNode temp = stack.pop();
            System.out.println(temp.val);
            //每出栈一个,依次把右左子点入栈
            if(temp.right != null)
                stack.push(temp.right);
            if(temp.left != null)
                stack.push(temp.left);
        }
    }
}

中序遍历

遍历方式:左根右
思路:仍然使用栈来保存节点,中序遍历要求先访问到最左节点,因此先要将left路径上所有元素依次入栈,再进行出栈操作,如果栈顶元素的右节点不为空,则将其右节点入栈,对其右子树进行中序遍历。

package binaryTree;

import java.util.Stack;
import offer.TreeNode;

/**
 * @author WangPan 
 * @date 2019/4/20 19:08
 * @description 二叉树的中序遍历,非递归版本
 **/
public class inorder {
    

    public static void in(TreeNode root){
    
        if(root == null)
            return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
    
            //首先让这个节点的所有左节点一次入栈
            while (root.left != null){
    
                stack.push(root.left);
                root = root.left;
            }
            TreeNode temp = stack.pop();
            System.out.println(temp.val);
            //出栈节点的右节点如果不是null则要进栈,对其右子树进行中序遍历
            if(temp.right != null){
    
                root = temp.right;
                stack.push(root);
            }
        }
    }
}

后序遍历

遍历方式:左右根
思路1:因为仍然要先从左开始遍历,所以大框架根中序遍历较相似,这里使用两个栈来实现,一个主栈保存遍历到的节点,一个辅助栈来保存暂时不输出的“根节点”,一个难点就是输出辅助栈中的根节点时候的判断条件,具体请看代码。该方法将使用两个栈,空间复杂度大一点。

package binaryTree;

import java.util.Stack;
import offer.TreeNode;

/**
 * @author WangPan 
 * @date 2019/4/20 19:33
 * @description 二叉树的后序遍历,利用两个栈,一个主栈一个辅助栈,当两个栈栈顶元素相同时输出,在中序遍历的基础上进行改进
 **/
public class postorder {
    

    public static void post(TreeNode root){
    
        if(root == null)
            return;
        Stack<TreeNode> stack = new Stack<>();
        //stack1用来保存那些暂时不输出的根节点
        Stack<TreeNode> stack1 = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
    
            while (root.left != null){
    
                stack.push(root.left);
                root = root.left;
            }

            TreeNode temp = stack.peek();
            //右节点为null时这个节点可以输出,无论其是左节点还是右节点
            if(temp.right == null){
    
                System.out.println(stack.pop().val + " ");
                //当temp是右节点时候要把根节点也输出,输出的条件是两个栈的栈顶元素相同
                while(!stack1.isEmpty() && stack.peek() == stack1.peek()){
    
                    System.out.print(stack1.pop().val + " ");
                    stack.pop();
                }
            } else {
    
                stack1.push(temp);//根节点要进入stack1
                root = temp.right;
                stack.push(root);
            }
        }
    }

    }
}

思路2:使用一个栈保存节点,当要输出的时候判断其是否满足可输出条件,即为叶子节点或其子节点已输出完毕,使用变量pre来保存前一个输出的节点,具体请看代码。

package binarytree;

import java.util.Stack;
import offer.TreeNode;

/**
 * @author WangPan 
 * @date 2019/4/20 19:33
 * @description 二叉树的后序遍历,非递归版本,利用一个栈,在前序遍历的基础上修改
 **/
public class PostOrder {
    
    //使用一个栈来访问,思路与前序遍历相似,前序遍历时根节点直接输出,这里先判断是该节点的子节点是否输出过,如果输出过或为叶子节点则可以直接输出,否则将其右左子节点一次入栈
    public static void postOneStack(TreeNode root){
    
        if(root == null) {
    
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        stack.push(root);
        while (!stack.isEmpty()){
    
            TreeNode temp = stack.peek();
            if((temp.left == null && temp.right == null) 
            || (pre != null && (pre == temp.left || pre == temp.right))) {
    
                System.out.print(stack.pop().val + " ");
                pre = temp;
            }else {
    
                if(temp.right != null) {
    
                    stack.push(temp.right);
                }
                if(temp.left != null) {
    
                    stack.push(temp.left);
                }
            }
        }
    }
}

总结

循环遍历二叉树的方法可能会在面试中问到,当然也是作为一名程序员应该掌握的东西,希望能对大家有点帮助,如有不当之处还请指出,一起学习,一起进步。我的GitHub主页:WangPanHUST

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/realwongp/article/details/89424703

智能推荐

mysql_install_db is deprecated. Please consider switching to mysqld --initialize_JHC_binge的博客-程序员信息网_please consider switching to mysqld --initialize

解决:需要使用mysqld来初始化./mysqld --initialize --datadir=/usr/local/mysql-cluster/data --user=mysql --basedir=/usr/local/mysql-cluster在安装mysql时遇到以下错误执行./mysqld --initialize 后./bin/mysqld: error wh..._1671465600

数据分析工具汇总_siyuetian1943的博客-程序员信息网_数据库分析工具

这里我把软件分成纵横四个层次的的象限图来表达!<font color="red">第一维度:数据存储层——>数据报表层——>数据分析层——>数据展现层</font><font color="blue">第二维度:用户级——>部门级——>企业级——>BI级</font>

Java中的输入输出语句_chc_1995phd的博客-程序员信息网_java打印输出语句

引入 Scanner类:import java.util.Scanner;(1)创建Scanner类对象;Scanner 标识符=new Scanner(System.in);如:Scanner readData=new Scanner(System.in);(2)调用Scanner类的方法读取数据,方法包括nextInt(),nextByte(),nextShort()等;例

Android4.3模拟器界面中右侧菜单按钮无法使用问题解决办法_赶路人儿的博客-程序员信息网

开发环境:笔记本电脑Windows2008+MyEclipse 10+Android4.3问题描述:运行或者调试Android项目时,发现模拟器中右侧Menu按钮无法点击,截图如下:查看在Android Virtual Devices选项卡中点击new按钮新建的模拟器的属性配置如下:解决办法:应在Device Definitions选项卡中新建模拟器就没问题

Qt网络编程QTcpServer和QTcpSocket的理解_ying_593254979的博客-程序员信息网

前一段时间通过调试Qt源码,大致了解了Qt的事件机制、信号槽机制。毕竟能力和时间有限。有些地方理解的并不是很清楚。开发环境:linux((fedora 17),Qt版本(qt-everywhere-opensource-src-4.7.3)。Qt网络编程比较常用的两个类:QTcpServer和QTcpSocket。当然还有UDP的类(在这就不介绍了)。这两个类的操作比较简单。

TensorRT-5.1.5.0-SSD_知识在于分享的博客-程序员信息网_tensorrt 5.1

文档:https://docs.nvidia.com/deeplearning/sdk/tensorrt-archived/tensorrt-513https://docs.nvidia.com/deeplearning/sdk/tensorrt-api/c_api/index.html安装:https://docs.nvidia.com/deeplearning/sdk/te...

随便推点

RabbitMQ的3种模式_Bee.F的博客-程序员信息网_我们需要将消息一次发给多个队列时,使用rabbitmq哪一种消息模式

直接模式(Direct)我们需要将消息发给唯一一个节点时使用这种模式,这是最简单的一种形式;任何发送到Direct Exchange的消息都会被转发到RouteKey中指定的Queue。一般情况可以使用rabbitMQ自带的Exchange:”"(该Exchange的名字为空字符串,下文称其为default Exchange)。这种模式下不需要将Exchange进行任何绑定(bindi...

泊松分布的前世今生_bitcarmanlee的博客-程序员信息网_泊松是怎么想到泊松分布的

1.初见泊松分布Poisson distribution,翻译成中文名为泊松分布、普阿松分布、帕松分布、布瓦松分布、布阿松分布、波以松分布、卜氏分配等,是概率与统计学中一种常见的离散概率分布,常用来描述单位时间内随机时间发生次数的概率分布。若随机变量XX服从参数为λ\lambda的泊松分布,则可以记为X∼π(X)X \sim \pi(X),或者X∼P(X)X \sim P(X)。其中,参数λ\lam

python 视频播放 拖动_视频画中画效果,拖动进度条可以seek到相应视频帧显示_weixin_39571179的博客-程序员信息网

在视频开发中,我们常常看到这样的效果,拖动进度条时,或是在进度条上方或是在屏幕中间,显示拖动进度条位置时刻的某一帧画面。这个需求,如果是你,你会如何做?通常一个需求,不仅要考虑实现,还有考虑一些是否有性能上影响。下面我想到的4个方案:1、在拖动过程中,可以通过TextureView来显示预览图,拖动进度条到某个position后,通过textureView.getBitmap()拿到对应的截图,用...

使用VS2019发布.Net Core MVC项目并部署到IIS过程+错误解决_Dreamer_Sun2020的博客-程序员信息网_c# vs2019 mvc部署

使用VS2019发布.Net Core MVC项目并部署到IIS过程+错误解决安装IIS和.Net Core运行时安装IIS安装.net core运行时程序以文件形式发布.net core项目这里要说发布的坑IIS上建立网站错误填坑!!安装IIS和.Net Core运行时首先,确保你的电脑已安装IIS,才能进行后续操作,安装过程如下。安装IIS首先打开Windows系统,选择控制面板进入..._1671465600

idea运行时的主类怎么设置_IntelliJ IDEA运行/调试配置_weixin_39825722的博客-程序员信息网

运行/调试配置IntelliJ IDEA 可以使用大量的运行/调试配置。每个运行/调试配置都代表一组命名的运行/调试启动属性。当您使用 IntelliJ IDEA 执行运行、调试或测试操作时,您始终会基于一个现有配置的参数来启动一个进程。IntelliJ IDEA 提供了许多运行/调试配置类型,用于各种运行、调试和测试问题。您可以创建自己的特定类型的运行/调试配置。每个运行/调试配置类型都有自己的...

2020-10-14 python 统计字符个数_Kaqiulee的博客-程序员信息网

#输入一行字符串,分别统计出其中英文字母、空格、数字和其他字符的个数请使用循环结构完成newstr=input("请输入一行字符串:")zimu=0kongge=0shuzi=0qita=0times=0while times&lt;len(newstr): mychar=newstr[times] #定义字符串变量,用来提取newstr中每个字符 times=times+1 if mychar.isalpha(): zimu=zimu+1 e

推荐文章

热门文章

相关标签