📄 ds9.3.1.htm
字号:
<p class="MsoNormal" style="margin-bottom: 10" align="center"><img border="0" src="ds9.3.4.gif" width="306" height="144"></p>
<blockquote>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b>3.<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 lang="EN-US">P<sub>l</sub></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">又有右子树</span><span lang="EN-US">P<sub>r</sub></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，可按中序遍历保持有序进行调整。</span></b></font><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"">结点前，中序遍历序列为：{...C<sub>L</sub>C...Q<sub>L</sub>QS<sub>L</sub>SPP<sub>R</sub>F...}</span></font></b></font></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">在删除＊P之后，为保持其他元素之间的相对位置不变，可以有两种做法：</span></b></font></p>
<blockquote>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">a.令＊P的左子树为＊f的左子树，而＊P的右子树为＊s的右子树，如图（2）所示；</span></b></font></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">b.令＊P的直接前驱（或直接后继）替代＊P，然后再从二叉树中删去它的直接前驱（或直接后继），如图（1）所示。</span></b></font></p>
</blockquote>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; letter-spacing: -.4pt" lang="EN-US"> </span></b></font></p>
<p class="MsoNormal" align="center"><span lang="EN-US"><span style="mso-spacerun: yes"> </span></span><img border="0" src="二叉9.gif" align="middle" width="272" height="426">
</p>
<p class="MsoNormal" align="center"><img border="0" src="二叉10.gif" align="middle" width="235" height="405">
<img border="0" src="二叉12.gif" width="291" height="395"></p>
</blockquote>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">在二叉排序树上删除一个结点的算法如下所示：</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">Status
DelBST(BiTree &T, keyType key)</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">{</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF"> if(!T)
return FALSE;</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF"> else
</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF"> {</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
if(key==T->data.key) return Delete(T);</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
</font><font color="#FFFFFF" size="4">else if(key>T->data.key) return
DelBST(T->lchild.key);</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
else return DelBFS(T->rchild.key);</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF"> }</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">}</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"> </p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">Status
Delete(BiTree &p)</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">{</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF"> if(!p->rchild)</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
{q=p;p=p->lchild;free(q);}</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF"> else
if(!p->lcild)</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
{q=p;p=p->rchild;free(q);}</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF"> else</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
{</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
q=p;s=p->lchild;</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
while(s->rchild){q=s;s=s->rchild;}</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
p->data=s->data;</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
if(q!=p) q->rchild=s->lchild;</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
else q->lchild=s->lchild;</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
delete s;</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">
}</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF"> return
TRUE;</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF">}</font></b></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"> </p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"><span style="mso-spacerun: yes; font-family: 黑体; mso-fareast-font-family: 宋体" lang="EN-US">
<font size="5" color="#FFFFFF"><b> </b></font></span><font size="5" color="#FFFFFF"><b><span style="font-family:
宋体;mso-ascii-font-family:黑体;mso-hansi-font-family:"Times New Roman"">对给定序列建立</span><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman"">二叉排序树，若左右子树均匀分布，则其查找过程类似于有序表的折半查找。但若给定序列原本有序，则建立的二叉排序树就蜕化为单链表，其查找效率同顺序查找一样。因此，对均匀的二叉排序树进行插入或删除结点后，应对其调整，使其依然保持均匀。</span></b></font></p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"> </p>
<p class="MsoNormal" align="left" style="margin-top: 0; margin-bottom: 0"> </p>
<p class="MsoNormal" align="center" style="margin-top: 0; margin-bottom: 0"><b><span style="font-family: 宋体; mso-hansi-font-family: Times New Roman"><a href="ds9.3.HTM"><font size="5" color="#FFFF00">返回</font></a></span><font size="5" color="#FFFFFF"><span lang="EN-US" style="font-family: 宋体; mso-hansi-font-family: Times New Roman"><o:p>
</o:p>
</span></font></b></p>
<!--mstheme--></font>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -