ds6.3.1.htm

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

</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-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"><font size="5" color="#FFFFFF" face="宋体"><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 color="#FFFFFF" face="宋体"><b><font size="5">A   
B D G C E F</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>
<p class="MsoNormal" style="margin-left:21.0pt"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF" face="宋体"><b><font size="5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</font></b></font></span></span></p>
<!--mstheme--></font>
<h5><!--mstheme--><font face="宋体" color="#6666FF"><font size="5" color="#FFFFFF" face="宋体"><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><span style="mso-spacerun: yes">&nbsp;</span>2．中序遍历（LDR）<o:p>
</o:p>  
</span></b></font><!--mstheme--></font></h5>
<!--mstheme--><font face="宋体">
<p class="MsoNormal" style="margin-left:21.0pt"><font size="5" color="#FFFFFF" face="宋体"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">&nbsp;   
中序遍历的递归过程为：若二叉树为空，遍历结束。否则，</span></b></font></p>
<p class="MsoNormal" style="margin-left:21.0pt"><font size="5" color="#FFFFFF" face="宋体"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">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:21.0pt"><font size="5" color="#FFFFFF" face="宋体"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">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" color="#FFFFFF" face="宋体"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">3</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" color="#FFFFFF" face="宋体"><b><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; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF" face="宋体"><b><font size="5">void   
InOrder</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"> </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">*/</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">InOrder</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">*/</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">Visite</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;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;   
</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">*/<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">InOrder</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></font></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.6<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 face="宋体"><font color="#FFFFFF"><b><font size="5"><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 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></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">D   
G B A E C F</font></b></font></span></p>  
<p class="MsoNormal" align="center"><span lang="EN-US"><span style="mso-spacerun:
yes"><font color="#FFFFFF" face="宋体"><b><font size="5">&nbsp; </font></b></font></span></span><img border="0" src="ds6.3.2.gif" width="254" height="209" align="middle"><span style="mso-spacerun:  
yes" lang="EN-US"><font color="#FFFFFF" face="宋体"><b><font size="5">&nbsp;</font></b></font></span><span lang="EN-US"><span style="mso-spacerun:
yes"><font color="#FFFFFF" face="宋体"><b><font size="5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</font></b></font></span></span></p>
<!--mstheme--></font>
<h5><!--mstheme--><font face="宋体" color="#6666FF"><font size="5" color="#FFFFFF" face="宋体"><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><span style="mso-spacerun: yes">&nbsp;</span>3．后序遍历（LRD）<o:p>
</o:p>  
</span></b></font><!--mstheme--></font></h5>
<!--mstheme--><font face="宋体">
<p class="MsoNormal" style="margin-left:21.0pt"><font size="5" color="#FFFFFF" face="宋体"><b><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" color="#FFFFFF" face="宋体"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">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:21.0pt"><font size="5" color="#FFFFFF" face="宋体"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">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" color="#FFFFFF" face="宋体"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">（</span><span lang="EN-US">3</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" color="#FFFFFF" face="宋体"><b><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">后序遍历二叉树的递归算法如下：</span></b></font></p>