📄 6_12.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">12. </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>中序线索化二叉树算法</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> Status</B> InOrderThreading ( BiThrTree <B>&</B>Thrt, BiThrTree T ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B></FONT><FONT SIZE=3><P ALIGN="JUSTIFY">// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>遍历二叉树</FONT><FONT SIZE=3> <I>T</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，并将其中序线索化，</FONT><I><FONT SIZE=3>Thrt</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指向头结点，</FONT><I><FONT SIZE=3>T</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>	</FONT><FONT SIZE=3> <B>if</B> ( <B>!</B> ( Thrt = ( BiThrTree ) <B>malloc</B> ( <B>sizeof </B>( BiThrNode ) ) ) ) <B>exit</B> ( OVERFLOW );</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> Thrt->ltag = Link; 	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>建立头结点的左标志</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> Thrt->rtag = Thread;	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>						</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>建立头结点的右标志</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> Thrt->rchild = Thrt;	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>						</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>头结点的右指针回指</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>if</B> ( <B>!</B> T ) Thrt->lchild = Thrt;	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>				</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>若二叉树为空则头结点左指针回指</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> <B>else {</P>
</B><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>Thrt->lchild = T;</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3>pre = Thrt;</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>			</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>头结点的</FONT><FONT SIZE=3> <I>lchild</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指向根结点，</FONT><I><FONT SIZE=3>pre</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>	</FONT><FONT SIZE=3>InThreading (T);</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>							</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>进行中序线索化</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>pre->rchild = Thrt; </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>pre->rtag = Thread;</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>最后一个结点线索化</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>Thrt->rchild = pre;</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>							</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>头结点的</FONT><FONT SIZE=3> <I>rchild</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>	</FONT><FONT SIZE=3> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // else </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>return</B> OK;</P>
</FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">}</B></FONT><FONT SIZE=3> // InOrderThreading</P>
</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY"></P>
</FONT><B><FONT SIZE=3><P ALIGN="JUSTIFY"> void</B> InThreading ( BiThrTree p ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B></FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> // </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>进行中序线索化</P>
</FONT><B><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> if </B>( p ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B></FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>InThreading ( p->lchild );			</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>左子树线索化</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><B><FONT SIZE=3>if</B> ( <B>!</B> p->lchild ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B><P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> p->ltag = Thread; </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>p->lchild = pre;	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>前驱线索</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	<B>}</B></FONT><FONT SIZE=3> // if </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><B><FONT SIZE=3>if</B> ( <B>!</B> pre->rchild ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B><P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> pre->rtag = Thread; </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>pre->rchild = p;	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>后继线索</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	<B>}</B></FONT><FONT SIZE=3> // if </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> pre = p;			</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>						</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>保持</FONT><FONT SIZE=3> <I>pre </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"> InThreading ( p->rchild )</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>；					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>右子树线索化</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> if </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
<B><P ALIGN="JUSTIFY">}</B></FONT><FONT SIZE=3> // InThreading</P></FONT></BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -