数据结构

b · 发表于 2004-5-29 04:30:57

<H2>特殊形态的二叉树</H2><

> 满二叉树和近似满二叉树是二叉树的两种特殊情形。<

>一棵高度为h≥0且有2h+1-1个结点的二叉树称为满二叉树。<

>若一棵二叉树至多只有最下面的两层结点的度数小于2，并且最下面一层结点都集中在该层的最左边，则称这种二叉树为近似满二叉树(有时也称为完全二叉树)。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img17.gif">(a) 满二叉树<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img18.gif">(b) 近似满二叉树<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img19.gif">(c) 非近似满二叉树图5 特殊形态的二叉树</BLOCKQUOTE>例如图5(a)是一棵高度为3的满二叉树。满二叉树的特点是每一层上的结点数都达到最大值，即对给定的高度，它是具有最多结点数的二叉树。满二叉树中不存在度数为1的结点，每个分枝结点均有两棵高度相同的子树，且叶结点都在最下面一层上。图5(b)是一棵近似满二叉树。显然满二叉树是近似满二叉树，但近似满二叉树不一定是满二叉树。在满二叉树的最下层上，从最右结点开始连续往左删去若干个结点后得到的二叉树是一棵近似满二叉树。因此，在近似满二叉树中，若某个结点没有左儿子，则它一定没有右儿子，即该结点是一个叶结点。图5(c)中，结点F没有左儿子而有右儿子L，故它不是一棵近似满二叉树

b · 发表于 2004-5-29 04:31:13

<H2>ADT二叉树的操作</H2><

>二叉树的常用操作与<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter4.htm" target="_blank" >树的常用操作</A>相似。<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" border=0><TR><TD 10pt" align=middle width="42%" bgColor=#e0e0e0>运算</TD><TD 10pt" align=middle width="58%" bgColor=#e0e0e0>含义</TD></TR><TR><TD 10pt" width="42%" bgColor=#e0e0e0>

arent(v,T)</TD><TD 10pt" width="58%" bgColor=#e0e0e0>这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为∧，表示结点v没有父结点。</TD></TR><TR><TD 10pt" width="42%" bgColor=#e0e0e0>Left_Child(v,T)</TD><TD 10pt" width="58%" bgColor=#e0e0e0>这是一个求左儿子结点的函数。函数值为树T中结点v的左儿子。当结点v没有左儿子时，函数值为∧。</TD></TR><TR><TD 10pt" width="42%" bgColor=#e0e0e0>Right_Child(v,T)</TD><TD 10pt" width="58%" bgColor=#e0e0e0>这是一个求右儿子结点的函数。函数值为树T中结点v的右儿子。当结点v没有右儿子时，函数值为∧。</TD></TR><TR><TD 10pt" width="42%" bgColor=#e0e0e0>Create(x,Left,Right,T)</TD><TD 10pt" width="58%" bgColor=#e0e0e0>这是一个建树过程。该函数生成一棵新的二叉树T，T的根结点v的标号为x，v的左右儿子分别为Left和Right。</TD></TR><TR><TD 10pt" width="42%" bgColor=#e0e0e0>Label(v,T)</TD><TD 10pt" width="58%" bgColor=#e0e0e0>这时一个求标号的函数，函数值就是结点v的标号。</TD></TR><TR><TD 10pt" width="42%" bgColor=#e0e0e0>Root(T)</TD><TD 10pt" width="58%" bgColor=#e0e0e0>这是一个求树根的函数，函数值为树T的根结点。当T是空树时，函数值为∧。</TD></TR><TR><TD 10pt" width="42%" bgColor=#e0e0e0>MakeNull(T)</TD><TD 10pt" width="58%" bgColor=#e0e0e0>这是一个过程，它使T成为一棵空树。</TD></TR></TABLE></CENTER></DIV>

b · 发表于 2004-5-29 04:31:32

<H2>二叉树的实现</H2>
<

>我们已经看到，<a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter1.htm#difference" target="_blank" >虽然二叉树与树很相似，但它却不是树的特殊情形</A>。在许多情况下，使用二叉树具有结构简单，操作方便的优点。另外我们也看到，在<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter6_3.htm" target="_blank" >树的左儿子右兄弟表示法</A>中，实际上已将一棵一般的树转化为一棵二叉树。在更一般的情形，我们还可以<a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter6_1.htm" target="_blank" >将果园或森林转化为一棵等价的二叉树</A>。下面我们来讨论几种二叉树的表示方法，最后还将介绍一种二叉树的扩展——<a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter5_4.htm" target="_blank" >线索二叉树</A>。
<UL>
<LI><a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter5_1.htm" target="_blank" >二叉树的顺序存储结构</A>
<LI><a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter5_2.htm" target="_blank" >二叉树的结点度表示法</A>
<LI><a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter5_3.htm" target="_blank" >二叉树的链式存储结构</A>
<LI><a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter5_4.htm" target="_blank" >线索二叉树</A> </LI></UL>

b · 发表于 2004-5-29 04:32:35

<H3>二叉树的顺序存储结构</H3><

>此结构是将二叉树的所有结点，按照一定的次序，存储到一片连续的存储单元中。因此，必须将结点排成一个适当的线性序列，使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。这种结构特别适用于<a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter3.htm" target="_blank" >近似满二叉树</A>。<

>在一棵具有n个结点的近似满二叉树中，我们从树根起，自上层到下层，逐层从左到右给所有结点编号，就能得到一个足以反映整个二叉树结构的线性序列，如图6所示。其中每个结点的编号就作为结点的名称。<BLOCKQUOTE><

align=center><img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img22.gif">图6 近似满二叉树的结点编号</BLOCKQUOTE>因此，我们可以对树的类型作如下说明：<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">TPosition=integer;TreeType=record NodeCount:integer; {树的总结点数} NodeList:array [1..MaxNodeCount] of LabelType; {存储结点的数组} end; </TD></TR></TABLE></CENTER></DIV>将数组下标作为结点名称(编号)，就可将二叉树中所有结点的标号存储在一维数组中。例如，图6中的二叉树的顺序存储结构如图7所示。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img23.gif">图7 近似满二叉树的顺序存储结构</BLOCKQUOTE>
在二叉树的这种表示方式下，各结点之间的逻辑关系是隐含表示的。<a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter3.htm" target="_blank" >近似满二叉树</A>中，除最下面一层外，各层都充满了结点。可能除最底层外，每一层的结点个数恰好是上一层结点个数的2倍。因此，从一个结点的编号就可推知其父亲，左、右儿子，和兄弟等结点的编号。例如，对于结点i我们有：<OL><LI>仅当i=1时，结点i为根结点； <LI>当i>1时，结点i的父结点为<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img8.gif">i/2<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img9.gif">； <LI>结点i的左儿子结点为2i； <LI>结点i的右儿子结点为2i+1； <LI>当i为奇数且不为1时，结点i的左兄弟结点为i-1； <LI>当i为偶数时，结点i的右兄弟结点为i+1。 </LI></OL>由上述关系可知，近似满二叉树中结点的层次关系足以反映结点之间的逻辑关系。因此，对近似满二叉树而言，顺序存储结构既简单又节省存储空间。对于一般的二叉树，采用顺序存储时，为了能用结点在数组中的位置来表示结点之间的逻辑关系，也必须按近似满二叉树的形式来存储树中的结点。显然，这将造成存储空间的浪费。在最坏情况下，一个只有k个结点的右单枝树却需要2k-1个结点的存储空间。例如，只有3个结点的右单枝树，如图8(a)所示，添上一些实际不存在的虚结点后，成为一棵近似满二叉树，相应的顺序存储结构如图8(b)所示。<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img1.gif">图8 一般二叉树的顺序存储结构下面我们就用这种顺序存储结构来实现二叉树的常用操作。在这种表示法中，整数0表示空结点∧。对于非近似满二叉树，我们将其补为近似满二叉树，并规定一个特殊的标号&，用来表示补充的结点，&要根据标号的具体类型来确定。顺序存储结构实现ADT二叉树的操作<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" border=0><TR><TD width="100%" bgColor=#e0e0e0>函数 Parent(v,T);功能<BLOCKQUOTE>这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为∧，表示结点v没有父结点。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Parent(v:TPosition;var T:TreeType):TPosition;begin return(v div 2);end;</BLOCKQUOTE>说明<BLOCKQUOTE>根据这种表示法，我们知道，当i>1时，结点i的父结点为<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img8.gif">i/2<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img9.gif">。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Left_Child(v,T);功能<BLOCKQUOTE>这是一个求左儿子结点的函数。函数值为树T中结点v的左儿子。当结点v没有左儿子时，函数值为∧。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Left_Child(v:TPosition;var T:TreeType):TPosition;begin if (2*v>T.NodeCount)or(T.NodeList[2*v]=&) then return(0) else return(2*v);end;</BLOCKQUOTE>说明<BLOCKQUOTE>如果结点v的左儿子存在，则其下标为2*v。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Right_Child(v,T);功能<BLOCKQUOTE>这是一个求右儿子结点的函数。函数值为树T中结点v的右儿子。当结点v没有右儿子时，函数值为∧。</BLOCKQUOTE>实现<BLOCKQUOTE>Procedure Right_Child(v:TPosition;var T:TreeType):TPosition;begin if (2*v+1>T.NodeCount)or(T.NodeList[2*v+1]=&) then return(0) else return(2*v+1);end;</BLOCKQUOTE>说明<BLOCKQUOTE>如果结点v的左儿子存在，则其下标为2*v+1。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR></TABLE></CENTER></DIV>

b · 发表于 2004-5-29 04:33:25

<TABLE cellPadding=5 width="90%" border=0><TR><TD width="100%" bgColor=#e0e0e0><

5px; MARGIN-BOTTOM: 5px">函数 Left_Child(v,T);<

5px; MARGIN-BOTTOM: 5px">功能<BLOCKQUOTE><

5px; MARGIN-BOTTOM: 5px">这是一个求左儿子结点的函数。函数值为树T中结点v的左儿子。当结点v没有左儿子时，函数值为∧。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Left_Child(v:TPosition;var T:TreeType):TPosition;begin if (2*v>T.NodeCount)or(T.NodeList[2*v]=&) then return(0) else return(2*v);end;</BLOCKQUOTE>说明<BLOCKQUOTE>如果结点v的左儿子存在，则其下标为2*v。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Right_Child(v,T);功能<BLOCKQUOTE>这是一个求右儿子结点的函数。函数值为树T中结点v的右儿子。当结点v没有右儿子时，函数值为∧。</BLOCKQUOTE>实现<BLOCKQUOTE>Procedure Right_Child(v:TPosition;var T:TreeType):TPosition;begin if (2*v+1>T.NodeCount)or(T.NodeList[2*v+1]=&) then return(0) else return(2*v+1);end;</BLOCKQUOTE>说明<BLOCKQUOTE>如果结点v的左儿子存在，则其下标为2*v+1。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Create(x,Left,Right,T);功能<BLOCKQUOTE>这是一个建树过程。该函数生成一棵新的二叉树T，T的根结点标号为x，左右儿子分别为Left和Right。</BLOCKQUOTE>实现<BLOCKQUOTE>Procedure Create(x

abelType;var Left,Right,T:TreeType);begin T.NodeList[1]:=x; T.NodeCount:=Left.NodeCount+Right.NodeCount+1; h_left:=cal(Left.NodeCount); h_right:=cal(Right.NodeCount);{分别计算Left和Right的高度} if h_left>h_Right then h:=h_left else h:=h_right;{新树T的高度为h+1} for i:=Left.NodeCount+1 to (1 shl (h+1))-1 do Left.NodeList:=&； Left.NodeCount:=(1 shl (h+1))-1; {将Left补成高度为h的满二叉树；其中shl是左移位运算，用来计算2的幂}if h_right<h then begin for i:=Right.NodeCount+1 to (1 shl h)-1 do Right.NodeList:=&； Right.NodeCount:=(1 shl h)-1; end; {若Right的高度小于h，则将Right补成高度为h-1的满二叉树}　{=======对于Left中编号为i的结点v，它在新树T中的编号为2h +i，其中h=<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img10.gif">log2(i+1)-1<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img11.gif"> ；对于Right中编号为i的结点v，它在新树T中的编号为2h+1+i，其中h=<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img10.gif">log2(i+1)-1<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img11.gif"> 。=======}　 for i:=1 to Left.NodeCount do T.NodeList[(1 shl cal(i))+i]:=Left.NodeList;{计算出Left中编号为i的结点在T中的位置，将其复制到T中} for i:=1 to Right.NodeCount do T.NodeList[(1 shl (cal(i)+1))+i]:=Right.NodeList;{计算出Right中编号为i的结点在T中的位置，将其复制到T中}end;　其中cal(i)用来计算含有i个结点的近似满二叉树T的高度，cal(i)=<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img10.gif">log2(i+1)-1<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img11.gif">,可以实现如下：　Function cal(i:integer;):integer;varx:real;begin x:=log2(i+1)-1; if x=int(x) then return(x) else return(int(x)+1); {向上取整}end;　其中log2(n)计算实数n以2为底的对数。</BLOCKQUOTE>说明<BLOCKQUOTE>　在顺序存储的结构下，建立一棵新的二叉树的过程比较复杂。我们首先给出以下几个命题：　命题一<BLOCKQUOTE>一棵<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter2.htm" target="_blank" >高度</A>为h的<a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter3.htm" target="_blank" >满二叉树</A>有2h+1-1个结点。</BLOCKQUOTE>证明：<BLOCKQUOTE>满二叉树的第i层有2i个结点，i=0,1,2,...,h(树根为第0层)，因此高度为h的满二叉树有20+21+..+2h = 2h+1-1个结点。</BLOCKQUOTE>推论一<BLOCKQUOTE>我们从树根起，自上层到下层，逐层从左到右给二叉树的所有结点编号，如<a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter5_1.htm#image6" target="_blank" >图6</A>所示，则<a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter3.htm" target="_blank" >近似满二叉树</A>的第h层的从左到右第k个结点的编号为2h+k-1。</BLOCKQUOTE>证明：<BLOCKQUOTE>由于是近似满二叉树，所以第0层到第h-1层是满二叉树，根据命题一知道共有2h-1个结点，因此第h层的从左到右第1个结点的编号为2h-1+1，第h层的从左到右第k个结点的编号为2h-1+k。</BLOCKQUOTE>推论二<BLOCKQUOTE>一棵有n个结点的近似满二叉树，高度为<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img10.gif">log2(n+1)-1<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img11.gif"> ,其中<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img10.gif"> <img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img11.gif">是天花板符号，<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img10.gif"> x<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img11.gif">表示大于等于x的最小整数。</BLOCKQUOTE>证明：<BLOCKQUOTE>有n个结点的近似满二叉树，若其高度为h，则满足2h-1<n≤2h+1-1,化简得 log2(n+1)-1 ≤ h < [log2(n+1)-1]+1，即h=<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img10.gif">log2(n+1)-1<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img11.gif">。</BLOCKQUOTE>推论三<BLOCKQUOTE>在近似满二叉树T中，设编号为i的结点处于T的第h层从左到右第k个位置上，则h=<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img10.gif">log2(i+1)-1<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img11.gif"> ，k=i-(2h-1)。</BLOCKQUOTE>证明：<BLOCKQUOTE>我们先不考虑编号大于i的结点，则前i个结点构成一棵近似满二叉树，根据推论二知其层数为h=<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img10.gif">log2(i+1)-1<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img11.gif"> ，又因为第0层到第h-1层是满二叉树，根据命题一知道共有2h-1个结点，所以编号为i的结点处于第h层的第k=i-(2h-1)个位置上。</BLOCKQUOTE>我们用T(h,k)表示树T的第h层的第k个结点，则有下列命题：　命题二<BLOCKQUOTE>Left(h,k)=T(h+1,k)，Right(h,k)=T(h+1,k+2h)，其中Left和Right分别是树T的根结点的左右子树。</BLOCKQUOTE>证明：<BLOCKQUOTE>显然。</BLOCKQUOTE>我们用N(v,T)表示结点v在生成的新树T中的编号，则有下列命题：　命题三<BLOCKQUOTE>对于Left中编号为i的结点v，N(v,T)=2h +i，其中h=<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img10.gif">log2(i+1)-1<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img11.gif"> ；对于Right中编号为i的结点v，N(v,T)=2h+1+i，其中h=<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img10.gif">log2(i+1)-1<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img11.gif"> 。</BLOCKQUOTE>证明：<BLOCKQUOTE>在Left中编号为i的结点，根据推论三，他处于Left的第h=<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img10.gif">log2(i+1)-1<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img11.gif"> 层，第k=i-(2h-1)个位置上。根据命题二该结点处于新树T的第h+1层第k个位置上，所以根据推论一，它在二叉树T中的编号为2h+1+k-1=2*2h+[i-(2h-1)]-1=2h+i。结点在Right中的情况同理可证。</BLOCKQUOTE>　有了命题三，我们就可以完成建树的过程。算法如下：<OL><LI>根据推论二计算Left和Right的高度，分别为hLeft和hRight ； <LI>设h=max{hLeft,hRight}，新树T的高度就为h+1； <LI>将Left补成高度为h的满二叉树； <LI>若hRight<h，则将Right补成高度为h-1的满二叉树； <LI>依次扫描Left的每一个结点，根据命题三计算出Left中编号为i的结点在T中的位置，将其复制到T中； <LI>依次扫描Right的每一个结点，根据命题三计算出Right中编号为i的结点在T中的位置，将其复制到T中； </LI></OL>具体程序见前文的实现。</BLOCKQUOTE>复杂性<BLOCKQUOTE>算法的主要时间花在扫描和赋值结点上，设新树有n个结点，则复杂性为O(n)。</BLOCKQUOTE></TD></TR></TABLE>

b · 发表于 2004-5-29 04:33:38

<H3>二叉树的结点度表示法</H3><

>二叉树的顺序存储结构可看作是二叉树的一种无边表示，即树中边信息是隐含的。二叉树的另一种无边表示称为二叉树的结点度表示。这种表示法将二叉树中所有结点依其后序列表排列，并在每个结点中附加一个0到3之间的整数，以表示结点的状态。该整数为0时，表示相应的结点为一叶结点；为1时，表示相应结点只有一个左儿子；为2时，表示相应结点只有一个右儿子；为3时，表示相应结点有两个儿子。例如，图9(a)中的二叉树的结点度表示如图9(b)所示。<BLOCKQUOTE><

align=center><img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img2.gif"><

align=center>图9 二叉树的结点度表示</BLOCKQUOTE>在二叉树的结点度表示下，结点土的右儿子很容易找到，因为依后序列表法则，如果结点i有右儿子，它一定排在结点i的前一个，即i-1为其右儿子。找结点i的左儿子和父亲不像找右儿子那样直接。因为我们所知道的只是左儿子在i之前，而父亲在i之后，所以，结点i的左儿子和父亲必须对结点i之前和之后的结点进行搜索才能找到。说明：这种表示法我不了解，所以运算的实现暂缺。<a href="mailtstarfish.h@china.com" target="_blank" >或许你可以帮助我。</A>　 <DIV align=center><CENTER><TABLE cellPadding=5 width="90%" border=0><TR><TD width="100%" bgColor=#e0e0e0>函数 Parent(v,T);功能<BLOCKQUOTE>这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为∧，表示结点v没有父结点。</BLOCKQUOTE>实现<BLOCKQUOTE>　</BLOCKQUOTE>说明<BLOCKQUOTE>　</BLOCKQUOTE>复杂性<BLOCKQUOTE>　</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Left_Child(v,T);功能<BLOCKQUOTE>这是一个求左儿子结点的函数。函数值为树T中结点v的左儿子。当结点v没有左儿子时，函数值为∧。</BLOCKQUOTE>实现<BLOCKQUOTE>　</BLOCKQUOTE>说明<BLOCKQUOTE>　</BLOCKQUOTE>复杂性<BLOCKQUOTE>　</BLOCKQUOTE>　 </TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Right_Child(v,T);功能<BLOCKQUOTE>这是一个求右儿子结点的函数。函数值为树T中结点v的右儿子。当结点v没有右儿子时，函数值为∧。</BLOCKQUOTE>实现<BLOCKQUOTE>　</BLOCKQUOTE>说明<BLOCKQUOTE>　</BLOCKQUOTE>复杂性<BLOCKQUOTE>　</BLOCKQUOTE>　 </TD></TR></TABLE></CENTER></DIV>

b · 发表于 2004-5-29 04:33:48

<

5px; MARGIN-BOTTOM: 5px">函数 Create(x,Left,Right,T);<

5px; MARGIN-BOTTOM: 5px">功能<BLOCKQUOTE><

5px; MARGIN-BOTTOM: 5px">这是一个建树过程。该函数生成一棵新的二叉树T，T的根结点标号为x，左右儿子分别为Left和Right。</BLOCKQUOTE>实现<BLOCKQUOTE>　</BLOCKQUOTE>说明<BLOCKQUOTE>　</BLOCKQUOTE>复杂性

b · 发表于 2004-5-29 04:34:06

<H3>二叉树的链式存储结构</H3><

>由于二叉树的每个结点最多有两个儿子，因此存储二叉树的最自然的方法是链接的方法。在用链接方式存储二叉树时，对于每个结点，除了存储结点标号等信息外，还应设置指向结点左右儿子的指针LeftChild和RightChild。结点的类型说明为:<DIV align=center><CENTER><TABLE 10pt" cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%"><

5px; MARGIN-BOTTOM: 5px">Type<

5px; MARGIN-BOTTOM: 5px">TPosition=^NodeType;NodeType=record Label

abelType; LeftChild,RightChild:TPosition; end;TreeType=TPosition; </TD></TR></TABLE></CENTER></DIV>若用游标来模拟指针，可用一数组来存储二叉树的所有结点，并对此数组作如下说明:<DIV align=center><CENTER><TABLE 10pt" cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">TypeTPosition=integer;NodeType=record Label

abelType; LeftChild,RightChild:TPosition; end;TreeType=TPosition;varSellsapce:array [1..MaxNodeCount] of NodeType; {cellspace用来存储结点单元} </TD></TR></TABLE></CENTER></DIV>例如，<a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter5_2.htm#image9" target="_blank" >图9(a)</A>中二叉树，用指针实现的二叉链表和用游标实现的二叉链表分别如图10(a)和(b)所示。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img6.gif">(a)<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img7.gif">(b)图10 二叉树的链式存储结构</BLOCKQUOTE>若经常要在二叉树中进行Parent操作，可在每个结点上再加一个指向其父结点的指针Parent，形成一个带父亲指针的二叉链表，或称其为一个三叉链表。三叉链表的类型定义如下：<DIV align=center><CENTER><TABLE 10pt" cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">TypeTPosition=^NodeType;NodeType=record Label

abelType; Parent,LeftChild,RightChild:TPosition; end;TreeType=TPosition; </TD></TR></TABLE></CENTER></DIV>若用游标来模拟指针，可用一数组来存储二叉树的所有结点，并对此数组作如下说明:<DIV align=center><CENTER><TABLE 10pt" cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">TypeTPosition=integer;NodeType=record Label:LabelType; Parent,LeftChild,RightChild:TPosition; end;TreeType=TPosition;varCellspace:array [1..MaxNodeCount] of NodeType;{cellspace用来存储结点} </TD></TR></TABLE></CENTER></DIV>下面我们就针对三叉链表讨论ADT二叉树基本操作的实现。请注意，下面的三叉链是用指针实现的，用游标实现的三叉链与此类似。<BLOCKQUOTE>三叉链表实现ADT二叉树基本操作</BLOCKQUOTE><DIV align=center><CENTER><TABLE cellPadding=5 width="90%" border=0><TR><TD width="100%" bgColor=#e0e0e0>函数 Parent(v,T);功能<BLOCKQUOTE>这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为∧，表示结点v没有父结点。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Parent(v:TPosition;var T:TreeType);begin return(v^.Parent);end;</BLOCKQUOTE>说明<BLOCKQUOTE>直接返回v的父结点指针。</BLOCKQUOTE>复杂性<BLOCKQUOTE>O(1)</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Left_Child(v,T);功能<BLOCKQUOTE>这是一个求左儿子结点的函数。函数值为树T中结点v的左儿子。当结点v没有左儿子时，函数值为∧。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Left_Child(v:TPosition;var T:TreeType):TPosition;begin return(v^.LeftChild);end;</BLOCKQUOTE>说明<BLOCKQUOTE>直接返回v的左儿子指针。</BLOCKQUOTE>复杂性<BLOCKQUOTE>O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Right_Child(v,T);功能<BLOCKQUOTE>这是一个求右儿子结点的函数。函数值为树T中结点v的右儿子。当结点v没有右儿子时，函数值为∧。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Right_Child(v:TPosition;var T:TreeType):TPosition;begin return(v^.RightChild);end;</BLOCKQUOTE>说明<BLOCKQUOTE>直接返回v的右儿子指针。</BLOCKQUOTE>复杂性<BLOCKQUOTE>O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Create(x,Left,Right,T);功能<BLOCKQUOTE>这是一个建树过程。该函数生成一棵新的二叉树T，T的根结点标号为x，左右儿子分别为Left和Right。</BLOCKQUOTE>实现<BLOCKQUOTE>Procedure Create(x:LabelType;var Left,Right,T:TreeType);begin new(T); T^.Label:=x; T^.LeftChild:=Left; T^.RightChild:=Right; T^.Parent:=nil; Left^.Parent:=T; Right^.Parent:=T;end;</BLOCKQUOTE>说明<BLOCKQUOTE>先生成一个标号为x的新结点，作为新树的根结点，然后修改其左右儿子指针，分别指向Left和Right，同时修改Left和Right的父亲指针，使其指向T。</BLOCKQUOTE>复杂性<BLOCKQUOTE>O(1)。</BLOCKQUOTE></TD></TR></TABLE></CENTER></DIV>可以看到，使用这种三叉链表示树，能在O(1)时间内完成树的大部分操作，所以推荐使用这种方法表示树

b · 发表于 2004-5-29 04:34:27

<H2>线索二叉树</H2><

>当<a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter5_3.htm" target="_blank" >用二叉链表作为二叉树的存储结构</A>时，因为每个结点中只有指向其左、右儿子结点的指针，所以从任一结点出发只能直接找到该结点的左、右儿子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。<

>我们可以证明：在n个结点的二叉链表中含有n+1个空指针。因为含n个结点的二叉链表中含有个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针，因此一共使用了n-1个指针，所以在n个结点的二叉链表中含有n+1个空指针。<

>因此可以利用这些空指针，存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。为了区分一个结点的指针是指向其儿子的指针，还是指向其前驱或后继结点的线索，可在每个结点中增加两个线索标志。这样，线索二叉树结点类型定义为：<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">type TPosition=^thrNodeType; thrNodeType=record Label

abelType; ltag,rtag:0..1; LeftChild,RightChild:TPosition; end; </TD></TR></TABLE></CENTER></DIV>其中ltag为左线索标志，rtag为右线索标志。它们的含义是:<UL><LI>ltag=0，LeftChild是指向结点左儿子的指针； <LI>ltag=1，LeftChild是指向结点前驱的左线索。
<LI>rtag=0，RightChild是指向结点右儿子的指针； <LI>rtag=1，RihgtChild是指向结点后继的右线索。 </LI></UL>例如图13(a)是一棵中序线索二叉树，它的线索链表如图13(b)所示。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img3.gif">(a)<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img4.gif">(b)图13 线索二叉树及其线索链表</BLOCKQUOTE>图13(b)中，在二叉树的线索链表上增加了一个头结点，其LeftChild指针指向二叉树的根结点，其RightChild指针指向中序遍历时的最后一个结点。另外，二叉树中依中序列表的第一个结点的LeftChild指针，和最后一个结点的RightChild指针都指向头结点。这就像为二叉树建立了一个双向线索链表，既可从第一个结点起，顺着后继进行遍历，也可从最后一个结点起顺着前驱进行遍历。如何在线索二叉树中找结点的前驱和后继结点？以图13的中序线索二叉树为例。树中所有叶结点的右链是线索，因此叶结点的RightChild指向该结点的后继结点，如图13中结点"b"的后继为结点"*"。当一个内部结点右线索标志为0时，其RightChild指针指向其右儿子，因此无法由RightChild得到其后继结点。然而，由中序遍历的定义可知，该结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。例如在找结点"*"的后继时，首先沿右指针找到其右子树的根结点"-"，然后沿其LeftChild指针往下直至其左线索标志为1的结点，即为其后继结点(在图中是结点"c")。类似地，在中序线索树中找结点的前驱结点的规律是：若该结点的左线索标志为1，则LeftChild为线索，直接指向其前驱结点，否则遍历左子树时最后访问的那个结点，即左子树中最右下的结点为其前驱结点。由此可知，若线索二叉树的高度为h，则在最坏情况下，可在O(h)时间内找到一个结点的前驱或后继结点。在对中序线索二叉树进行遍历时，无须像非线索树的遍历那样，利用递归引入栈来保存待访问的子树信息。对一棵非线索二叉树以某种次序遍历使其变为一棵线索二叉树的过程称为二叉树的线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。为了记下遍历过程中访问结点的先后次序，可附设一个指针pre始终指向刚刚访问过的结点。当指针p指向当前访问的结点时，pre指向它的前驱。由此也可推知pre所指结点的后继为p所指的当前结点。这样就可在遍历过程中将二叉树线索化。对于找前驱和后继结点这二种运算而言，线索树优于非线索树。但线索树也有其缺点。在进行插人和删除操作时，线索树比非线索树的时间开销大。原因在于在线索树中进行插人和删除时，除了修改相应的指针外，还要修改相应的线索

b · 发表于 2004-5-29 04:34:41

<H2>二叉树的应用 </H2>
<

align=left> 二叉树是一种非常重要的抽象数据类型，许多复杂的ADT和算法都利用二叉树来实现。下面简单地介绍一下二叉树的经典应用。
<UL>
<LI><a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter6_1.htm" target="_blank" >果园或森林的二叉树表示</A> </LI></UL>

		自动登录	找回密码
密码			注-册-帐-号