📄 ds6.3.3.2.htm
字号:
</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><span lang="EN-US">0</span><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></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">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"><b><font size="5">BiThrTree
InPostNode</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">BiThrTree
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; 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">*/<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 post;</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">post=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">if (p->rtag!=1)</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>while
(post->rtag==0) post=post->lchild;</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>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">以上给出的仅是在中序线索二叉树中寻找某结点的前驱结点和后继结点的算法。在前序线索二叉树中寻找结点的后继结点以及在后序线索二叉树中寻找结点的前驱结点可以采用同样的方法分析和实现。在此就不再讨论了。</span></b></font></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">4</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="text-indent: -26.25pt; mso-list: l26 level1 lfo38; tab-stops: list 47.25pt; margin-left: 30"><font size="5" color="#FFFFFF"><b><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman" lang="EN-US">（</span><span lang="EN-US" style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">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"><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-hansi-font-family:"Times New Roman"">①
当<span lang="EN-US">p->ltag=0时，p->lchild为</span></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><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" style="text-indent: -26.25pt; mso-list: l26 level1 lfo38; tab-stops: list 47.25pt; margin-left: 30"><font size="5" color="#FFFFFF"><b><span lang="EN-US" style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">（2）</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 size="5" color="#FFFFFF"><b>①
若<span lang="EN-US">p->rchild是头结点，则遍历结束；<o:p>
</o:p>
</span></b></font></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span></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->rchild不是头结点，则p结点一定是以p->rchild结点为根的左子树中在中序遍历下的最后一个结点，因此p结点也是在该子树中按先序遍历的最后一个结点。此时，若p->rchild结点有右子树，则所找结点在先序下的后继结点的地址为p->rchild->rchild；若p->rchild为线索，则让p＝p->rchild，反复情况（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 size="5" color="#FFFFFF">BiThrTree
</font><font color="#FFFFFF" size="4">IPrePostNode</font></span><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></b><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 post;</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->ltag==0)
post=p->lchild;</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 { post=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
(post->rtag==1&&post->rchild!=head) </font></b></font></span></p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -