数据结构

b · 发表于 2004-5-29 04:26:23

<H2>树的相关术语</H2><OL><LI><

10px; MARGIN-BOTTOM: 10px">一个结点的儿子结点的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。 <LI><

10px; MARGIN-BOTTOM: 10px">树中度为零的结点称为叶结点或终端结点。 <LI><

10px; MARGIN-BOTTOM: 10px">树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。例如在图1中，结点A，B和E的度分别为3，2，0。其中A为根结点,B为内部结点，E为叶结点，树的度为3。 <LI>如果存在树中的一个结点序列K1,K2,..,Kj，使得结点Ki是结点Ki+1的父结点(1≤i≤j)，则称该结点序列是树中从结点K1到结点Kj的一条路径或道路。我们称这条路径的长度为j-1，它是该路径所经过的边(即连接两个结点的线段)的数目。树中任一结点有一条到其自身的长度为零的路径。例如，在图1中，结点A到结点I有一条路径ABFI，它的长度为3。 <LI>如果在树中存在一条从结点K到结点M的路径，则称结点K是结点M的祖先，也称结点M是结点K的子孙或后裔。例如在图1中，结点F的祖先有A，B和F自己，而它的子孙包括它自己和I,J。注意，任一结点既是它自己的祖先也是它自己的子孙。 <LI>我们将树中一个结点的非自身祖先和子孙分别称为该结点的真祖先和真子孙。在一棵树中，树根是唯一没有真祖先的结点。叶结点是那些没有真子孙的结点。子树是树中某一结点及其所有真子孙组成的一棵树。 <LI>树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径的长度。树的高度是指根结点的高度。例如图1中的结点B，C和D的高度分别为2，0和1，而树的高度与结点A的高度相同为3。 <LI>从树根到任一结点n有唯一的一条路径，我们称这条路径的长度为结点n的深度或层数。根结点的深度为0，其余结点的深度为其父结点的深度加1。深度相同的结点属于同一层。例如，在图1中，结点A的深度为0；结点B，C和D的深度为1；结点E，F，G，H的深度为2；结点I和J的深度为3。在树的第二层的结点有E，F，J和H，树的第0层只有一个根结点A。 <LI>树的定义在某些结点之间确定了父子关系，我们又将这种关系延拓为祖先子孙关系。但是树中的许多结点之间仍然没有这种关系。例如兄弟结点之间就没有祖先子孙关系。如果我们在树的每一组兄弟结点之间定义一个从左到右的次序，则得到一棵有序树；否则称为无序树。设结点n的所有儿子按其从左到右的次序排列为n1,n2,..,nk，则我们称n1是n的最左儿子，或简称左儿子，并称ni是ni-1的右邻兄弟，或简称右兄弟(i=2,3,..k)。图2中的两棵树作为无序树是相同的，但作为有序树是不同的，因为结点a的两个儿子在两棵树中的左右次序是不同的。后面，我们只关心有序树，因为无序树总可能转化为有序树加以研究。<img src="http://algorithm.myrice.com/datastructure/basic/tree/images/img1.gif">图2 两棵不同的有序树我们还可以将兄弟结点之间的左右次序关系加以延拓：如果a与b是兄弟，并且a在b的左边，则认为a的任一子孙都在b的任一子孙的左边。 <LI>森林是m(m>0)棵互不相交的树的集合。如果我们删去一棵树的树根，留下的子树就构成了一个森林。当我们删去的是一棵有序树的树根时，留下的子树也是有序的，这些树组成一个树表。在这种情况下，称这些树组成的森林为有序森林或果园。 <LI>在讨论表的时候，我们对表的每一位置的元素赋予一个元素值。这里，我们也用树的结点来存储元素，即对于树中的每一个结点赋予一个标号，这个标号并不是该结点的名称，而是存储于该结点的一个值。结点的名称总是不变的，而它的标号是可以改变的。我们可以做这样的类比：树：表 = 标号：元素 = 结点：位置</LI></OL>

b · 发表于 2004-5-29 04:26:36

<H2>树的数学定义</H2>
<

>连通无回路的无向图称为无向树，简称树。若该无向图至少含有两个连通分支，则称为森林。
<

>在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支点。
<

>设D是有向图，若D的基图是无向树，则称D为有向树。
设T是n(n≥2)阶有向树，若T中有一个顶点的入度为0，其余顶点的入度均为1，则称T为根树。入度为0的顶点称为树根，入度为1出度为0的顶点称为树叶，入度为1出度不为0的顶点称为内点，内点和树根统称为分支点。从树根到T的任意顶点v的通路（路径）长度称为v的层数，层数最大顶点的层数称为树高。将平凡树也称为根树。
<BLOCKQUOTE>
<HR align=left color=#808080 noShade SIZE=4>

注意：在计算机学中所讨论的树和纯粹数学中的树有所不同。事实上，计算机学中的树就是离散数学中的根树。
<HR align=left color=#808080 noShade SIZE=4>
</BLOCKQUOTE>

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

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

>树的最重要的作用之一是用以实现各种各样的抽象数据类型。与<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter1.htm" target="_blank" >表</A>的情形相同，定义在树上的操作也是多种多样的。在这里我们只考虑作为抽象数据类型的树的几种典型操作。<

>以下的∧表示空结点，∧在树的不同实现方法中有不同的定义。<BLOCKQUOTE><

align=center>ADT树的基本运算</BLOCKQUOTE><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>Parent(v,T)</TD><TD 10pt" width="58%" bgColor=#e0e0e0>这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为∧，表示结点v没有父结点。</TD></TR><TR><TD 10pt" width="42%" bgColor=#e0e0e0>Leftmost_Child(v,T)</TD><TD 10pt" width="58%" bgColor=#e0e0e0>这是一个求最左儿子结点的函数。函数值为树T中结点v的最左儿子。当v是叶结点时，函数值为∧，表示结点v没有儿子。</TD></TR><TR><TD 10pt" width="42%" bgColor=#e0e0e0>Right_Sibling(v,T)</TD><TD 10pt" width="58%" bgColor=#e0e0e0>这是一个求右邻兄弟的函数，函数值为树T中结点v的右邻兄弟。当v没有右邻兄弟时，函数值为∧。</TD></TR><TR><TD 10pt" width="42%" bgColor=#e0e0e0>Create(i,x,T1,T2,..,Ti,T)</TD><TD 10pt" width="58%" bgColor=#e0e0e0>这是一族建树过程。对于每一个非负整数i，该函数生成一棵新树T，T的根结点是标号为x的新结点v，并令v有i个儿子，这些儿子从左到右分别为树T1,T2,..,Ti的根。当i=0时，v既是树根，又是树叶。</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:27:30

<H2>树的遍历</H2><

>树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的系统的访问，即依次对树中每个结点访问一次且仅访问一次。树的3种最重要的遍历方式分别称为前序遍历、中序遍历和后序遍历。以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表，中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。<

>树的这3种遍历方式可递归地定义如下：<UL><LI><

5px; MARGIN-BOTTOM: 5px">如果T是一棵空树，那么对T进行前序遍历、中序遍历和后序遍历都是空操作，得到的列表为空表。 <LI>如果T是一棵单结点树，那么对T进行前序遍历、中序遍历和后序遍历都只访问这个结点。这个结点本身就是要得到的相应列表。 <LI>否则，设T如图6所示，它以n为树根，树根的子树从左到右依次为T1,T2,..,Tk，那么有： <OL><LI>对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。 <LI>对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T2,..,Tk进行中序遍历。 <LI>对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n。 </LI></OL></LI></UL><img src="http://algorithm.myrice.com/datastructure/basic/tree/images/img9.gif">图6 树T前序遍历和中序遍历可形式地依次描述如下三种遍历可以形式地描述如下，其中用到了<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter4.htm" target="_blank" >树的ADT操作</A>：<DIV align=center><CENTER><TABLE 10pt" cellPadding=5 width="90%" border=0><TR><TD width="100%" bgColor=#e0e0e0>Procedure Preorder_Traversal(v:NodeType); {前序遍历算法}begin Visite(v); {访问节点v} i:=Leftmost_Child(v); while i<>∧ do begin Preorder_Traversal(i);{从左到右依次访问v的每一个儿子节点i} i:=Right_Sibling(i); end;end; </TD></TR><TR><TD width="100%" bgColor=#e0e0e0>Procedure Inorder_Traversal(v:NodeType); {中序遍历算法}beginif Leftmost_Child(v)=∧ {判断v是否是叶节点} then Visite(v) else begin Inorder_Traversal(Leftmost_Child(v)); {中序遍历v的左边第一个儿子节点} Visite(v); {访问节点v} i:=Right_Sibling(Leftmost_Child(v)); {i=v的左边第二个儿子} while i<>∧ do begin Inorder_Traversal(i); {从左边第二个开始到最右边一个为止依次访问v的每一个儿子节点i} i:=Right_Sibling(i); end; end;end; </TD></TR><TR><TD width="100%" bgColor=#e0e0e0>Procedure Postorder_Traversal(v:NodeType); {后序遍历算法}begin i:=Leftmost_Child(v); while i<>∧ do begin Preorder_Traversal(i);{从左到右依次访问v的每一个儿子节点i} i:=Right_Sibling(i); end; Visite(v); {访问节点v}end; </TD></TR></TABLE></CENTER></DIV>为了将一棵树中所有结点按某种次序列表，只须对树根调用相应过程。例如对图7中的树进行前序遍历、中序遍历和后序遍历将分别得到前序列表：A B E F I J C D G H；中序列表：E B I F J A C G D H；后序列表：E I J F B C G H D A。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/tree/images/img4.gif">图7 一棵树</BLOCKQUOTE> 下面介绍一种方法可以产生上述3种遍历方式的结点列表。设想我们从树根出发，依逆时针方向沿树的外缘绕行(例如围绕图7中的树绕行的路线如图8所示)。绕行途中可能多次经过同一结点。如果我们按第一次经过的时间次序将各个结点列表，就可以得到前序列表；如果按最后一次经过的时间次序列表，也就是在即将离开某一结点走向其父亲时将该结点列出，就得到后序列表。为了产生中序列表，要将叶结点与内部结点加以区别。叶结点在第一次经过时列出，而内部结点在第二次经过时列出。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/tree/images/img10.gif">图8 树的遍历</BLOCKQUOTE>在上述3种不同次序的列表方式中，各树叶之间的相对次序是相同的，它们都按树叶之间从左到右的次序排列。3种列表方式的差别仅在于内部结点之间以及内部结点与树叶之间的次序有所不同。对一棵树进行前序列表或后序列表有助于查询结点间的祖先子孙关系。假设结点v在后序列表中的序号(整数)为postorder(v)，我们称这个整数为结点v的后序编号。例如在图7中，结点E，I和J的后序编号分别为1，2和3。结点的后序编号具有这样的特点：设结点v的真子孙个数为desc(v)，那么在以v为根的子树中的所有结点的后序编号恰好落在postorder(v)-desc(v)与postorder(v)之间。因此为了检验结点x是否为结点y的子孙，我们只要判断它们的后序编号是否满足：<BLOCKQUOTE><BLOCKQUOTE>postorder(y)-desc(y)≤postorder(x)≤postorder(y)</BLOCKQUOTE></BLOCKQUOTE> 前序编号也具有类似的性质

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

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

>本节介绍实现树的几种基本方法，并讨论这些方法对于各种树操作的效率。虽然各种表示法都有其优点，但是我们还是推荐使用最后一种<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter6_3.htm" target="_blank" >左儿子右兄弟表示法</A>来表示树。<UL><LI><a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter6_1.htm" target="_blank" >父亲数组表示法</A> <LI><a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter6_2.htm" target="_blank" >儿子链表表示法</A> <LI><a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter6_3.htm" target="_blank" >左儿子右兄弟表示法</A> </LI></UL>

b · 发表于 2004-5-29 04:28:05

<H3>父亲数组表示法</H3><

>设T是一棵树，表示T的一种最简单的方法是用一个一维数组存储每个结点，数组的下标就是结点的位置指针，每个结点中有一个指向各自的父亲结点的数组下标的域，这样可使Parent操作非常方便。类型定义如下：<BLOCKQUOTE><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=integer; {结点的位置类型为整型} NodeType=Record Label

abelType; {该结点的标号} Parent:TPosition; {该结点的父亲的数组下标,对于根结点该域为0} End; TreeType=Record NodeCount:integer; {树的结点的总数目} Node:Array [1..MaxNodeCount] of NodeType;{存储树的结点} End; </TD></TR></TABLE></CENTER></DIV></BLOCKQUOTE>由于树中每个结点的父亲是唯一的，所以上述的父亲数组表示法可以唯一地表示任何一棵树。在这种表示法下，寻找一个结点的父结点只需要O(1)时间。在树中可以从一个结点出发找出一条向上延伸到达其祖先的道路，即从一个结点到其父亲，再到其祖父等等。求这样的道路所需的时间正比于道路上结点的个数。在树的父亲数组表示法中，对于涉及查询儿子和兄弟信息的树操作，可能要遍历整个数组。为了节省查询时间，可以规定指示儿子的数组下标值大于父亲的数组下标值，而指示兄弟结点的数组下标值随着兄弟的从左到右是递增的。<BLOCKQUOTE>父亲数组实现的ADT树操作<DIV align=center><CENTER><TABLE 10pt" cellPadding=5 width="90%" border=0><TR><TD width="100%" bgColor=#e0e0e0>函数 Parent(v,T)功能<BLOCKQUOTE>这是一个求父结点的函数，函数值为树T中标号为v的结点的父亲。当v是根结点时，函数值为0，表示结点v没有父结点。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Parent(v:TPosition;var T:TreeType):TPosition；begin return(T.Node[v].Parent);end;</BLOCKQUOTE>说明<BLOCKQUOTE>由于每个结点都有一个域存储了其父亲结点的标号(数组下标)，因此Parent操作实现非常简单。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Leftmost_Child(v,T)功能<BLOCKQUOTE>这是一个求最左儿子结点的函数。函数值为树T中标号为v的结点的最左儿子。当v是叶结点时，函数值为0，表示结点v没有儿子。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Leftmost_Child(v:TPosition;var T:TreeType):TPosition;begin i:=v+1; while (i<=T.NodeCount)and(T.Node.Parent<>v) do inc(i); if i=T.NodeCount+1 then return(0) else return(i);end;</BLOCKQUOTE>说明<BLOCKQUOTE>因为没有保存每个结点的子结点的信息，因此只能依次扫描每个结点，根据我们的约定，子结点一定排在父结点的后面，且兄弟结点的下标从左到右依次递增，因此第一次遇到的父亲是n的结点就是n的最左结点。</BLOCKQUOTE>复杂性<BLOCKQUOTE>该算法的复杂性取决于while循环。若设T.NodeCount=n，显然，在最坏情况下循环执行n-v次，最好情况下执行1次，平均情况下执行<img src="http://algorithm.myrice.com/datastructure/basic/tree/images/img2.gif">(n-v)/2<img src="http://algorithm.myrice.com/datastructure/basic/tree/images/img3.gif">，所以无论何种情况下，复杂性都为O(n)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Right_Sibling(v,T)功能<BLOCKQUOTE>这是一个求右邻兄弟的函数，函数值为树T中结点v的右邻兄弟。当v没有右邻兄弟时，函数值为0。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Right_Sibling(v:TPosition;var T:TreeType):TPosition;begin i:=v+1; while (i<=T.NodeCount)and(T.Node.Parent<>T.Node[v].Parent) do inc(i); if i=T.NodeCount+1 then return(0) else return(i);end;</BLOCKQUOTE>说明<BLOCKQUOTE>依次搜索排在v之后的结点，遇到第一个与v有相同父结点的结点就是v的右邻兄弟。</BLOCKQUOTE>复杂性<BLOCKQUOTE>同Leftmost_Child一样，该函数复杂性为O(n)，其中n为树的总结点数。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Create(i,x,T1,T2,..,Ti)功能<BLOCKQUOTE>这是一族建树过程。对于每一个非负整数i，该函数生成一棵新树T，T的根结点是标号为x的新结点v，并令v有i个儿子，这些儿子从左到右分别为树T1,T2,..,Ti的根。当i=0时，v既是树根，又是树叶。</BLOCKQUOTE>实现<BLOCKQUOTE>Procedure Create(i:integer;var xabelType;var T1,T2,..,Ti,T:TreeType);vark,j,father:integer;begin with T do begin NodeCount:=1; Node[1].Label:=x; Node[1].Parent:=0; {生成根结点} for k:=1 to i do if Tk.NodeCount<>0 then begin inc(NodeCount); Node[NodeCount]:=Tk.Node[1]; Node[NodeCount].Parent:=1;{修改Tk的根结点的父亲使其指向T的根} father:=NodeCount; {记下Tk的根结点的标号} for j:=2 to Tk.NodeCount do beign inc(NodeCount); Node[NodeCount]:=Tk.Node[j]; Node[NodeCount].Parent:=Node[NodeCount].Parent+father-1; {修改Tk的每一个非根结点的父亲，因为Tk的根结点的位置改变了} end; end; end;end;</BLOCKQUOTE>说明<BLOCKQUOTE>这个过程首先生成一个新结点，其中存储的数据为x，新结点在数组T的第一个元素位置上；然后对于每一个Tk，1≤k≤i，如果Tk不为空则将Tk的每一个结点复制到T中，同时修改Tk的每一个元素的父结点，因为Tk的根结点在T中的下标已经不是1了，而是father，因此Tk的每一个元素的父结点的下标都应给增加一个增量father-1。</BLOCKQUOTE>复杂性<BLOCKQUOTE>如果∑(Tk的结点数)=n，即生成的新树的结点总数为n，则复杂性为O(n)。</BLOCKQUOTE></TD></TR></TABLE></CENTER></DIV></BLOCKQUOTE>Label,Root和MakeNull比较简单，这里就不一一实现了。我们可以看出，用父亲数组实现树，比较容易实现Parent运算，但是对于Leftmost_Child和Right_Sibling则效率不高，而且这种实现方法很占用内存。但实现上比较简单

b · 发表于 2004-5-29 04:28:52

<H3>儿子链表表示法</H3><

>树的另一种常用的表示方法就是儿子链表表示法。这种表示法用一个<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter1.htm" target="_blank" >线性表</A>来存储树的所有结点信息，称为结点表。对每个结点建立一个儿子表。儿子表中只存储儿子结点的地址信息，可以是指针，数组下标甚至内存地址。由于每个结点的儿子数目不定，因此儿子表常用单链表来实现，因此这种表示法称为儿子链表表示法。这种实现法与图的邻接表表示法类似。下图是一个儿子链表表示法的示意图。<BLOCKQUOTE><

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

align=center>图3 树的儿子链表实现</BLOCKQUOTE>图3中儿子链表结构表示的树如图4所示，树中各结点存放于一个<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter3_1.htm" target="_blank" >数组实现的表</A>中，数组下标作为各结点的指针。每一个数组元素（即每一个结点）含有一个儿子表，在图3中儿子表是<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter3_2.htm" target="_blank" >用单链表来实现</A>的，当然也可以用其他<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter3.htm" target="_blank" >表的实现方式</A>来实现儿子表，比如说<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter3_3.htm" target="_blank" >游标方式(静态链表)</A>。但由于每个结点的儿子数目不确定，所以一般不用数组来实现儿子表，但可以用数组来实现结点表，就如图3所示。在图3中可以看到，位于结点表第一个位置的结点(未必是根结点)有两个儿子结点，从左到右的两个儿子结点分别位于结点表的第2和第3个位置。因为图3中的结点表用数组实现，所以结点的标号就是结点在结点表中的数组下标。如图4所示。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/tree/images/img5.gif">图4 图3中儿子链表所表示的树</BLOCKQUOTE>为了指明树的根结点的位置，我们可以用一个变量Root记录根结点在结点表中的位置。有了根结点的位置，就可以利用儿子表依次找到树中所有的结点。儿子链表表示的树的类型定义如下：<DIV align=center><CENTER><TABLE 10pt" cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">Type{======================NodeListType是一个元素为NodeType类型的线性表，其位置类型为TPosition，NodeListType定义了结点表的类型；ChildrenListType是一个元素为TPosition类型的线性表， ChildrenListType定义了儿子表的类型=======================}TPosition=....ChildrenListType=...NodeType=Record {结点的类型} Label

abelType; {结点的标号} Children:ChildrenListType;{结点的儿子表} End;NodeListType=...TreeType=record root:TPosition; {记录树根在结点表中的位置} Node:NodeListType; {结点表} end; </TD></TR></TABLE></CENTER></DIV> 其中NodeListType是一个元素为NodeType类型的线性表，其位置类型为TPosition，NodeListType定义了结点表的类型；ChildrenListType是一个元素为TPosition类型的线性表， ChildrenListType定义了儿子表的类型。以上类型定义并不考虑表的具体实现方式，如果假设结点表和儿子表都用单链表实现，则类型定义可以具体实现如下：<DIV align=center><CENTER><TABLE 10pt" cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">{儿子链表实现树的类型定义的一个具体实例，结点表和儿子表都用单链表实现}TypeTPosition=^NodeType; {结点表的位置类型}ChildrenNodeType=record {儿子表的结点项的类型} child:TPosition; {指向儿子结点的位置指针} next:^ChildrenNodeType; {指向下一个儿子表项的指针} end;NodeType=Record {结点的类型定义为单链表} Label

abelType; {结点的标号} Children:^ChildrenNodeType;{指向儿子表的指针} Next:TPosition; End;TreeType=^NodeType; {树的类型定义为结点指针类型} </TD></TR></TABLE></CENTER></DIV>注意以上的定义只是一种具体情况，实际应用中结点表和儿子表可能用数组、链表等任何一种表的实现方式实现。下面我们就讨论结点表和儿子表都用链表实现的儿子链表的ADT操作的实现，之所以用单链表实现结点表和儿子表，是因为这样可以使ADT树的实现较为简洁和高效。至于结点表和儿子表的其他实现方式，可以类似地实现。<BLOCKQUOTE>儿子链表实现的ADT树操作</BLOCKQUOTE><DIV align=center><CENTER><TABLE cellPadding=5 width="90%" border=0><TR><TD width="100%" bgColor=#e0e0e0>函数 Leftmost_Child(v,T)功能<BLOCKQUOTE>这是一个求最左儿子结点的函数。函数值为树T中结点v的最左儿子的位置。当v是叶结点时，函数值为nil，表示结点v没有儿子。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Leftmost_Child(v:TPosition;var T:TreeType):TPosition;begin return(v^.Children);end;</BLOCKQUOTE>说明<BLOCKQUOTE>返回v的儿子表的第一个位置的元素，就是v的最左儿子的位置指针，若v的儿子表为空则返回空结点nil。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Right_Sibling(v,T)功能<BLOCKQUOTE>这是一个求右邻兄弟的函数，函数值为树T中结点v的右邻兄弟。当v没有右邻兄弟时，函数值为nil。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Right_Sibling(v:TPosition;var T:TreeType):TPosition;vari:TPosition;k:^ChildrenNodeType;Find:Boolean;begin i:=T; {i指向T的第一个结点} Find:=false; while (i<>nil)and(not Find) do begin k:=Locate(v,i^.Children); {在结点i的儿子表中定位结点v} if k<>nil then Find:=true; {如果在i的儿子表中找到结点v则Find=true;} i:=i^.next; end; if (Find)and(k^.next<>nil) {如果找到v在某个结点的儿子表中的位置 并且v不是该结点的儿子表的最后一个元素} then return(k^.next^.child) {则返回v的右邻兄弟的指针} else return(nil);{否则返回空指针}end;</BLOCKQUOTE>说明<BLOCKQUOTE>由于儿子链表只保存各个结点的儿子的信息，没有保存兄弟和父亲的信息，因此在查找v的兄弟时，必须先找到v的父亲结点，然后再找到v在父亲结点的儿子表中的位置，才能得到v的右邻兄弟。</BLOCKQUOTE>复杂性<BLOCKQUOTE>假设树有n个结点，在最坏情况下，结点v恰好是树的根结点，则循环要找遍T的所有结点，因此复杂性为O(n)；在最好情况下，第一次循环就可以找到v的兄弟，因此最好情况下复杂性为O(1)；平均情况下复杂性可以证明（证略）为O(n/2)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Parent(v,T)功能<BLOCKQUOTE>这是一个求父结点的函数，函数值为树T中结点v的父亲在结点表中的位置。当v是根结点时，函数值为nil，表示结点v没有父结点。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Parent(v:TPosition;var T:TreeType):TPosition；vari:TPosition;k:^ChildrenNodeType;Find:Boolean;begin i:=T; {i指向T的第一个结点} Find:=false; while (i<>nil)and(not Find) do begin k:=Locate(v,i^.Children); {在结点i的儿子表中定位结点v} if k<>nil then Find:=true else i:=i^.next; {如果在i的儿子表中找到结点v则Find=true否则i:=i^.next} end; if Find then return(i) {则返回v的父亲的指针} else return(nil);{否则返回空指针}end;</BLOCKQUOTE>说明<BLOCKQUOTE>由于儿子链表只保存各个结点的儿子的信息，没有保存父亲的信息，因此在查找v的父亲时，必须依次扫描结点表，找到儿子表中含有结点v的结点。</BLOCKQUOTE>复杂性<BLOCKQUOTE>同Right_Sibling一样，最好情况为O(1)，最坏情况为O(n)，平均情况为O(n/2)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Create(i,v,T1,T2,..,Ti)功能<BLOCKQUOTE>这是一族建树过程。对于每一个非负整数i，该函数生成一个新树T，T的根结点v的标号为x，并令v有i个儿子，这些儿子从左到右分别为树T1,T2,..,Ti的根。当i=0时，v既是树根，又是树叶。</BLOCKQUOTE>实现<BLOCKQUOTE>Procedure Create(i:integer;var x

abelType;var T1,T2,..,Ti,T:TreeType);vark:integer;p:TPosition;tmp:^ChildrenNodeType;begin new(T);T^.Label:=x;T^.children:=nil;T^.next:=nil; {建立新树的根结点}p:=T; {p指向链表T的最后一个结点}for k:=i downto 1 do {用downto是为了保持子树Tk从左到右的顺序} if Tk<>nil then {如果子树Tk不为空} begin p^.next:=Tk;{将链表Tk接在链表T之后} while p^.next<>nil do p:=p^.next; {p指向链表T的最后一个结点} new(tmp); tmp^.child:=Tk; tmp^.next:=T^.children; {建立一个新的儿子表项} T^.children:=tmp; {将Tk的根结点在T中的位置插入T的根结点的儿子表的首部} end;end;</BLOCKQUOTE>说明<BLOCKQUOTE>这个过程首先生成新树的根结点，其标号为x；然后对于每一个Tk，1≤k≤i，如果Tk不为空则将Tk的根结点链接到T的后面，为了实现这一步，可以设置一个指针p，p始终指向T的最后一个结点。然后将每个Tk加入到T的根结点的儿子表中。for循环用的是downto，是因为后面将Tk的根结点插入到T的根的儿子表的第一个位置上，因此只有从右向左插入Tk才可以保持子树从左到右的顺序。</BLOCKQUOTE>复杂性<BLOCKQUOTE>如果∑(Tk的结点数)=n，即生成的新树的结点总数为n，则复杂性显然为O(n)。</BLOCKQUOTE>　 </TD></TR></TABLE></CENTER></DIV>Label,Root和MakeNull比较简单，这里就不一一实现了

b · 发表于 2004-5-29 04:29:50

<H3>左儿子右兄弟表示法</H3><

>树的左儿子右兄弟表示法又称为二叉树表示法或二叉链表表示法。每个结点除了data域外，还含有两个域，分别指向该结点的最左儿子和右邻兄弟。这种表示法常用二叉链表实现，因此又称为二叉链表表示法。但是实际应用中常用游标(静态链表)来代替链表，请参见<a href="http://algorithm.myrice.com/datastructure/basic/list/chapter3_3.htm" target="_blank" >表的游标实现</A>。<

>若用指针实现，其类型定义为：<DIV align=center><CENTER><TABLE 10pt" cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%"><

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

abelType; Leftmost_Child,Right_Sibling: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%">Type TPosition=integer; NodeType=record Label

abelType; Leftmost_Child,Right_Sibling:TPosition; end; CellspaceType=array [1..MaxNodeCount] of NodeType; TreeType=TPosition;var Cellspace:CellspaceType; Tree:TreeType; </TD></TR></TABLE></CENTER></DIV>此时树类型TreeType是整数类型，它指示树根在cellspace中的游标。例如图5(a)中树的左儿子右兄弟表示法的指针和游标实现分别如图5(b)和(c)所示。<img src="http://algorithm.myrice.com/datastructure/basic/tree/images/img7.gif">(a)<img src="http://algorithm.myrice.com/datastructure/basic/tree/images/img8.gif">(b)<img src="http://algorithm.myrice.com/datastructure/basic/tree/images/img6.gif">(c)图5 树的左儿子右兄弟表示法
用树的左儿子右兄弟表示法可以直接实现树的大部分操作，只有在对树结点作Parent操作时需遍历树。如果要反复执行Parent操作，可在结点记录中再开辟一个指向父结点的指针域，也可以利用最右儿子单元中的Right_Sibling作为指向父结点的指针(否则这里总是空指针)。当执行Parent(v)时，可以先通过Right_Sibling逐步找出结点v的最右兄弟，再通过最右兄弟的Right_Sibling(父亲指针)找到父结点。这个结点就是结点v的父亲。在这样的表示法下，求一个结点的父亲所需要的时间正比于该结点右边的兄弟个数。不过，这时每个记录中需要多用一位(bit)空间，用以标明该记录中的right_sibling是指向右邻兄弟还是指向父亲。考虑到对于现在的计算机，内存已经不是很重要的限制因素了。我们下面就采取增加一个parent域的方案，以改进左儿子右兄弟表示法中Parent操作的效率。因此重新定义树的类型如下：若用指针实现，其类型定义为：<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">Type TPosition=^NodeType; NodeType=record Label

abelType; Parent,Leftmost_Child,Right_Sibling:TPosition; {增加一个Parent域} end; TreeType=TPosition;var Tree:TreeType; </TD></TR></TABLE></CENTER></DIV>若用游标实现，其类型定义为:<DIV align=center><CENTER><TABLE cellPadding=5 width="90%" bgColor=#e0e0e0 border=0><TR><TD width="100%">Type TPosition=integer; NodeType=record Label:LabelType; Parent,Leftmost_Child,Right_Sibling:TPosition; {增加一个Parent域} end; CellspaceType=array [1..MaxNodeCount] of NodeType; TreeType=TPosition;var Cellspace:CellspaceType; Tree:TreeType; </TD></TR></TABLE></CENTER></DIV>下面我们只针对上面的指针实现方案实现树的ADT操作。对于指针实现的树，空结点∧表示空指针nil。对于浮标实现的树，可以类似地实现下面的操作。<BLOCKQUOTE>指针实现的左儿子右兄弟表示法实现的ADT树操作</BLOCKQUOTE><DIV align=center><CENTER><TABLE 10pt" cellPadding=5 width="90%" border=0><TR><TD width="100%" bgColor=#e0e0e0>函数 Leftmost_Child(v,T)功能<BLOCKQUOTE>这是一个求最左儿子结点的函数。函数值为树T中结点v的最左儿子的位置。当v是叶结点时，函数值为nil，表示结点v没有儿子。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Leftmost_Child(v:TPosition;var T:TreeType):TPosition;begin return(v^.Leftmost_Child);end;</BLOCKQUOTE>说明<BLOCKQUOTE>返回v的最左儿子的位置指针。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Right_Sibling(v,T)功能<BLOCKQUOTE>这是一个求右邻兄弟的函数，函数值为树T中结点v的右邻兄弟。当v没有右邻兄弟时，函数值为nil。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Right_Sibling(v:TPosition;var T:TreeType):TPosition;begin return(v^.Right_Sibling);end;</BLOCKQUOTE>说明<BLOCKQUOTE>返回v的右邻兄弟的位置指针。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Parent(v,T)功能<BLOCKQUOTE>这是一个求父结点的函数，函数值为树T中结点v的父亲在结点表中的位置。当v是根结点时，函数值为nil，表示结点v没有父结点。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Parent(v:TPosition;var T:TreeType):TPosition;begin return(v^.Parent);end;</BLOCKQUOTE>说明<BLOCKQUOTE>返回v的父结点的位置指针。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(1)。</BLOCKQUOTE></TD></TR><TR><TD width="100%" bgColor=#e0e0e0>函数 Create(i,x,T1,T2,..,Ti)功能<BLOCKQUOTE>这是一族建树过程。对于每一个非负整数i，该函数生成一个新树T，T的根结点v的标号为x，并令v有i个儿子，这些儿子从左到右分别为树T1,T2,..,Ti的根。当i=0时，v既是树根，又是树叶。</BLOCKQUOTE>实现<BLOCKQUOTE>Function Create(i:integer;var x:LabelType;var T1,T2,..,Ti,T:TreeType);begin New(T); {建T的根结点} T^.Label:=x; T^.Parent:=nil; T^.Right_Sibling:=nil; if i>0 then begin T^.Leftmost_Child:=T1; for k:=1 to i do begin Tk^.Parent:=T; if kk^.Right_Sibling:=Tk+1 else Tk^.Right_Sibling:=nil; end; end;end;</BLOCKQUOTE>说明<BLOCKQUOTE>这个过程首先生成新树的根结点，其中存储的数据为x；然后对于每一个Tk，1≤k≤i，将Tk的根结点的父亲指向T，将Tk的根结点的右兄弟指向Tk+1(对于k=i的Tk其右兄弟为nil)。这里我们假设输入的参数Tk<>nil，1≤k≤i。</BLOCKQUOTE>复杂性<BLOCKQUOTE>显然为O(i)。</BLOCKQUOTE></TD></TR></TABLE></CENTER></DIV>Label,Root和MakeNull比较简单，这里就不一一实现了。我们看到，用这种左儿子右兄弟表示法实现树，可以高效地实现树的ADT操作，缺点是占用了用来存储指针的空间。不过我们还是推荐用这种表示法来表示树

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

<H2>二叉树的定义</H2><

> 二叉树是一类非常重要的树形结构，它可以递归地定义如下：<

>二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。若用n,n1和n2分别表示T，u(1)和u(2)的结点数，则有n=1+n1+n2 。u(1)和u(2)有时分别称为T的第一和第二子树。<

>因此，二叉树的根可以有空的左子树或空的右子树，或者左、右子树均为空。二叉树有5种基本形态，如图1所示。<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img14.gif"><BLOCKQUOTE>图1 二叉树的5种基本形态(其中□表示空)</BLOCKQUOTE>在二叉树中，每个结点至多有两个儿子，并且有左、右之分。因此任一结点的儿子不外4种情况：没有儿子；只有一个左儿子；只有一个右儿子；有一个左儿子并且有一个右儿子。　注意：二叉树与<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter1.htm" target="_blank" >树</A>和<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter2.htm" target="_blank" >有序树</A>的区别二叉树与度数不超过2的树不同，与度数不超过2的有序树也不同。在有序树中，虽然一个结点的儿子之间是有左右次序的，但若该结点只有一个儿子时，就无须区分其左右次序。而在二叉树中，即使是一个儿子也有左右之分。例如图2中(a)和(b)是两棵不同的二叉树。虽然它们与图3中的普通树(作为无序树或有序树)很相似，但它们却不能等同于这棵普通的树。若将这3棵树均看作是有序树，则它们就是相同的了。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img24.gif">图2 两棵不同的二叉树<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img15.gif">图3 一棵普通的树</BLOCKQUOTE>由此可见，尽管二叉树与<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter1.htm" target="_blank" >树</A>有许多相似之处，但二叉树不是<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter1.htm" target="_blank" >树</A>的特殊情形

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

<H2>二叉树的数学性质</H2><

>二叉树具有以下的重要性质：<OL><LI>高度为h≥0的二叉树至少有h+1个结点； <LI>高度不超过h(≥0)的二叉树至多有2h+1-1个结点； <LI>含有n≥1个结点的二叉树的高度至多为n-1； <LI>含有n≥1个结点的二叉树的高度至少为<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img8.gif">logn<img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img9.gif">，因此其高度为Ω(logn)。 </LI></OL><

>具有n个结点的不同形态的二叉树的数目在一些涉及二叉树的平均情况复杂性分析中是很有用的。设Bn是含有n个结点的不同二叉树的数目。由于二叉树是递归地定义的，所以我们很自然地得到关于Bn的下面的递归方程：<BLOCKQUOTE><

><V:SHAPETYPE><V:STROKE joinstyle="miter"></V:STROKE><V:FORMULAS><V:F eqn="if lineDrawn pixelLineWidth 0"></V:F><V:F eqn="sum @0 1 0"></V:F><V:F eqn="sum 0 0 @1"></V:F><V:F eqn="prod @2 1 2"></V:F><V:F eqn="prod @3 21600 pixelWidth"></V:F><V:F eqn="prod @3 21600 pixelHeight"></V:F><V:F eqn="sum @0 0 1"></V:F><V:F eqn="prod @6 1 2"></V:F><V:F eqn="prod @7 21600 pixelWidth"></V:F><V:F eqn="sum @8 21600 0"></V:F><V:F eqn="prod @7 21600 pixelHeight"></V:F><V:F eqn="sum @10 21600 0"></V:F></V:FORMULAS><V

ATH extrusionok="f" gradientshapeok="t" connecttype="rect"></V

ATH><LOCK v:ext="edit" aspectratio="t"></LOCK></V:SHAPETYPE><V:SHAPE><V:IMAGEDATA></V:IMAGEDATA></V:SHAPE><img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img21.gif"> (1) </BLOCKQUOTE>即一棵具有n>1个结点的二叉树可以看成是由一个根结点、一棵具有i个结点的左子树和一棵具有n-i-1个结点的右子树所组成。(1)式的解是<V:SHAPETYPE> <V:STROKE joinstyle="miter"></V:STROKE><V:FORMULAS><V:F eqn="if lineDrawn pixelLineWidth 0"></V:F><V:F eqn="sum @0 1 0"></V:F><V:F eqn="sum 0 0 @1"></V:F><V:F eqn="prod @2 1 2"></V:F><V:F eqn="prod @3 21600 pixelWidth"></V:F><V:F eqn="prod @3 21600 pixelHeight"></V:F><V:F eqn="sum @0 0 1"></V:F><V:F eqn="prod @6 1 2"></V:F><V:F eqn="prod @7 21600 pixelWidth"></V:F><V:F eqn="sum @8 21600 0"></V:F><V:F eqn="prod @7 21600 pixelHeight"></V:F><V:F eqn="sum @10 21600 0"></V:F></V:FORMULAS><V

ATH extrusionok="f" gradientshapeok="t" connecttype="rect"></V:PATH><LOCK v:ext="edit" aspectratio="t"></LOCK></V:SHAPETYPE><V:SHAPE><V:IMAGEDATA></V:IMAGEDATA></V:SHAPE><BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img13.gif"> (2)</BLOCKQUOTE>即所谓的Catalan数。因此，当n=3时,B3=5。于是，含有3个结点的不同的二叉树有5棵，如图4所示。<BLOCKQUOTE><img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img16.gif">图4 含有3个结点的不同二叉树</BLOCKQUOTE>

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