二叉树的中序遍历非递归算法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)


相关推荐

  • JBOSS 下载_JbusDriver

    JBOSS 下载_JbusDriver1:JBossApplicationServerDownloadshttp://jbossas.jboss.org/downloads/只下载JBossAS7.1.1.Final ASCertifiedJavaEE6FullProfile 2012-03-09 LGPL [b]Communityparticipationonly[/b]

  • Springboot的jar包和war包的区别

    Springboot的jar包和war包的区别转自: https://blog.csdn.net/qq_32331073/article/details/81544061SpringBoot默认支持很多模板引擎,但是JSP只能够在War中使用,同时mvc.view.prifix/suffix必须主动配置给出,另外必须导入JSP的默认渲染servlet:”org.apache.jasper.servlet.JspServlet”,即添加依赖:…

  • Pokemon GO将在日本发布 网络安全公司呼吁防范虚假软件

    Pokemon GO将在日本发布 网络安全公司呼吁防范虚假软件

  • springcloud版本号

    springcloud版本号因为SpringCloud不同其他独立项目,它拥有很多子项目的大项目。所以它是的版本是版本名+版本号,下面这些都是它的一些版本名:这些Angle,Brixton,Camden等都是伦敦地铁站的名字,他们按照字母顺序发行,就是版本的演进.当一个版本的SpringCloud项目的发布内容积累到临界点或者一个严重bug解决可用后,就会发布一个“servicereleases”版本,简称SR…

  • dreamweaver cs6 html教程,Dreamweaver cs6安装详细图文教程

    dreamweaver cs6 html教程,Dreamweaver cs6安装详细图文教程类型:Mac应用软件大小:314.6M语言:中文评分:10.0标签:立即下载Dreamweaver这款强大的所见即所得的网页编辑器相信大家都有用过,CS6这个新版本增加了对Html5、css及jqurey的支持,还有其他一些功能的增加。不过建议新手是没必要下这个版本的,毕竟这个版本的功能对于刚接触DW的人来说用处不是很大,用CS5足矣。西西为大家制作了Dreamweavercs6的详细安装图文…

  • javascript uint8数组和uint32之间的转换

    javascript uint8数组和uint32之间的转换低位在前,高位在后functionintTobytes(value){vara=newUint8Array(4)a[3]=(value>>24)&0xFFa[2]=(value>>16)&0xFFa[1]=(value>>8)&0xFFa[0]=value

发表回复

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

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