📄 8_6.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">6. </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>二叉平衡树的旋转算法</P>
</B><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3>(1) </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>右旋平衡处理。</P>
<P ALIGN="JUSTIFY">	</FONT><B><FONT SIZE=3>void</B> R_Rotate ( BSTree <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>为根的二叉排序树作右旋处理，处理之后</FONT><FONT SIZE=3> <I>p</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指向新的树根结点，</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>即旋转处理之前的左子树的根结点。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> lc = p->lchild;								// <I>lc</I> </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> p->lchild = lc->rchild; p->bf = 0	 			// <I>p</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>左子树指向</FONT><FONT SIZE=3> <I>lc</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>右子树，且平衡因子为</FONT><FONT SIZE=3> 0</P>
<P ALIGN="JUSTIFY"> lc->rchild = p; lc->bf = 0			 			// <I>lc</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>右子树指向</FONT><FONT SIZE=3> <I>p</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，且平衡因子为</FONT><FONT SIZE=3> 0</P>
</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> p = lc;							 			// <I>p</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指向新的根结点，</P>
<B><P ALIGN="JUSTIFY">	}</B></FONT><FONT SIZE=3> // R_Rotate</P>
</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3>(2) </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>左旋平衡处理。</P>
<P ALIGN="JUSTIFY">	</FONT><B><FONT SIZE=3>void</B> L_Rotate ( BSTree <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>为根的二叉排序树作左旋处理，处理之后</FONT><FONT SIZE=3> <I>p</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指向新的树根结点，</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>即旋转处理之前的右子树的根结点。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> rc = p->rchild;					 			// <I>rc</I> </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> p->rchild = rc->lchild; p->bf = 0	 			// <I>p</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>右子树指向</FONT><FONT SIZE=3> <I>rc</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>左子树，且平衡因子为</FONT><FONT SIZE=3> 0</P>
<P ALIGN="JUSTIFY"> rc->lchild = p; rc->bf = 0		 				// <I>rc</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的左子树指向</FONT><FONT SIZE=3> <I>p</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，且平衡因子为</FONT><FONT SIZE=3> 0</P>
</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> p = rc;							 			// <I>p</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指向新的根结点，</P>
<B><P ALIGN="JUSTIFY">	}</B></FONT><FONT SIZE=3> // L_Rotate</P></FONT></BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -