ds6.3.1.htm

这是清华大学所用的数据结构的电子版教材

<p class="MsoNormal" style="margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF" face="宋体"><b><font size="5">void   
PostOrder</font></b></font></span><font color="#FFFFFF" face="宋体"><b><font size="5"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">BiTree   
bt</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）</span></font></b></font></p>
<p class="MsoNormal" style="margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF" face="宋体"><b><font size="5">{</font></b></font></span><font color="#FFFFFF" face="宋体"><b><font size="5"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">后序遍历二叉树</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">bt*/<o:p>
</o:p>  
</span></font></b></font></p>
<p class="MsoNormal" style="margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF" face="宋体"><b><font size="5">&nbsp;</font></b></font></span><font color="#FFFFFF" face="宋体"><b><font size="5">if   
(bt==NULL) return;<span style="mso-spacerun: yes">&nbsp; </span></font></b></font></span><font color="#FFFFFF" face="宋体"><b><font size="5"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">递归调用的结束条件</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/<o:p>  
</o:p>  
</span></font></b></font></p>
<p class="MsoNormal" style="margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF" face="宋体"><b><font size="5">&nbsp;</font></b></font></span><font color="#FFFFFF" face="宋体"><b><font size="5">PostOrder</font></b></font></span><font color="#FFFFFF" face="宋体"><b><font size="5"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">bt-&gt;lchild</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">)</span><span lang="EN-US">;</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">后序递归遍历</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">bt</span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">的左子树</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/<o:p>
</o:p>  
</span></font></b></font></p>
<p class="MsoNormal" style="margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF" face="宋体"><b><font size="5">&nbsp;</font></b></font></span><font color="#FFFFFF" face="宋体"><b><font size="5">PostOrder</font></b></font></span><font color="#FFFFFF" face="宋体"><b><font size="5"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">bt-&gt;rchild</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">)</span><span lang="EN-US">;</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">后序递归遍历</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">bt</span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">的右子树</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/<span style="mso-spacerun: yes">&nbsp;</span></span></font></b></font><font size="5" color="#FFFFFF" face="宋体"><b><span lang="EN-US">Visite</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">bt-&gt;data</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）</span><span lang="EN-US">;<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;   
</span></span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">访问结点的数据域</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/</span></b></font></p>
<p class="MsoNormal" style="margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF" face="宋体"><b>}</b></font></span></p>
<p class="MsoNormal" align="center" style="text-align:center;text-indent:21.0pt"><font size="5" color="#FFFFFF" face="宋体"><b><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">算法</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"> 
6.7<o:p>  
</o:p>  
</span></b></font></p>
<p class="MsoNormal" style="margin-left:21.0pt"><span lang="EN-US"><font size="5" color="#FFFFFF" face="宋体"><b>&nbsp;<o:p>
</o:p>  
</b></font></span></p>
<p class="MsoNormal" style="margin-left:21.0pt"><font color="#FFFFFF" face="宋体"><b><font size="5"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">&nbsp;对于图</span><span style="mso-hansi-font-family: Times New Roman">图<span lang="EN-US">6.3(b)</span></span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">所示的二叉树，按先序遍历所得到的结点序列为：</span></font></b></font></p>
<p class="MsoNormal" style="margin-left:21.0pt"><span lang="EN-US"><font size="5" color="#FFFFFF" face="宋体"><b>&nbsp;&nbsp;  
</b></font><font color="#FFFFFF" face="宋体"><b><font size="5">G   
D B E F C A</font></b></font></span></p>  
<p class="MsoNormal" style="margin-left:21.0pt" align="center"><img border="0" src="ds6.3.2.gif" width="254" height="209"></p>
<!--mstheme--></font>
<h5><!--mstheme--><font face="宋体" color="#6666FF"><font size="5" face="宋体" color="#FFFFFF"><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; mso-fareast-font-family: 黑体"><span style="mso-spacerun: yes">&nbsp;</span>4</span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman">．层次遍历</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; mso-fareast-font-family: 黑体"><o:p>
</o:p>
</span></b></font><!--mstheme--></font></h5>
<!--mstheme--><font face="宋体">
<p class="MsoNormal"><font size="5" face="宋体" color="#FFFFFF"><b><span style="mso-spacerun: yes" lang="EN-US">&nbsp;&nbsp;&nbsp;   
</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。对于下</span><span style="mso-hansi-font-family: Times New Roman">图</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">所示的二叉树，按层次遍历所得到的结果序列为：</span></b></font></p>
<p class="MsoNormal"><font size="5" face="宋体" color="#FFFFFF"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">&nbsp;&nbsp;  
</span></b></font><span lang="EN-US"><font size="5" face="宋体" color="#FFFFFF"><b>A   
B C D E F G<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span></b></font></span></p>  
<p class="MsoNormal" style="margin-left:21.0pt" align="center"><img border="0" src="ds6.3.2.gif" width="254" height="209"></p>
<p class="MsoNormal" style="margin-left:21.0pt" align="left"><font size="5" face="宋体" color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><b>下面讨论层次遍历的算法。</b></span></font></p>
<p class="MsoNormal"><font size="5" face="宋体" color="#FFFFFF"><b><span style="mso-spacerun: yes" lang="EN-US">&nbsp;&nbsp;&nbsp;   
</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">由层次遍历的定义可以推知，在进行层次遍历时，对一层结点访问完后，再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇到的结点先访问，这与队列的操作原则比较吻合。因此，在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个操作：</span></b></font></p>
<p class="MsoNormal" style="margin-left:47.25pt;text-indent:-26.25pt;mso-list:
l37 level1 lfo19;tab-stops:list 47.25pt"><font size="5" face="宋体" color="#FFFFFF"><b><span lang="EN-US" style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（1）</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">访问该元素所指结点；</span></b></font></p>
<p class="MsoNormal" style="margin-left:47.25pt;text-indent:-26.25pt;mso-list:
l37 level1 lfo19;tab-stops:list 47.25pt"><font size="5" face="宋体" color="#FFFFFF"><b><span lang="EN-US" style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（2）</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。</span></b></font></p>
<p class="MsoNormal" style="margin-left:21.0pt"><font size="5" face="宋体" color="#FFFFFF"><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><b>此过程不断进行，当队列为空时，二叉树的层次遍历结束。</b></span></font></p>
<p class="MsoNormal"><font size="5" face="宋体" color="#FFFFFF"><b><span style="mso-spacerun: yes" lang="EN-US">&nbsp;   
</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">在下面的层次遍历算法中，二叉树以二叉链表存放，一维数组</span><span lang="EN-US">Queue[MAXNODE]</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">用以实现队列，变量</span><span lang="EN-US">front</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">和</span><span lang="EN-US">rear</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">分别表示当前对首元素和队尾元素在数组中的位置。</span></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font size="5" face="宋体" color="#FFFFFF"><b><span lang="EN-US">void   
LevelOrder</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">BiTree   
bt</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">）</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">层次遍历二叉树</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">bt*/<o:p>
</o:p>  
</span></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><b><font size="5" face="宋体" color="#FFFFFF">{ 
BiTree Queue[MAXNODE];</font></b></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><b><font size="5" face="宋体" color="#FFFFFF">&nbsp;   
</font></b></span><b><font size="5" face="宋体" color="#FFFFFF">int front,rear;</font></b></span></p>  
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><b><font size="5" face="宋体" color="#FFFFFF">&nbsp;   
</font></b></span><b><font size="5" face="宋体" color="#FFFFFF">if (bt==NULL)   
return;</font></b></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><b><font size="5" face="宋体" color="#FFFFFF">&nbsp;   
</font></b></span><b><font size="5" face="宋体" color="#FFFFFF">front=-1;</font></b><b><font size="5" face="宋体" color="#FFFFFF">rear=0;</font></b></span></p>