📄 ds6.3.3.2.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>数 据 结 构</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>
<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">
<!--mstheme--><font face="宋体">
<p:colorscheme
colors="#0000FF,#FFFFFF,#000000,#FFCC66,#00FFFF,#3366FF,#FF0033,#FFFF00"/>
<p align="center"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font size="6"><font color="#FFFFFF">6.3.2
</font></font></span><font size="5" color="#FFFF00"><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">线索二叉树的基本操作实现</span></font></b></p>
<p align="left"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>在线索二叉树中，结点的结构可以定义为如下形式：</b></font></span></p>
<p class="MsoNormal" style="text-indent: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>typedef
char elemtype;</b></font></span></p>
<p class="MsoNormal" style="text-indent: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>typedef
struct BiThrNode {</b></font></span></p>
<p class="MsoNormal" style="text-indent: 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">elemtype data;</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 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">struct
BiThrNode *lchild;</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 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">struct
BiThrNode *rchild;</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 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">unsigned
ltag:1;</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 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">unsigned
rtag:1;</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 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">}BiThrNodeType,*BiThrTree;</font></b></font></span></p>
<p class="MsoNormal" style="text-indent:21.0pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>下面以中序线索二叉树为例，讨论线索二叉树的建立、线索二叉树的遍历以及在线索二叉树上查找前驱结点、查找后继结点、插入结点和删除结点等操作的实现算法。</b></font></span></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">1</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" 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">pre</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</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">指向当前结点，则</span><span lang="EN-US">pre</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="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" 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">pre</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"><b>int<span style="mso-spacerun: yes">
</span>InOrderThr(BiThrTree *head,BiThrTree T)</b></font></span></p>
<p class="MsoNormal" style="margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span lang="EN-US">{</span></b></font><font color="#FFFFFF" size="4"><span style="mso-bidi-font-size: 10.0pt"><b><span lang="EN-US">/*</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">T</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">*/</span></b></span></font><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font size="5" color="#FFFFFF"><b><o:p>
</o:p>
</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" size="4"><b>if (!(*head =(BiThrNodeType*)malloc(sizeof(BiThrNodeType))))<span style="mso-spacerun:
yes"> </span></b></font></span></p>
<p class="MsoNormal" style="margin-left: 21.0pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font color="#FFFFFF" size="4"><b><span style="mso-spacerun: yes"> </span><span style="mso-spacerun:
yes"> </span><span style="mso-spacerun: yes"> </span>return 0;</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">(*head)->ltag=0;<span style="mso-spacerun: yes">
</span>(*head)->rtag=1;<span style="mso-spacerun: yes"> </span></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">*/<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">(*head)->rchild=*head;<span style="mso-spacerun: yes">
</span></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">*/</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">if (!T)
(*head)->lchild=*head;</font></b></font></span><font color="#FFFFFF" size="4"><span style="mso-bidi-font-size: 10.0pt"><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">*/</span></span></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">else {</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><font color="#FFFFFF"><b><font size="5">
(*head)->lchild=T;<span style="mso-spacerun: yes"> </span>pre= head;</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">InThreading(T);<span style="mso-spacerun: yes">
</span></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">*/<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">pre->rchild=*head;pre->rtag=1;</font></b></font></span><font color="#FFFFFF" size="4"><span style="mso-bidi-font-size: 10.0pt"><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">*/</span></span></font><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font size="5" color="#FFFFFF"><b><o:p>
</o:p>
</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">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -