二叉树的中序遍历非递归算法java_二叉树遍历例题解析

二叉树的中序遍历非递归算法java_二叉树遍历例题解析*非递归算法思想:  (1)设置一个栈S存放所经过的根结点(指针)信息;初始化S; (2)第一次访问到根结点并不访问,而是入栈;  (3)中序遍历它的左子树,左子树遍历结束后,第二次遇到根结点,就将根结点(指针)退栈,并且访问根结点;然后中序遍历它的右子树。 (4)当需要退栈时,如果栈为空则结束。     代码实现:void…

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

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

*非递归算法思想:

   (1)设置一个栈S存放所经过的根结点(指针)信息;初始化S;

  (2)第一次访问到根结点并不访问,而是入栈;

   (3)中序遍历它的左子树,左子树遍历结束后,第二次遇到根结点,就将根结点(指针)退栈,并且访问根结点;然后中序遍历它的右子树。

  (4) 当需要退栈时,如果栈为空则结束。

 

二叉树的中序遍历非递归算法java_二叉树遍历例题解析

 

二叉树的中序遍历非递归算法java_二叉树遍历例题解析

 

二叉树的中序遍历非递归算法java_二叉树遍历例题解析

 

二叉树的中序遍历非递归算法java_二叉树遍历例题解析

 

代码实现:

void Midorder(struct BiTNode *t)      //t为根指针 
{ struct BiTNode *st[maxleng];//定义指针栈
  int top=0;                  //置空栈
  do{            
    while(t)               //根指针t表示的为非空二叉树 
    { if (top==maxleng) exit(OVERFLOW);//栈已满,退出
      st[top++]=t;             //根指针进栈
      t=t->lchild;             //t移向左子树
     }   //循环结束表示以栈顶元素的指向为根结点的二叉树
         //的左子树遍历结束
    if (top)                    //为非空栈   
    { t=st[--top];             //弹出根指针
      printf("%c",t->data);    //访问根结点
      t=t->rchild;             //遍历右子树
     }
   } while(top||t); //父结点未访问,或右子树未遍历
 }

 

 

依照同样的思维,写的先序遍历非递归模式

void Preorder(struct BiTNode * t){
  struct BiTNode * St[MaxSize], *p;
  int top = 0; 			//置空栈
  if (t! = NULL){
	  St[top++] = t;
    while(top){
	   p = St[--top]; printf("%c ", p->data);
	   if(p->rchild != NULL)
	      St[top++] = p->rchild;
	   if(p->lchild != NULL)
	      St[top++] = p->lchild;
    }
    printf("\n");
  }
}

 

后序遍历

void Postorder(struct BiTNode * t){
  struct BiTNode * St[MaxSize], *pre;
  int flag, top = 0;
  if (t != NULL){
	  do{
		 while(t != NULL){
		   St[top++] = t; t = t->lchild;
        }
		 pre = NULL; flag = 1;
		 while(top && flag){
          t = St[top-1];
		   if(t->rchild == pre){
		   	printf(“%c ”, t->data); top--;  pre = t;
		   }
		   else{ t=t->rchild; flag = 0;}
	     }
	   }while(top);
	  printf(“\n”); 
	}
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)
blank

相关推荐

  • isset,empty,is_null小知识

    isset,empty,is_null小知识

  • Matlab画图 线条的颜色、宽度等相关设置

    Matlab画图 线条的颜色、宽度等相关设置线条的属性有:Color——颜色、LineWidth——线条宽度、LineStyle——线型、LineJoin——线条边角的样式、AlignVertexCenters——锐化垂直线和水平线线条属性的默认值为([0,0,0],’-‘,’0.5′,’round’,’off’)颜色、线型、一、线条颜色二、线条宽度线条宽度的默认值为0.5,线条宽度只能指定正值。三、线条类型实例:plot(t…

  • Centos7配置MySQL读写分离[通俗易懂]

    Centos7配置MySQL读写分离[通俗易懂]背景82和83两台Mysql已经实现了主从复制。即将使用mysql-proxy进行读写分离,配置192为proxy,写82读83。mysql-proxymysql-proxy是一个处于客户端和服务器之间的中间件,它可以检测,分析或改变它们的通信。简单说就是一个中间层代理,一个连接池,负责将前台应用的连接请求转发给后台的数据库,并且通过lua脚本,可以实现复杂的连接控制和过滤,从而实现读写分离和负载…

  • Spark Streaming Join

    Spark Streaming Join多数据源Join思路多数据源Join大致有以下三种思路:数据源端Join,如Android/IOS客户端在上报用户行为数据时就获取并带上用户基础信息。计算引擎上Join,如用SparkStreaming、Flink做Join。结果端Join,如用HBase/ES做Join,Join键做Rowkey/_id,各字段分别写入列簇、列或field。三种思路各有优劣,使用时注意…

  • 使用python进行方差分析_python多因素方差分析

    使用python进行方差分析_python多因素方差分析利用python实现方差分析简介 方差分析是一种常用的对数据进行分析的方法,用于两个及两个以上样本均数和方差差别的显著性检验。本文介绍单因素方差分析和双因素方差分析。 方差分析存在三个假设: 1、各样本总体服从正态分布。 2、各样本总体方差一样。 3、各样本总体相互独立。单因素方差分析 单因素方差分析就是在只有一种影响因素下判断各个样本间的均值差别的显著性。 数据会…

    2022年10月15日
  • pycharm2021专业版激活码【最新永久激活】

    (pycharm2021专业版激活码)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~1STL…

发表回复

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

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