树结构综述.doc

JSOI2009春季函授讲义（A1） 第 53 页 共 53 页树的结构树的定义 树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。我们可以形式地给出树的递归定义如下:1. 单个结点是一棵树，树根就是该结点本身。 2. 设T1,T2,.,Tk是树，它们的根结点分别为n1,n2,.,nk。用一个新结点n作为n1,n2,.,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,.,nk为一组兄弟结点，它们都是结点n的儿子结点。我们还称n1,n2,.,nk为结点n的子树。 空集合也是树，称为空树。空树中没有结点。一棵典型的树如图1所示：图1 树的层次结构由图1可以看出树的形状就像一棵现实中的树，只不过是倒过来的。树的相关术语1. 一个结点的儿子结点的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。 2. 树中度为零的结点称为叶结点或终端结点。 3. 树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。例如在图1中，结点A，B和E的度分别为3，2，0。其中A为根结点,B为内部结点，E为叶结点，树的度为3。 4. 如果存在树中的一个结点序列K1,K2,.,Kj，使得结点Ki是结点Ki+1的父结点(1ij)，则称该结点序列是树中从结点K1到结点Kj的一条路径或道路。我们称这条路径的长度为j-1，它是该路径所经过的边(即连接两个结点的线段)的数目。树中任一结点有一条到其自身的长度为零的路径。例如，在图1中，结点A到结点I有一条路径ABFI，它的长度为3。 5. 如果在树中存在一条从结点K到结点M的路径，则称结点K是结点M的祖先，也称结点M是结点K的子孙或后裔。例如在图1中，结点F的祖先有A，B和F自己，而它的子孙包括它自己和I,J。注意，任一结点既是它自己的祖先也是它自己的子孙。 6. 我们将树中一个结点的非自身祖先和子孙分别称为该结点的真祖先和真子孙。在一棵树中，树根是唯一没有真祖先的结点。叶结点是那些没有真子孙的结点。子树是树中某一结点及其所有真子孙组成的一棵树。 7. 树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径的长度。树的高度是指根结点的高度。例如图1中的结点B，C和D的高度分别为2，0和1，而树的高度与结点A的高度相同为3。 8. 从树根到任一结点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。 9. 树的定义在某些结点之间确定了父子关系，我们又将这种关系延拓为祖先子孙关系。但是树中的许多结点之间仍然没有这种关系。例如兄弟结点之间就没有祖先子孙关系。如果我们在树的每一组兄弟结点之间定义一个从左到右的次序，则得到一棵有序树；否则称为无序树。设结点n的所有儿子按其从左到右的次序排列为n1,n2,.,nk，则我们称n1是n的最左儿子，或简称左儿子，并称ni是ni-1的右邻兄弟，或简称右兄弟(i=2,3,.k)。图2中的两棵树作为无序树是相同的，但作为有序树是不同的，因为结点a的两个儿子在两棵树中的左右次序是不同的。后面，我们只关心有序树，因为无序树总可能转化为有序树加以研究。图2 两棵不同的有序树我们还可以将兄弟结点之间的左右次序关系加以延拓：如果a与b是兄弟，并且a在b的左边，则认为a的任一子孙都在b的任一子孙的左边。 10. 森林是m(m0)棵互不相交的树的集合。如果我们删去一棵树的树根，留下的子树就构成了一个森林。当我们删去的是一棵有序树的树根时，留下的子树也是有序的，这些树组成一个树表。在这种情况下，称这些树组成的森林为有序森林或果园。 11. 在讨论表的时候，我们对表的每一位置的元素赋予一个元素值。这里，我们也用树的结点来存储元素，即对于树中的每一个结点赋予一个标号，这个标号并不是该结点的名称，而是存储于该结点的一个值。结点的名称总是不变的，而它的标号是可以改变的。我们可以做这样的类比：树：表 = 标号：元素 = 结点：位置 树的数学定义连通无回路的无向图称为无向树，简称树。若该无向图至少含有两个连通分支，则称为森林。在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支点。设D是有向图，若D的基图是无向树，则称D为有向树。设T是n(n2)阶有向树，若T中有一个顶点的入度为0，其余顶点的入度均为1，则称T为根树。入度为0的顶点称为树根，入度为1出度为0的顶点称为树叶，入度为1出度不为0的顶点称为内点，内点和树根统称为分支点。从树根到T的任意顶点v的通路（路径）长度称为v的层数，层数最大顶点的层数称为树高。将平凡树也称为根树。注意：在计算机学中所讨论的树和纯粹数学中的树有所不同。事实上，计算机学中的树就是离散数学中的根树。ADT树的操作树的最重要的作用之一是用以实现各种各样的抽象数据类型。与表的情形相同，定义在树上的操作也是多种多样的。在这里我们只考虑作为抽象数据类型的树的几种典型操作。以下的表示空结点，在树的不同实现方法中有不同的定义。ADT树的基本运算运算含义Parent(v,T)这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为，表示结点v没有父结点。Leftmost_Child(v,T)这是一个求最左儿子结点的函数。函数值为树T中结点v的最左儿子。当v是叶结点时，函数值为，表示结点v没有儿子。Right_Sibling(v,T)这是一个求右邻兄弟的函数，函数值为树T中结点v的右邻兄弟。当v没有右邻兄弟时，函数值为。Create(i,x,T1,T2,.,Ti,T)这是一族建树过程。对于每一个非负整数i，该函数生成一棵新树T，T的根结点是标号为x的新结点v，并令v有i个儿子，这些儿子从左到右分别为树T1,T2,.,Ti的根。当i=0时，v既是树根，又是树叶。Label(v,T)这时一个求标号的函数，函数值就是结点v的标号。Root(T)这是一个求树根的函数，函数值为树T的根结点。当T是空树时，函数值为。MakeNull(T)这是一个过程，它使T成为一棵空树。树的遍历树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的系统的访问，即依次对树中每个结点访问一次且仅访问一次。树的3种最重要的遍历方式分别称为前序遍历、中序遍历和后序遍历。以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表，中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。树的这3种遍历方式可递归地定义如下： 如果T是一棵空树，那么对T进行前序遍历、中序遍历和后序遍历都是空操作，得到的列表为空表。 如果T是一棵单结点树，那么对T进行前序遍历、中序遍历和后序遍历都只访问这个结点。这个结点本身就是要得到的相应列表。 否则，设T如图6所示，它以n为树根，树根的子树从左到右依次为T1,T2,.,Tk，那么有： 对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,.,Tk。 对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T2,.,Tk进行中序遍历。 对T进行后序遍历是先依次对T1,T2,.,Tk进行后序遍历，最后访问树根n。 图6 树T前序遍历和中序遍历可形式地依次描述如下三种遍历可以形式地描述如下，其中用到了树的ADT操作：Procedure Preorder_Traversal(v:NodeType); 前序遍历算法beginVisite(v); 访问节点vi:=Leftmost_Child(v);while i do begin Preorder_Traversal(i);从左到右依次访问v的每一个儿子节点i i:=Right_Sibling(i); end;end; 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; Procedure Postorder_Traversal(v:NodeType); 后序遍历算法begini:=Leftmost_Child(v);while i do begin Preorder_Traversal(i);从左到右依次访问v的每一个儿子节点i i:=Right_Sibling(i); end; Visite(v); 访问节点vend; 为了将一棵树中所有结点按某种次序列表，只须对树根调用相应过程。例如对图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。图7 一棵树 下面介绍一种方法可以产生上述3种遍历方式的结点列表。设想我们从树根出发，依逆时针方向沿树的外缘绕行(例如围绕图7中的树绕行的路线如图8所示)。绕行途中可能多次经过同一结点。如果我们按第一次经过的时间次序将各个结点列表，就可以得到前序列表；如果按最后一次经过的时间次序列表，也就是在即将离开某一结点走向其父亲时将该结点列出，就得到后序列表。为了产生中序列表，要将叶结点与内部结点加以区别。叶结点在第一次经过时列出，而内部结点在第二次经过时列出。图8 树的遍历在上述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的子孙，我们只要判断它们的后序编号是否满足：postorder(y)-desc(y)postorder(x)postorder(y) 前序编号也具有类似的性质。树与森林本节及其以后内容可放在二叉树之后，即学完了二叉树的有关知识，再来看这些内容就比较容易些。本节首先介绍树的几种存储结构，既树的常用表示法，并讨论这些方法对于各种树操作的效率。虽然各种表示法都有其优点，但是我们还是推荐使用最后一种左儿子右兄弟表示法来表示树；然后简单介绍树和森林的二叉树表示；最后介绍树的几种常见的应用。父亲数组表示法设T是一棵树，表示T的一种最简单的方法是用一个一维数组存储每个结点，数组的下标就是结点的位置指针，每个结点中有一个指向各自的父亲结点的数组下标的域，这样可使Parent操作非常方便。类型定义如下：TypeTPosition=integer; 结点的位置类型为整型NodeType=Record Label:LabelType; 该结点的标号 Parent:TPosition; 该结点的父亲的数组下标,对于根结点该域为0 End;TreeType=Record NodeCount:integer; 树的结点的总数目 Node:Array 1.MaxNodeCount of NodeType;存储树的结点 End; 由于树中每个结点的父亲是唯一的，所以上述的父亲数组表示法可以唯一地表示任何一棵树。在这种表示法下，寻找一个结点的父结点只需要O(1)时间。在树中可以从一个结点出发找出一条向上延伸到达其祖先的道路，即从一个结点到其父亲，再到其祖父等等。求这样的道路所需的时间正比于道路上结点的个数。在树的父亲数组表示法中，对于涉及查询儿子和兄弟信息的树操作，可能要遍历整个数组。为了节省查询时间，可以规定指示儿子的数组下标值大于父亲的数组下标值，而指示兄弟结点的数组下标值随着兄弟的从左到右是递增的。父亲数组实现的ADT树操作函数 Parent(v,T)功能这是一个求父结点的函数，函数值为树T中标号为v的结点的父亲。当v是根结点时，函数值为0，表示结点v没有父结点。实现Function Parent(v:TPosition;var T:TreeType):TPosition；beginreturn(T.Nodev.Parent);end;说明由于每个结点都有一个域存储了其父亲结点的标号(数组下标)，因此Parent操作实现非常简单。复杂性显然为O(1)。函数 Leftmost_Child(v,T)功能这是一个求最左儿子结点的函数。函数值为树T中标号为v的结点的最左儿子。当v是叶结点时，函数值为0，表示结点v没有儿子。实现Function Leftmost_Child(v:TPosition;var T:TreeType):TPosition;begini:=v+1;while (i=T.NodeCount)and(T.Nodei.Parentv) do inc(i);if i=T.NodeCount+1 then return(0) else return(i);end;说明因为没有保存每个结点的子结点的信息，因此只能依次扫描每个结点，根据我们的约定，子结点一定排在父结点的后面，且兄弟结点的下标从左到右依次递增，因此第一次遇到的父亲是n的结点就是n的最左结点。复杂性该算法的复杂性取决于while循环。若设T.NodeCount=n，显然，在最坏情况下循环执行n-v次，最好情况下执行1次，平均情况下执行(n-v)/2，所以无论何种情况下，复杂性都为O(n)。函数 Right_Sibling(v,T)功能这是一个求右邻兄弟的函数，函数值为树T中结点v的右邻兄弟。当v没有右邻兄弟时，函数值为0。实现Function Right_Sibling(v:TPosition;var T:TreeType):TPosition;begini:=v+1;while (i=T.NodeCount)and(T.Nodei.ParentT.Nodev.Parent) do inc(i);if i=T.NodeCount+1 then return(0) else return(i);end;说明依次搜索排在v之后的结点，遇到第一个与v有相同父结点的结点就是v的右邻兄弟。复杂性同Leftmost_Child一样，该函数复杂性为O(n)，其中n为树的总结点数。函数 Create(i,x,T1,T2,.,Ti)功能这是一族建树过程。对于每一个非负整数i，该函数生成一棵新树T，T的根结点是标号为x的新结点v，并令v有i个儿子，这些儿子从左到右分别为树T1,T2,.,Ti的根。当i=0时，v既是树根，又是树叶。实现Procedure Create(i:integer;var x:LabelType;var T1,T2,.,Ti,T:TreeType);vark,j,father:integer;beginwith T dobeginNodeCount:=1;Node1.Label:=x;Node1.Parent:=0; 生成根结点for k:=1 to i do if Tk.NodeCount0 then begin inc(NodeCount); NodeNodeCount:=Tk.Node1; NodeNodeCount.Parent:=1;修改Tk的根结点的父亲使其指向T的根 father:=NodeCount; 记下Tk的根结点的标号 for j:=2 to Tk.NodeCount do beign inc(NodeCount); NodeNodeCount:=Tk.Nodej; NodeNodeCount.Parent:=NodeNodeCount.Parent+father-1; 修改Tk的每一个非根结点的父亲，因为Tk的根结点的位置改变了 end; end; end;end;说明这个过程首先生成一个新结点，其中存储的数据为x，新结点在数组T的第一个元素位置上；然后对于每一个Tk，1ki，如果Tk不为空则将Tk的每一个结点复制到T中，同时修改Tk的每一个元素的父结点，因为Tk的根结点在T中的下标已经不是1了，而是father，因此Tk的每一个元素的父结点的下标都应给增加一个增量father-1。复杂性如果(Tk的结点数)=n，即生成的新树的结点总数为n，则复杂性为O(n)。Label,Root和MakeNull比较简单，这里就不一一实现了。我们可以看出，用父亲数组实现树，比较容易实现Parent运算，但是对于Leftmost_Child和Right_Sibling则效率不高，而且这种实现方法很占用内存。但实现上比较简单。儿子链表表示法树的另一种常用的表示方法就是儿子链表表示法。这种表示法用一个线性表来存储树的所有结点信息，称为结点表。对每个结点建立一个儿子表。儿子表中只存储儿子结点的地址信息，可以是指针，数组下标甚至内存地址。由于每个结点的儿子数目不定，因此儿子表常用单链表来实现，因此这种表示法称为儿子链表表示法。这种实现法与图的邻接表表示法类似。下图是一个儿子链表表示法的示意图。图3 树的儿子链表实现图3中儿子链表结构表示的树如图4所示，树中各结点存放于一个数组实现的表中，数组下标作为各结点的指针。每一个数组元素（即每一个结点）含有一个儿子表，在图3中儿子表是用单链表来实现的，当然也可以用其他表的实现方式来实现儿子表，比如说游标方式(静态链表)。但由于每个结点的儿子数目不确定，所以一般不用数组来实现儿子表，但可以用数组来实现结点表，就如图3所示。在图3中可以看到，位于结点表第一个位置的结点(未必是根结点)有两个儿子结点，从左到右的两个儿子结点分别位于结点表的第2和第3个位置。因为图3中的结点表用数组实现，所以结点的标号就是结点在结点表中的数组下标。如图4所示。图4 图3中儿子链表所表示的树为了指明树的根结点的位置，我们可以用一个变量Root记录根结点在结点表中的位置。有了根结点的位置，就可以利用儿子表依次找到树中所有的结点。儿子链表表示的树的类型定义如下：Type=NodeListType是一个元素为NodeType类型的线性表，其位置类型为TPosition，NodeListType定义了结点表的类型；ChildrenListType是一个元素为TPosition类型的线性表，ChildrenListType定义了儿子表的类型=TPosition=.ChildrenListType=.NodeType=Record 结点的类型 Label:LabelType; 结点的标号 Children:ChildrenListType;结点的儿子表 End;NodeListType=.TreeType=record root:TPosition; 记录树根在结点表中的位置 Node:NodeListType; 结点表 end; 其中NodeListType是一个元素为NodeType类型的线性表，其位置类型为TPosition，NodeListType定义了结点表的类型；ChildrenListType是一个元素为TPosition类型的线性表，ChildrenListType定义了儿子表的类型。以上类型定义并不考虑表的具体实现方式，如果假设结点表和儿子表都用单链表实现，则类型定义可以具体实现如下：儿子链表实现树的类型定义的一个具体实例，结点表和儿子表都用单链表实现TypeTPosition=NodeType; 结点表的位置类型ChildrenNodeType=record 儿子表的结点项的类型 child:TPosition; 指向儿子结点的位置指针 next:ChildrenNodeType; 指向下一个儿子表项的指针 end;NodeType=Record 结点的类型定义为单链表 Label:LabelType; 结点的标号 Children:ChildrenNodeType;指向儿子表的指针 Next:TPosition; End;TreeType=NodeType; 树的类型定义为结点指针类型 注意以上的定义只是一种具体情况，实际应用中结点表和儿子表可能用数组、链表等任何一种表的实现方式实现。下面我们就讨论结点表和儿子表都用链表实现的儿子链表的ADT操作的实现，之所以用单链表实现结点表和儿子表，是因为这样可以使ADT树的实现较为简洁和高效。至于结点表和儿子表的其他实现方式，可以类似地实现。儿子链表实现的ADT树操作函数 Leftmost_Child(v,T)功能这是一个求最左儿子结点的函数。函数值为树T中结点v的最左儿子的位置。当v是叶结点时，函数值为nil，表示结点v没有儿子。实现Function Leftmost_Child(v:TPosition;var T:TreeType):TPosition;beginreturn(v.Children);end;说明返回v的儿子表的第一个位置的元素，就是v的最左儿子的位置指针，若v的儿子表为空则返回空结点nil。复杂性显然为O(1)。函数 Right_Sibling(v,T)功能这是一个求右邻兄弟的函数，函数值为树T中结点v的右邻兄弟。当v没有右邻兄弟时，函数值为nil。实现Function Right_Sibling(v:TPosition;var T:TreeType):TPosition;vari:TPosition;k:ChildrenNodeType;Find:Boolean;begini:=T; i指向T的第一个结点Find:=false;while (inil)and(not Find) do begin k:=Locate(v,i.Children); 在结点i的儿子表中定位结点v if knil then Find:=true; 如果在i的儿子表中找到结点v则Find=true; i:=i.next; end;if (Find)and(k.nextnil) 如果找到v在某个结点的儿子表中的位置 并且v不是该结点的儿子表的最后一个元素 then return(k.next.child) 则返回v的右邻兄弟的指针 else return(nil);否则返回空指针end;说明由于儿子链表只保存各个结点的儿子的信息，没有保存兄弟和父亲的信息，因此在查找v的兄弟时，必须先找到v的父亲结点，然后再找到v在父亲结点的儿子表中的位置，才能得到v的右邻兄弟。复杂性假设树有n个结点，在最坏情况下，结点v恰好是树的根结点，则循环要找遍T的所有结点，因此复杂性为O(n)；在最好情况下，第一次循环就可以找到v的兄弟，因此最好情况下复杂性为O(1)；平均情况下复杂性可以证明（证略）为O(n/2)。函数 Parent(v,T)功能这是一个求父结点的函数，函数值为树T中结点v的父亲在结点表中的位置。当v是根结点时，函数值为nil，表示结点v没有父结点。实现Function Parent(v:TPosition;var T:TreeType):TPosition；vari:TPosition;k:ChildrenNodeType;Find:Boolean;begini:=T; i指向T的第一个结点Find:=false;while (inil)and(not Find) do begin k:=Locate(v,i.Children); 在结点i的儿子表中定位结点v if knil 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;说明由于儿子链表只保存各个结点的儿子的信息，没有保存父亲的信息，因此在查找v的父亲时，必须依次扫描结点表，找到儿子表中含有结点v的结点。复杂性同Right_Sibling一样，最好情况为O(1)，最坏情况为O(n)，平均情况为O(n/2)。函数 Create(i,v,T1,T2,.,Ti)功能这是一族建树过程。对于每一个非负整数i，该函数生成一个新树T，T的根结点v的标号为x，并令v有i个儿子，这些儿子从左到右分别为树T1,T2,.,Ti的根。当i=0时，v既是树根，又是树叶。实现Procedure Create(i:integer;var x:LabelType;var T1,T2,.,Ti,T:TreeType);vark:integer;p:TPosition;tmp:ChildrenNodeType;beginnew(T);T.Label:=x;T.children:=nil;T.next:=nil; 建立新树的根结点p:=T; p指向链表T的最后一个结点for k:=i downto 1 do 用downto是为了保持子树Tk从左到右的顺序if Tknil then 如果子树Tk不为空 begin p.next:=Tk;将链表Tk接在链表T之后 while p.nextnil do p:=p.next; p指向链表T的最后一个结点 new(tmp); tmp.child:=Tk; tmp.next:=T.children; 建立一个新的儿子表项 T.children:=tmp; 将Tk的根结点在T中的位置插入T的根结点的儿子表的首部 end;end;说明这个过程首先生成新树的根结点，其标号为x；然后对于每一个Tk，1ki，如果Tk不为空则将Tk的根结点链接到T的后面，为了实现这一步，可以设置一个指针p，p始终指向T的最后一个结点。然后将每个Tk加入到T的根结点的儿子表中。for循环用的是downto，是因为后面将Tk的根结点插入到T的根的儿子表的第一个位置上，因此只有从右向左插入Tk才可以保持子树从左到右的顺序。复杂性如果(Tk的结点数)=n，即生成的新树的结点总数为n，则复杂性显然为O(n)。 Label,Root和MakeNull比较简单，这里就不一一实现了。左儿子右兄弟表示法树的左儿子右兄弟表示法又称为二叉树表示法或二叉链表表示法。每个结点除了data域外，还含有两个域，分别指向该结点的最左儿子和右邻兄弟。这种表示法常用二叉链表实现，因此又称为二叉链表表示法。但是实际应用中常用游标(静态链表)来代替链表，请参见表的游标实现。若用指针实现，其类型定义为：TypeTPosition=NodeType;NodeType=record Label:LabelType; Leftmost_Child,Right_Sibling:TPosition; end;TreeType=TPosition; 若用游标实现，其类型定义为:TypeTPosition=integer;NodeType=record Label:LabelType; Leftmost_Child,Right_Sibling:TPosition; end;CellspaceType=array 1.MaxNodeCount of NodeType;TreeType=TPosition;varCellspace:CellspaceType;Tree:TreeType; 此时树类型TreeType是整数类型，它指示树根在cellspace中的游标。例如图5(a)中树的左儿子右兄弟表示法的指针和游标实现分别如图5(b)和(c)所示。(a)(b)(c)图5 树的左儿子右兄弟表示法 用树的左儿子右兄弟表示法可以直接实现树的大部分操作，只有在对树结点作Parent操作时需遍历树。如果要反复执行Parent操作，可在结点记录中再开辟一个指向父结点的指针域，也可以利用最右儿子单元中的Right_Sibling作为指向父结点的指针(否则这里总是空指针)。当执行Parent(v)时，可以先通过Right_Sibling逐步找出结点v的最右兄弟，再通过最右兄弟的Right_Sibling(父亲指针)找到父结点。这个结点就是结点v的父亲。在这样的表示法下，求一个结点的父亲所需要的时间正比于该结点右边的兄弟个数。不过，这时每个记录中需要多用一位(bit)空间，用以标明该记录中的right_sibling是指向右邻兄弟还是指向父亲。考虑到对于现在的计算机，内存已经不是很重要的限制因素了。我们下面就采取增加一个parent域的方案，以改进左儿子右兄弟表示法中Parent操作的效率。因此重新定义树的类型如下：若用指针实现，其类型定义为：TypeTPosition=NodeType;NodeType=record Label:LabelType; Parent,Leftmost_Child,Right_Sibling:TPosition; 增加一个Parent域 end;TreeType=TPosition;varTree:TreeType; 若用游标实现，其类型定义为:TypeTPosition=integer;NodeType=record Label:LabelType; Parent,Leftmost_Child,Right_Sibling:TPosition; 增加一个Parent域 end;CellspaceType=array 1.MaxNodeCount of NodeType;TreeType=TPosition;varCellspace:CellspaceType;Tree:TreeType; 下面我们只针对上面的指针实现方案实现树的ADT操作。对于指针实现的树，空结点表示空指针nil。对于浮标实现的树，可以类似地实现下面的操作。指针实现的左儿子右兄弟表示法实现的ADT树操作函数 Leftmost_Child(v,T)功能这是一个求最左儿子结点的函数。函数值为树T中结点v的最左儿子的位置。当v是叶结点时，函数值为nil，表示结点v没有儿子。实现Function Leftmost_Child(v:TPosition;var T:TreeType):TPosition;beginreturn(v.Leftmost_Child);end;说明返回v的最左儿子的位置指针。复杂性显然为O(1)。函数 Right_Sibling(v,T)功能这是一个求右邻兄弟的函数，函数值为树T中结点v的右邻兄弟。当v没有右邻兄弟时，函数值为nil。实现Function Right_Sibling(v:TPosition;var T:TreeType):TPosition;beginreturn(v.Right_Sibling);end;说明返回v的右邻兄弟的位置指针。复杂性显然为O(1)。函数 Parent(v,T)功能这是一个求父结点的函数，函数值为树T中结点v的父亲在结点表中的位置。当v是根结点时，函数值为nil，表示结点v没有父结点。实现Function Parent(v:TPosition;var T:TreeType):TPosition;beginreturn(v.Parent);end;说明返回v的父结点的位置指针。复杂性显然为O(1)。函数 Create(i,x,T1,T2,.,Ti)功能这是一族建树过程。对于每一个非负整数i，该函数生成一个新树T，T的根结点v的标号为x，并令v有i个儿子，这些儿子从左到右分别为树T1,T2,.,Ti的根。当i=0时，v既是树根，又是树叶。实现Function Create(i:integer;var x:LabelType;var T1,T2,.,Ti,T:TreeType);beginNew(T); 建T的根结点T.Label:=x;T.Parent:=nil;T.Right_Sibling:=nil;if i0 then begin T.Leftmost_Child:=T1; for k:=1 to i do begin Tk.Parent:=T; if ki then Tk.Right_Sibling:=Tk+1 else Tk.Right_Sibling:=nil; end;end;end;说明这个过程首先生成新树的根结点，其中存储的数据为x；然后对于每一个Tk，1ki，将Tk的根结点的父亲指向T，将Tk的根结点的右兄弟指向Tk+1(对于k=i的Tk其右兄弟为nil)。这里我们假设输入的参数Tknil，1ki。复杂性显然为O(i)。Label,Root和MakeNull比较简单，这里就不一一实现了。我们看到，用这种左儿子右兄弟表示法实现树，可以高效地实现树的ADT操作，缺点是占用了用来存储指针的空间。不过我们还是推荐用这种表示法来表示树。果园或森林的二叉树表示从树的左儿子右兄弟表示法和二叉树的链式表示法可知，一般树和二叉树都可以用二叉链表作为其存储结构。因此，以二叉链表为媒介可以将一棵一般树转换为一棵二叉树。例如，图11(a)中的树可转化为图11(b)中的二叉树，它们具有相同的二叉链表表示。(a)(b)图11 将一棵树转化为二叉树由树的左儿子右兄弟表示法可知，与其对应的二叉树根结点的右子树必为空树。因此，如果我们将一个果园中的所有树转换为二叉树，并将第i+1棵树当作第i棵树的根结点的右子树，i=1,2,.，则可将一个果园转换为一棵二叉树。如图12(a)中的果园，经上述转换，变成为图12(c)中的二叉树。(点击可以放大图形)图12 果园的二叉树的表示对于一个森林，可先确定森林中各树的一个排列顺序，将其变成一个果园，然后再用相应的二叉树来表示。用树的前序和中序遍历可定义果园的前序和中序遍历如下：1. 若果园非空，则对果园的前序遍历是依序对果园中第i棵树，i=1,2,.，进行前序遍历的结果。 2. 若果园非空，则对果园的中序遍历是依序对果园中第i棵树，i=1,2,.，进行中序遍历的结果。 在前序和中序遍历的意义下，果园和与之相应的二叉树是等价的。树的应用：二叉排序树排序是一种十分重要的运算。所谓排序就是把一堆杂乱无章的元素按照某种次序排列起来，形成一个线性有序的序列。二叉排序树是利用二叉树的结构特点来实现对元素排序的。一、二叉排序树的定义二叉排序树或者是空树，或者是具有如下性质的二叉树：、左子树上所有结点的数据值均小于根结点的数据值；、右子树上所有结点的数据值均大于或等于根结点的数据值；、左子树、右子树本身又各是一棵二叉排序树。由此可见，二叉排序树是一种特殊结构的二叉树。（18（10（3，15（12，15），21（20，21（，37）就是一棵二叉排序树。二、二叉排序树的构造二叉排序树的构造过程实质上就是排序的过程，它是二叉排序树作媒介，将一个任意的数据序列变成一个有序序列。二叉排序树的构造一般是采用陆续插入结点的办法逐步构成的。具体构造的思路是：1、以待排序的数据的第一个数据构成根结点；2、对以后的各个数据，逐个插入结点，而且规定：在插入过程的每一步，原有树结点位置不再变动，只是将新数据的结点作为一个叶子结点插入到合适的位置，使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求。树的应用：Huffman树一、哈夫曼树的含义：哈夫曼树是一种带权路径长度最短的树。所谓路径长度就是某个端结点到树的根结点的距离，等于该端结点的祖先数，或该结点所在层数减1，用lk表示。二叉树中每个端结点对应的一个实数称为该结点的权，用Wk表示。我们定义各端结点的权Wk与相应的路径程度lk乘积的代数和为该二叉树的带权路径长度，用WPL表示，即：可以证明，哈夫曼树是最优二叉树。如给定权值5，4，7，2，3，可以生成很多棵二叉树，其中的（A（B（7，5），C（4，D（3，2）是哈夫曼树。 二、哈夫曼树的构造1、哈夫曼算法：（1）根据给定的n个权值W1，W2，Wn构成n棵二叉树的森林：FT1，T2，Tn。其中每棵二叉树Ti只有一个带权为Wi的根结点，其左右子树为空。（2）在F中选取两棵结点的权值最小的树作为左右子树构成一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。（3）在F中删除这两棵树，同时，将新得到的二叉树加入F中。（4）重复（2）、（3），直到F只含一棵树为止。最后的这棵树便是哈夫曼树。2、算法描述为了上述算法，选用数组型的链表作为存储结构，其类型设计如下：Type tnode=RECORD weight：real； Lc，Rc：integer； END； tree=ARRAY1.2*n-1 of t