二叉树前序遍历 迭代_二叉树的前序中序后序遍历算法

二叉树前序遍历 迭代_二叉树的前序中序后序遍历算法二叉树的前序遍历对于一颗二叉树,当遍历它的时候使用递归总是轻而易举的。这是二叉树前序遍历-使用递归publicvoidpreorderTraversal(TreeNoderoot){if(root==null)return;System.out.print(root.data+””);preorde…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

二叉树的前序遍历
对于一颗二叉树,当遍历它的时候使用
递归总是轻而易举的。
这是二叉树前序遍历-使用递归
public void preorderTraversal(TreeNode root){ 
   
        if(root==null)
            return;
        System.out.print(root.data+" ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }
1.简单几行代码就可以将一颗二叉树遍历完
	但是递归其中的运算是如何的,我们不需
	要知道,计算机会用函数栈自己解决,
	初学递归时,会陷入一种困境,我们总是
	想钻进递归方法里把每一步都缕清,事实上
	人脑是不可能把每一步的结果都想出来的,
	就算写在纸上也无法思考清楚。当然,
	我们也不需要去钻今递归代码里,我们只
	需要明白递归用来干什么就行。
	
2.在二叉树的前序遍历中,我们知道前序遍历
	是先打印根结点,再打印左子树,然后打印
	右子树。对于树中的每一个结点都符号这个
	要求,我们不需要关心左子树还有左子树,
	左子树还有右子树,右子树还有右子树等等
	无穷无尽的问题
	因为每一个结点都必须遵守这样的规定,
	同样,我们也无需过分关心结点为空怎么办
	空结点的处理应该是细节问题,它不影响
	前序遍历的规定,放过细节,关心策略。
二叉树和前序遍历-迭代
1.那么当不用递归处理,改用循环迭代
	进行前序遍历,我们该怎么做呢?
	
2.我们应该关心每一个结点是否应该被
打印输出?关心它的下一个结点该打印哪一个?
	关心当处理到空结点时候怎么办吗?
	这些问题都不是我们初步要考虑的,可能
	会有细节问题,不过细节在代码完善时候再
	考虑也不迟
	
3.我们只需要明白策略即可。对于二叉树前序
	遍历,我们知道它的遍历规则,那么我们定义
	一个	策略【root】

在这里插入图片描述

1.我们把二叉树分成三个部分,root结点表示需要当前
  要打印的的结点,T1表示左子树,T2表示右子树
2.我们不用知道T1或者T2树里面是如何按序打印值的,
  从总体上看我们只要先打印root,再打印左子树,然后
  右子树就行了。
3. 策略【root】:表示的就是这种规则,先打印root,再
  打印T1,再打印T2。它对于每一个结点都适用这种策略
4. 那我们可以轻而易举地写出这种伪代码
	while(root){ 
   
		//打印本结点
		System.out.print(root.data+" ");
		
		if(T1){ 
   
            打印T1
         }
        if(T2){ 
   
            打印T2
         }
	}
分析:
1. 每一颗右子树T2都比左子树T1晚打印,
  我们使用Stack栈来先存放T2树,再存放
  T1树,这样从整体上看T1树在栈顶将会先
  释放。
	while(root){ 
   
		//打印本结点
		System.out.print(root.data+" ");
		
		if(root.right!=null){ 
   
            stack.push(root.right);
        }

        if(root.left!=null){ 
   
            stack.push(root.left);
        }
	}
这样我们的思维就出来了,先打印root结点,有右子
结点就压入栈,先处理左子结点

总体思维有了后,我们处理细节部分,
1. while循环是会接受一个root结点,表示要处理的树的
  根结点,那么root!=null是while的入口条件,同样如果
  root结点下没有子结点,也就是说Stack栈没有存放子树
  那么也就说明栈为空代表无子树迭代结束,!stack.isEmpty()
  也是while的入口条件

2. 每一次进入循环的root是如何确定的?
  我们知道当第一个root结点进入循环,打印它,并把它的
  右子树,左子树压入栈

在这里插入图片描述

2.当root.left和root.right入栈操作完成后,无论是否
 都入栈(也许为空),我们的root都应该指向栈顶结点
 因为下一次循环进入的root就应该是栈顶结点

3. 因为循环体内我们使用的是直接System.out结点
 这样造成栈顶元素无法释放,所以打印完结点后,
 直接释放栈顶元素
代码
public void preorderTraversal(TreeNode root,Stack<TreeNode> stack){ 
   
        
        while(!stack.isEmpty() || root!=null){ 
   
            System.out.print(root.data+" ");
            if(!stack.isEmpty()){ 
   
                stack.pop();
            }
            if(root.right!=null){ 
   
                stack.push(root.right);
            }

            if(root.left!=null){ 
   
                stack.push(root.left);
            }
            root = stack.isEmpty() ? null : stack.peek();
        }

    }
总结
使用迭代对二叉树进行前序遍历,它的遍历策略不难理解,
但是循环的入口,出口并不是那么容易控制,迭代代码并
不难理解,但是很容易形成“一看就懂,一写就废”

这篇对于迭代的理解帮助我们学习二叉树遍历时如何处理,
代码是数不尽样式的,但自己的思想却只有自己知道。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/195261.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Landsat 9 数据详细介绍

    Landsat 9 数据详细介绍1.基本情况Landsat9号是Landsat系列中最新的一颗卫星,计划于2020年12月在加利福利亚范登堡空军基地加利福尼亚由AtlasV401火箭搭载进行发射,实际于于2021年9月27日发射,并已经开始采集第一批数据,2021年10月31日获取到遥感数据。Landsat9是继续Landsat系列对地球表面观测不可替代的记录。为了减少建造时间和观测缺口的风险,Landsat9在很大程度上复制了它的前身Landsat8。来源:原文链接…

  • fastjson List String JSONArray 转换

    fastjson List String JSONArray 转换imgCode//ListList<Course>courseTable=newLinkedList<>();courseTable.add(newCourse(“1″,”Java”,30,3.0));courseTable.add(newCourse(“2″,”JavaScript”,25,2.5));System.out.pri…

  • 利用python、tensorflow、opencv实现人脸识别(包会)!「建议收藏」

    利用python、tensorflow、opencv实现人脸识别(包会)!「建议收藏」 一,前言本人是机械专业在读硕士,在完成暑假实践的时候接触到了人脸识别,对这一实现很感兴趣,所以花了大概十天时间做出了自己的人脸识别。这篇文章应该是很详细的了所以帮你实现人脸识别应该没什么问题。先说本博文的最终要达到的效果:通过一系列操作,在摄像头的视频流中识别特定人的人脸,并且予以标记。本人通过网上资料的查询发现这类人脸识别,大多参考了一位日本程序员小哥的文章。链接:http…

    2022年10月25日
  • WinRAR 6.0 永久去除广告

    WinRAR 6.0 永久去除广告风吹起了从前,看着天边似在眼前,万般流连~

  • git 回滚到指定版本_git回滚多了怎么办

    git 回滚到指定版本_git回滚多了怎么办我们在GIT操作项目时,往往会遇到很多需要回滚的代码。我们可以回滚到任意之前的版本,case如下:1.首先找到你需要回滚的版本号,可以通过日志查看命令行:gitlog-32.选择上图红色箭头执行的commit版本号,第一个时最后提交的,我们回滚到第二个commit:f3eb8f9df34dc6ba47e477e05c8772a62d653fbb命令行:gitr

    2022年10月25日
  • 学习使用口令激活成功教程工具:hashcat、LC、SamInside

    学习使用口令激活成功教程工具:hashcat、LC、SamInside在学习使用口令激活成功教程工具之前,我们要先创建一个用户账号,原理是利用其哈希值进行激活成功教程。很关键的一点是,要在虚拟机里面创建用户!!!很关键的一点是,要在虚拟机里面创建用户!!!很关键的一点是,要在虚拟机里面创建用户!!!重要的事情一定要说三遍。在宿主机(我是win10系统)创建用户获取的hash值是假的,根本无法用于激活成功教程。我个人猜测,是由于宿主机存在某种保护机制,使得不让获取到真正的hash。因…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号