ds6.3.2.htm

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

上述过程是一个递归过程，其递归算法的思想是：先根据先序序列的第一个元素建立根结点；然后在中序序列中找到该元素，确定根结点的左、右子树的中序序列；再在先序序列中确定左、右子树的先序序列；最后由左子树的先序序列与中序序列建立左子树，由右子树的先序序列与中序序列建立右子树。</b></font></span></p>
<p class="MsoNormal" style="text-indent:21.0pt"><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">下面给出用</span><span lang="EN-US">C</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">语言描述的该算法。假设二叉树的先序序列和中序序列分别存放在一维数组</span><span lang="EN-US">preod[ 
]</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">与</span><span lang="EN-US">inod[ 
]</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">中，并假设二叉树各结点的数据值均不相同。</span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><b><font color="#FFFFFF" size="4"><span lang="EN-US">void 
ReBiTree</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">（</span><span lang="EN-US">char preod[],char 
inod[],int n,BiTree root</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">）</span></font></b></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font size="5" color="#FFFFFF">/*</font></span><font color="#FFFFFF" size="4"><span style="mso-bidi-font-size: 10.0pt"><span lang="EN-US">n</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; 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">root</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; 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></font><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font size="5" color="#FFFFFF"><o:p>
</o:p>
</font></span></b></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span lang="EN-US">{ 
if (n</span><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">≤</span><span lang="EN-US">0) 
root=NULL;</span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><b><font size="5" color="#FFFFFF">&nbsp; 
</font></b></span><b><font size="5" color="#FFFFFF">else 
PreInOd(preod,inod,1,n,1,n,&amp;root);</font></b></span></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>}</b></font></span></p>
<p class="MsoNormal" align="center" style="text-align:center;text-indent:21.0pt"><font size="5" color="#FFFFFF"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; 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.11<o:p>
</o:p>
</span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF" size="4">void 
PreInOd</font></span><b><font color="#FFFFFF" size="4"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">（</span><span lang="EN-US">char preod[],char 
inod[],int i,j,k,h,BiTree *t</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">）</span></font></b></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>{*t=(BiTNode 
*)malloc(sizeof(BiTNode));</b></font></span></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><b><font size="5" color="#FFFFFF">&nbsp;</font></b></span><b><font size="5" color="#FFFFFF">*t-&gt;data=preod[i];</font></b></span></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><b><font size="5" color="#FFFFFF">&nbsp;</font></b></span><b><font size="5" color="#FFFFFF">m=k;</font></b></span></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><b><font size="5" color="#FFFFFF">&nbsp;</font></b></span><b><font size="5" color="#FFFFFF">while 
(inod[m]</font></b></span><b><font size="5" color="#FFFFFF"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">!=</span><span lang="EN-US">preod[i])<span style="mso-spacerun: yes">&nbsp; 
</span>m++;</span></font></b></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><b><font size="5" color="#FFFFFF">&nbsp;</font></b></span><b><font size="5" color="#FFFFFF">if 
(m==k) *t-&gt;lchild=NULL</font></b></span></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><b><font size="5" color="#FFFFFF">&nbsp;</font></b></span><font size="5" color="#FFFFFF"><b>else 
</b>PreInOd(preod,inod,i+1,i+m-k,k,m-1,&amp;t-&gt;lchild);</font></span></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><b><font size="5" color="#FFFFFF">&nbsp;</font></b></span><b><font size="5" color="#FFFFFF">if 
(m==h) *t-&gt;rchild=NULL</font></b></span></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><b><font size="5" color="#FFFFFF">&nbsp;</font></b></span><font size="5" color="#FFFFFF"><b>else 
</b>PreInOd<b>(</b>preod,inod,i+m-k+1,j,m+1,h,&amp;t-&gt;rchild)<b>;</b></font></span></p>
<p class="MsoNormal" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>}</b></font></span></p>
<p class="MsoNormal" align="center" style="text-indent: 0; margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; 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.12</span></b></font><span lang="EN-US"><font size="5" color="#FFFFFF"><b>&nbsp;<o:p>
</o:p>
</b></font></span></p>
<font size="5" color="#FFFFFF"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">&nbsp; 
需要说明的是，数组</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">preod</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">和</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">inod</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">的元素类型可根据实际需要来设定，这里设为字符型。另外，如果只知道二叉树的先序序列和后序序列，则不能唯一地确定一棵二叉树。</span></b></font>
<p align="left">　</p>
<p align="center"><b><a href="ds6.3.HTM"><font size="5" color="#FFFF00">返回</font></a></b></p>

<!--mstheme--></font>

</body>

</html>