📄 ds6.3.3.2.htm
字号:
<p class="MsoNormal" style="text-indent: 21.0pt; margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b> </b></font><font color="#FFFFFF"><b><font size="5">
post=post->rchild;</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 21.0pt; margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">post=post->rchild;</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 21.0pt; margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">}</font></b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">return(post);</font></b></font></span></p>
<p class="MsoNormal" style="margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>}</b></font></span></p>
<!--mstheme--></font>
<h5><!--mstheme--><font face="宋体" color="#6666FF"><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; mso-fareast-font-family: 黑体"><font size="5" color="#FFFF00">5</font></span><font size="5" color="#FFFF00"><span style="mso-bidi-font-size: 10.0pt; font-family: 黑体; 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></font></b><!--mstheme--></font></h5>
<!--mstheme--><font face="宋体">
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">这一操作的实现依据是：若一个结点是某子树在中序下的第一个结点，则它必是该子树在后序下的第一个结点。该结论可以用反证法证明。</span></font></b></font></p>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">下面就依据这一结论，讨论在中序线索二叉树上查找某结点在后序下前驱结点的情况。设开始时，指向此某结点的指针为</span><span lang="EN-US">p</span><span style="font-family:宋体;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"><b><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">（</span><span lang="EN-US">1</span><span style="font-family:宋体;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"><span style="font-family:宋体;
mso-hansi-font-family:"Times New Roman""><font color="#FFFFFF"><b><font size="5">①
当<span lang="EN-US">p->ltag=0时，p->lchild为</span></font></b></font></span><font color="#FFFFFF"><b><font size="5"><span lang="EN-US">p</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">在后序下的前驱</span><span style="font-family:
宋体;mso-hansi-font-family:"Times New Roman"">；<span lang="EN-US"><o:p>
</o:p>
</span></span></font></b></font></p>
<p class="MsoNormal" style="margin-left:21.0pt"><span style="font-family:宋体;
mso-hansi-font-family:"Times New Roman""><font color="#FFFFFF"><b><font size="5">②
当<span lang="EN-US">p->ltag=1时，p->rchild为</span></font></b></font></span><font color="#FFFFFF"><b><font size="5"><span lang="EN-US">p</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">在后序下的前驱</span><span style="font-family:
宋体;mso-hansi-font-family:"Times New Roman"">。</span></font></b></font></p>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">（</span><span lang="EN-US">2</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">）若待确定后序前驱的结点为叶子结点，则也有两种情况：</span></font></b></font></p>
<p class="MsoNormal"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman" lang="EN-US"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><span style="font-family:宋体;
mso-hansi-font-family:"Times New Roman""><font color="#FFFFFF"><b><font size="5">①</font></b></font></span><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font color="#FFFFFF"><b><font size="5"> 若p->lchild是头结点，则遍历结束；<o:p>
</o:p>
</font></b></font></span></p>
<p class="MsoNormal"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman" lang="EN-US"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><span style="font-family:宋体;
mso-hansi-font-family:"Times New Roman""><font color="#FFFFFF"><b><font size="5">②
</font></b></font></span><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font color="#FFFFFF"><b><font size="5">若p->lchild不是头结点，则p结点一定是以p->lchild结点为根的右子树中在中中序遍历下的第一个结点，因此p结点也是在该子树中按后序遍历的第一个结点。此时，若p->lchild结点有左子树，则所找结点在后序下的前驱结点的地址为p->lchild->lchild；若p->lchild为线索，则让p＝p->lchild，反复情况（2）的判定。<o:p>
</o:p>
</font></b></font></span></p>
<p class="MsoNormal" style="margin-left:21.0pt"><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">
在中序线索二叉树上寻找结点</span><span lang="EN-US">p</span><span style="font-family:宋体;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" size="5"><b>BiThrTree
IPostPretNode</b></font></span><font color="#FFFFFF" size="4"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">（</span><span lang="EN-US">BiThrTree
head,BiThrTree p</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">）</span></font></p>
<p class="MsoNormal" style="margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF"><b><font size="5">{</font></b></font></span><font color="#FFFFFF"><b><font size="5"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</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">p</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">head</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">*/<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"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">BiThrTree pre;</font></b></font></span></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"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">if (p->rtag==0)
pre=p->rchild;</font></b></font></span></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"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">else { pre=p;</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 21.0pt; margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">while (pre->ltag==1&&
post->rchild!=head)</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 21.0pt; margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b> </b></font><font color="#FFFFFF"><b><font size="5">
pre=pre->lchild;</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 21.0pt; margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">pre=pre->lchild;</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 21.0pt; margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">}</font></b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">return(pre);</font></b></font></span></p>
<p class="MsoNormal" style="margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>}</b></font></span></p>
<p align="left"> </p>
<p align="center"><b><a href="ds6.3.3.HTM"><font size="5" color="#FFFF00">返回</font></a></b></p>
<!--mstheme--></font>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -