📄 8_5.htm
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb_2312-80">
<META NAME="Generator" CONTENT="Microsoft Word 97">
<TITLE>第 2 章 线性表</TITLE>
</HEAD>
<BODY>
<B><FONT SIZE=3><P ALIGN="JUSTIFY">5. </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>二叉排序树的删除算法</P>
</B><P ALIGN="JUSTIFY">	</FONT><B><FONT SIZE=3>Status</B> DeleteBST ( BiTree <B>&</B>T, KeyType key ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>若二叉排序树</FONT><FONT SIZE=3> <I>T</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>中存在关键字等于</FONT><FONT SIZE=3> <I>key</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的数据元素时，则删除该数据元素结点</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>并返回</FONT><FONT SIZE=3> TRUE</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>；否则返回</FONT><FONT SIZE=3> FALSE</P>
<P ALIGN="JUSTIFY">	 <B>if</B> ( <B>!</B> T ) <B>return</B> FALSE;						// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>不存在关键字等于</FONT><FONT SIZE=3> <I>key</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的数据元素</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> <B>else {</P>
</B></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">		</FONT><B><FONT SIZE=3>if</B> ( key = T->data.key ) Delete (T);			// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>找到关键字等于</FONT><FONT SIZE=3> <I>key</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的数据元素</P>
<P ALIGN="JUSTIFY">		</FONT><B><FONT SIZE=3>else if</B> ( key < T->data.key ) DeleteBST ( T->lchild, key );</P>
<P ALIGN="JUSTIFY">		<B>else</B> DeleteBST ( T->rchild, key )</P>
<P ALIGN="JUSTIFY">		<B>return</B> TRUE;</P>
<P ALIGN="JUSTIFY">	 </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // else </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
<P ALIGN="JUSTIFY">	<B>}</B></FONT><FONT SIZE=3> // DeleteBST</P>
<P ALIGN="JUSTIFY"></P>
<P ALIGN="JUSTIFY">	<B>Status</B> DeleteBST ( BiTree <B>&</B>p ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>从二叉排序树中删除结点</FONT><FONT SIZE=3> <I>p</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，并重接它的左子树或右子树</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> <B>if</B> ( <B>!</B> p->rchild ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</B>							</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>右子树空，则只需重接它的左子树</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3>q = p; p = p->lchild; <B>free</B> (q);</P>
<P ALIGN="JUSTIFY">	 </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</FONT><FONT SIZE=3> </B>// if </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
<B><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> else if</B> ( <B>!</B> p->lchild ) {						// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>左子树空，则只需重接它的右子树</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3>q = p; p = p->rchild; <B>free</B> (q);</P>
<P ALIGN="JUSTIFY">	 } // else if </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
<B><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> else {										</B>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>左子树和右子树均不空</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3>q = p; s = p->lchild;</P>
</FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3>while</B> ( s->rchild ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</B>						</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>转左，然后向右到尽头</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> q = s; s = s->rchild</P>
<P ALIGN="JUSTIFY">		</FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</P>
</B><P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3>p->data = s->data;							// <I>s</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指向被删除结点的前驱</P>
<B><P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3>if</B> ( q <B>!</B> = p ) q->rchild = s->lchild;			// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>重接</FONT><FONT SIZE=3> <I>q</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指针所指的右子树</P>
<B><P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3>else</B> q->lchild = s->rchild;					// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>重接</FONT><FONT SIZE=3> <I>q</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指针所指的左子树</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</FONT><FONT SIZE=3> </B>// else </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
<P ALIGN="JUSTIFY">	<B>}</B></FONT><FONT SIZE=3> // DeleteBST</P></FONT></BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -