⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 二叉树三种遍历的非递归算法（背诵版）.htm

📁 关于二叉树的相关知识和算法
💻 HTM
字号:
🔍 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0062)http://www.freekaoyan.com/bbs/printpage.asp?BoardID=31&ID=1569 -->
<HTML><HEAD><TITLE>免费考研论坛-[分享]二叉树三种遍历的非递归算法（背诵版）</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2800.1400" name=GENERATOR>
<META 
content=免费,考研,专业课,试卷,公共课,研究生,硕士,考研信息,英语,数学,政治,机械,法律,金融,经济学,MBA,通信,生物,管理,招生,调剂,EMBA,会计,电子 
name=keywords>
<META content=免费考研专业课试卷公共课研究生硕士考研信息英语数学政治机械法律金融经济学MBA通信生物管理招生调剂EMBA会计电子 
name=description><LINK href="二叉树三种遍历的非递归算法（背诵版）.files/css.css" type=text/css 
rel=STYLESHEET><!--论坛页面开始代码-->
<SCRIPT language=JavaScript src="二叉树三种遍历的非递归算法（背诵版）.files/Main.js"></SCRIPT>
</HEAD>
<BODY leftMargin=0 topMargin=0>
<DIV class=menuskin id=popmenu 
onmouseover="clearhidemenu();highlightmenu(event,'on')" style="Z-INDEX: 100" 
onmouseout="highlightmenu(event,'off');dynamichide(event)"></DIV><!--printpage.asp##帖子可打印页面-->
<TABLE style="TABLE-LAYOUT: fixed; WORD-BREAK: break-all" width=980 align=center 
border=0>
  <TBODY>
  <TR>
    <TD vAlign=center 
      align=top><B>以文本方式查看主题</B><BR><BR>-&nbsp;&nbsp;<B>免费考研论坛</B>&nbsp;&nbsp;(http://www.freekaoyan.com/bbs/index.asp)<BR>--&nbsp;&nbsp;<B>计算机工程学院</B>&nbsp;&nbsp;(http://www.freekaoyan.com/bbs/list.asp?boardid=31)<BR>----&nbsp;&nbsp;<B>[分享]二叉树三种遍历的非递归算法（背诵版）</B>&nbsp;&nbsp;(http://www.freekaoyan.com/bbs/dispbbs.asp?boardid=31&amp;id=1569)<BR>
      <HR>
    </TD></TR><!--printpage.asp##{$bbslist}循环部分-->
  <TR>
    <TD vAlign=center 
      align=top>--&nbsp;&nbsp;作者：duoduo0246<BR>--&nbsp;&nbsp;发布时间：2005-3-21 
      16:36:00<BR><BR>--&nbsp;&nbsp;[分享]二叉树三种遍历的非递归算法（背诵版）<BR><BR><BR>
      <P>二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法，直接用于考研答题。<BR><BR>1.先序遍历非递归算法<BR>#define 
      maxsize 100<BR>typedef struct<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;Bitree 
      Elem[maxsize];<BR>&nbsp;&nbsp;&nbsp;&nbsp;int 
      top;<BR>}SqStack;<BR><BR>void PreOrderUnrec(Bitree 
      t)<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;SqStack 
      s;<BR>&nbsp;&nbsp;&nbsp;&nbsp;StackInit(s);<BR>&nbsp;&nbsp;&nbsp;&nbsp;p=t;<BR>&nbsp;&nbsp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;while 
      (p!=null || 
      !StackEmpty(s))<BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while 
      (p!=null)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
      //遍历左子树<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;visite(p-&gt;data);<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;push(s,p);<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p=p-&gt;lchild;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
      <BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}//endwhile<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if 
      (!StackEmpty(s))&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
      //通过下一次循环中的内嵌while实现右子树遍历<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p=pop(s);<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p=p-&gt;rchild;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}//endif<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;}//endwhile 
      <BR>&nbsp;&nbsp;&nbsp;&nbsp;<BR>}//PreOrderUnrec<BR><BR>2.中序遍历非递归算法<BR>#define 
      maxsize 100<BR>typedef struct<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;Bitree 
      Elem[maxsize];<BR>&nbsp;&nbsp;&nbsp;&nbsp;int 
      top;<BR>}SqStack;<BR><BR>void InOrderUnrec(Bitree 
      t)<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;SqStack 
      s;<BR>&nbsp;&nbsp;&nbsp;&nbsp;StackInit(s);<BR>&nbsp;&nbsp;&nbsp;&nbsp;p=t;<BR>&nbsp;&nbsp;&nbsp;&nbsp;while 
      (p!=null || 
      !StackEmpty(s))<BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while 
      (p!=null)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
      //遍历左子树<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;push(s,p);<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p=p-&gt;lchild;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}//endwhile<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if 
      (!StackEmpty(s))<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p=pop(s);<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;visite(p-&gt;data);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//访问根结点<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p=p-&gt;rchild;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//通过下一次循环实现右子树遍历<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}//endif&nbsp;&nbsp; 
      <BR>&nbsp;&nbsp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;}//endwhile<BR><BR>}//InOrderUnrec<BR><BR><BR>3.后序遍历非递归算法<BR>#define 
      maxsize 100<BR>typedef enum{L,R} tagtype;<BR>typedef struct 
      <BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;Bitree 
      ptr;<BR>&nbsp;&nbsp;&nbsp;&nbsp;tagtype tag;<BR>}stacknode;<BR><BR>typedef 
      struct<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;stacknode 
      Elem[maxsize];<BR>&nbsp;&nbsp;&nbsp;&nbsp;int 
      top;<BR>}SqStack;<BR><BR>void PostOrderUnrec(Bitree 
      t)<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;SqStack 
      s;<BR>&nbsp;&nbsp;&nbsp;&nbsp;stacknode 
      x;<BR>&nbsp;&nbsp;&nbsp;&nbsp;StackInit(s);<BR>&nbsp;&nbsp;&nbsp;&nbsp;p=t;<BR>&nbsp;&nbsp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;do 
      <BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while 
      (p!=null)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//遍历左子树<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x.ptr 
      = p; 
      <BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x.tag 
      = L;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
      //标记为左子树<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;push(s,x);<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p=p-&gt;lchild;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while 
      (!StackEmpty(s) &amp;&amp; 
      s.Elem[s.top].tag==R)&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x 
      = 
      pop(s);<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p 
      = 
      x.ptr;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;visite(p-&gt;data);&nbsp;&nbsp; 
      //tag为R，表示右子树访问完毕，故访问根结点&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
      <BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if 
      (!StackEmpty(s))<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s.Elem[s.top].tag 
      =R;&nbsp;&nbsp;&nbsp;&nbsp; 
      //遍历右子树<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p=s.Elem[s.top].ptr-&gt;rchild;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;}while 
      (!StackEmpty(s));<BR>}//PostOrderUnrec</P><BR>
      <DIV align=right><FONT color=#000066>[此贴子已经被作者于2005-3-24 
      21:32:02编辑过]</FONT></DIV>
      <HR>
    </TD></TR><!--printpage.asp##{$bbslist}循环部分-->
  <TR>
    <TD vAlign=center 
      align=top>--&nbsp;&nbsp;作者：doublefish<BR>--&nbsp;&nbsp;发布时间：2005-4-27 
      15:54:00<BR><BR>--&nbsp;&nbsp;<BR>那我就照着背吧~~~ 
      <HR>
    </TD></TR><!--printpage.asp##{$bbslist}循环部分-->
  <TR>
    <TD vAlign=center 
      align=top>--&nbsp;&nbsp;作者：fanbe<BR>--&nbsp;&nbsp;发布时间：2005-5-8 
      18:10:00<BR><BR>--&nbsp;&nbsp;<BR>真有这么重要吗？？？？？？？？ 
      <HR>
    </TD></TR><!--printpage.asp##{$bbslist}循环部分-->
  <TR>
    <TD vAlign=center 
      align=top>--&nbsp;&nbsp;作者：iostream06<BR>--&nbsp;&nbsp;发布时间：2005-5-8 
      19:33:00<BR><BR>--&nbsp;&nbsp;<BR>
      <DIV class=quote><B>以下是引用<I>fanbe</I>在2005-5-8 
      18:10:00的发言：</B><BR>真有这么重要吗？？？？？？？？</DIV>
      <P>
      <P>树的非递归遍历当然很重要！许多教材上有提及，但可惜都是用伪码描述，我想用不着背的，编者之所以没给标准代码，可能就是鼓励读者自己写写，而且平时写程序时多用几次就搞定的了。也算是写程序的乐趣吧~~对这种重点内容当然应该是“据为己有”啦，不然考上研读着也是一种灾难。&nbsp;&nbsp; 
      纯属个人意见，井底之谈，大家大可以一笑置之。</P>
      <HR>
    </TD></TR><!--printpage.asp##{$bbslist}循环部分-->
  <TR>
    <TD vAlign=center 
      align=top>--&nbsp;&nbsp;作者：yakumo126<BR>--&nbsp;&nbsp;发布时间：2005-5-10 
      17:43:00<BR><BR>--&nbsp;&nbsp;<BR>感觉明白原理之后，并不是很难！ 
      <HR>
    </TD></TR><!--printpage.asp##{$bbslist}循环部分-->
  <TR>
    <TD vAlign=center 
      align=top>--&nbsp;&nbsp;作者：bingo<BR>--&nbsp;&nbsp;发布时间：2005-5-11 
      21:21:00<BR><BR>--&nbsp;&nbsp;<BR>
      <P>理解就好</P>
      <HR>
    </TD></TR><!--printpage.asp##{$bbslist}循环部分-->
  <TR>
    <TD vAlign=center 
      align=top>--&nbsp;&nbsp;作者：zbky2006<BR>--&nbsp;&nbsp;发布时间：2005-6-2 
      7:54:00<BR><BR>--&nbsp;&nbsp;<BR>
      <P>还是理解吧</P>
      <HR>
    </TD></TR></TBODY></TABLE><!--页面结束部分-->
<TABLE cellSpacing=0 cellPadding=0 width=980 align=center border=0>
  <TBODY>
  <TR>
    <TD style="FONT-SIZE: 11px; FONT-FAMILY: Tahoma, Arial" 
      align=middle><BR>我为人人《《==》》人人为我<BR><BR>Powered by <B>Dvbbs!</B> <B 
      style="COLOR: #ff9900">6.0.0RC4</B>&nbsp; &copy; 2001-2005 Aspsky Technology 
      Ltd<BR>------------------------------------------------------------------------------<BR>本论坛属viewsnake个人论坛,仅供纯学习和情感交流!<BR><FONT 
      color=red>拒绝任何人以任何形式在本论坛发表与中华人民共和国法律相抵触的言论!</FONT><BR>管理邮箱 
      Freekaoyan@gmail.com 目前启用QQ:30310576, 其它号码非本viewsnake.<BR><BR><A 
      href="http://www.miibeian.gov.cn/" 
    target=_blank>苏ICP备05011575号</A><BR><BR></TD></TR></TBODY></TABLE>
<CENTER>
<SCRIPT src="二叉树三种遍历的非递归算法（背诵版）.files/click.aspx"></SCRIPT>
</CENTER></BODY></HTML>

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -