二叉树(同名1604).doc

数据结构与算法 二叉树Binary Tree二叉树的定义二叉树是一类非常重要的树形结构，它可以递归地定义如下：二叉树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所示。图1 二叉树的5种基本形态(其中表示空)在二叉树中，每个结点至多有两个儿子，并且有左、右之分。因此任一结点的儿子不外4种情况：没有儿子；只有一个左儿子；只有一个右儿子；有一个左儿子并且有一个右儿子。注意：二叉树与树和有序树的区别二叉树与度数不超过2的树不同，与度数不超过2的有序树也不同。在有序树中，虽然一个结点的儿子之间是有左右次序的，但若该结点只有一个儿子时，就无须区分其左右次序。而在二叉树中，即使是一个儿子也有左右之分。例如图2中(a)和(b)是两棵不同的二叉树。虽然它们与图3中的普通树(作为无序树或有序树)很相似，但它们却不能等同于这棵普通的树。若将这3棵树均看作是有序树，则它们就是相同的了。图2 两棵不同的二叉树图3 一棵普通的树由此可见，尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。二叉树的数学性质二叉树具有以下的重要性质：1. 高度为h0的二叉树至少有h+1个结点； 2. 高度不超过h(0)的二叉树至多有2h+1-1个结点； 3. 含有n1个结点的二叉树的高度至多为n-1； 4. 含有n1个结点的二叉树的高度至少为logn，因此其高度为(logn)。 具有n个结点的不同形态的二叉树的数目在一些涉及二叉树的平均情况复杂性分析中是很有用的。设Bn是含有n个结点的不同二叉树的数目。由于二叉树是递归地定义的，所以我们很自然地得到关于Bn的下面的递归方程： (1)即一棵具有n1个结点的二叉树可以看成是由一个根结点、一棵具有i个结点的左子树和一棵具有n-i-1个结点的右子树所组成。(1)式的解是 (2)即所谓的Catalan数。因此，当n=3时,B3=5。于是，含有3个结点的不同的二叉树有5棵，如图4所示。图4 含有3个结点的不同二叉树特殊形态的二叉树满二叉树和近似满二叉树是二叉树的两种特殊情形。一棵高度为h0且有2h+1-1个结点的二叉树称为满二叉树。若一棵二叉树至多只有最下面的两层结点的度数小于2，并且最下面一层结点都集中在该层的最左边，则称这种二叉树为近似满二叉树(有时也称为完全二叉树)。(a) 满二叉树(b) 近似满二叉树(c) 非近似满二叉树图5 特殊形态的二叉树例如图5(a)是一棵高度为3的满二叉树。满二叉树的特点是每一层上的结点数都达到最大值，即对给定的高度，它是具有最多结点数的二叉树。满二叉树中不存在度数为1的结点，每个分枝结点均有两棵高度相同的子树，且叶结点都在最下面一层上。图5(b)是一棵近似满二叉树。显然满二叉树是近似满二叉树，但近似满二叉树不一定是满二叉树。在满二叉树的最下层上，从最右结点开始连续往左删去若干个结点后得到的二叉树是一棵近似满二叉树。因此，在近似满二叉树中，若某个结点没有左儿子，则它一定没有右儿子，即该结点是一个叶结点。图5(c)中，结点F没有左儿子而有右儿子L，故它不是一棵近似满二叉树。二叉树的操作二叉树的常用操作与树的常用操作相似。运算含义Parent(v,T)这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为，表示结点v没有父结点。Left_Child(v,T)这是一个求左儿子结点的函数。函数值为树T中结点v的左儿子。当结点v没有左儿子时，函数值为。Right_Child(v,T)这是一个求右儿子结点的函数。函数值为树T中结点v的右儿子。当结点v没有右儿子时，函数值为。Create(x,Left,Right,T)这是一个建树过程。该函数生成一棵新的二叉树T，T的根结点v的标号为x，v的左右儿子分别为Left和Right。Label(v,T)这时一个求标号的函数，函数值就是结点v的标号。Root(T)这是一个求树根的函数，函数值为树T的根结点。当T是空树时，函数值为。MakeNull(T)这是一个过程，它使T成为一棵空树。二叉树的实现我们已经看到，虽然二叉树与树很相似，但它却不是树的特殊情形。在许多情况下，使用二叉树具有结构简单，操作方便的优点。另外我们也看到，在树的左儿子右兄弟表示法中，实际上已将一棵一般的树转化为一棵二叉树。在更一般的情形，我们还可以将果园或森林转化为一棵等价的二叉树。下面我们来讨论几种二叉树的表示方法。二叉树的顺序存储结构此结构是将二叉树的所有结点，按照一定的次序，存储到一片连续的存储单元中。因此，必须将结点排成一个适当的线性序列，使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。这种结构特别适用于近似满二叉树。在一棵具有n个结点的近似满二叉树中，我们从树根起，自上层到下层，逐层从左到右给所有结点编号，就能得到一个足以反映整个二叉树结构的线性序列，如图6所示。其中每个结点的编号就作为结点的名称。图6 近似满二叉树的结点编号因此，我们可以对树的类型作如下说明：TPosition=integer;TreeType=record NodeCount:integer; 树的总结点数 NodeList:array 1.MaxNodeCount of LabelType; 存储结点的数组 end;将数组下标作为结点名称(编号)，就可将二叉树中所有结点的标号存储在一维数组中。例如，图6中的二叉树的顺序存储结构如图7所示。图7 近似满二叉树的顺序存储结构在二叉树的这种表示方式下，各结点之间的逻辑关系是隐含表示的。近似满二叉树中，除最下面一层外，各层都充满了结点。可能除最底层外，每一层的结点个数恰好是上一层结点个数的2倍。因此，从一个结点的编号就可推知其父亲，左、右儿子，和兄弟等结点的编号。例如，对于结点i我们有：1. 仅当i=1时，结点i为根结点；2. 当i1时，结点i的父结点为i/2；3. 结点i的左儿子结点为2i；4. 结点i的右儿子结点为2i+1；5. 当i为奇数且不为1时，结点i的左兄弟结点为i-1；6. 当i为偶数时，结点i的右兄弟结点为i+1。由上述关系可知，近似满二叉树中结点的层次关系足以反映结点之间的逻辑关系。因此，对近似满二叉树而言，顺序存储结构既简单又节省存储空间。对于一般的二叉树，采用顺序存储时，为了能用结点在数组中的位置来表示结点之间的逻辑关系，也必须按近似满二叉树的形式来存储树中的结点。显然，这将造成存储空间的浪费。在最坏情况下，一个只有k个结点的右单枝树却需要2k-1个结点的存储空间。例如，只有3个结点的右单枝树，如图8(a)所示，添上一些实际不存在的虚结点后，成为一棵近似满二叉树，相应的顺序存储结构如图8(b)所示。图8 一般二叉树的顺序存储结构下面我们就用这种顺序存储结构来实现二叉树的常用操作。在这种表示法中，整数0表示空结点。对于非近似满二叉树，我们将其补为近似满二叉树，并规定一个特殊的标号&，用来表示补充的结点，&要根据标号的具体类型来确定。顺序存储结构实现ADT二叉树的操作函数 Parent(v,T);功能这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为，表示结点v没有父结点。实现Function Parent(v:TPosition;var T:TreeType):TPosition;beginreturn(v div 2);end;说明根据这种表示法，我们知道，当i1时，结点i的父结点为i/2。复杂性显然为O(1)。函数 Left_Child(v,T);功能这是一个求左儿子结点的函数。函数值为树T中结点v的左儿子。当结点v没有左儿子时，函数值为。实现Function Left_Child(v:TPosition;var T:TreeType):TPosition;beginif (2*vT.NodeCount)or(T.NodeList2*v=&) then return(0) else return(2*v);end;说明如果结点v的左儿子存在，则其下标为2*v。复杂性显然为O(1)。函数 Right_Child(v,T);功能这是一个求右儿子结点的函数。函数值为树T中结点v的右儿子。当结点v没有右儿子时，函数值为。实现Procedure Right_Child(v:TPosition;var T:TreeType):TPosition;beginif (2*v+1T.NodeCount)or(T.NodeList2*v+1=&) then return(0) else return(2*v+1);end;说明如果结点v的左儿子存在，则其下标为2*v+1。复杂性显然为O(1)。函数 Create(x,Left,Right,T);功能这是一个建树过程。该函数生成一棵新的二叉树T，T的根结点标号为x，左右儿子分别为Left和Right。实现Procedure Create(x:LabelType;var Left,Right,T:TreeType);beginT.NodeList1:=x;T.NodeCount:=Left.NodeCount+Right.NodeCount+1;h_left:=cal(Left.NodeCount);h_right:=cal(Right.NodeCount);分别计算Left和Right的高度if h_lefth_Right then h:=h_left else h:=h_right;新树T的高度为h+1for i:=Left.NodeCount+1 to (1 shl (h+1)-1 do Left.NodeListi:=&；Left.NodeCount:=(1 shl (h+1)-1; 将Left补成高度为h的满二叉树；其中shl是左移位运算，用来计算2的幂if h_righth then begin for i:=Right.NodeCount+1 to (1 shl h)-1 do Right.NodeListi:=&； Right.NodeCount:=(1 shl h)-1; end; 若Right的高度小于h，则将Right补成高度为h-1的满二叉树=对于Left中编号为i的结点v，它在新树T中的编号为2h +i，其中h=log2(i+1)-1 ；对于Right中编号为i的结点v，它在新树T中的编号为2h+1+i，其中h=log2(i+1)-1 。=for i:=1 to Left.NodeCount do T.NodeList(1 shl cal(i)+i:=Left.NodeListi;计算出Left中编号为i的结点在T中的位置，将其复制到T中for i:=1 to Right.NodeCount do T.NodeList(1 shl (cal(i)+1)+i:=Right.NodeListi;计算出Right中编号为i的结点在T中的位置，将其复制到T中end;其中cal(i)用来计算含有i个结点的近似满二叉树T的高度，cal(i)=log2(i+1)-1,可以实现如下：Function cal(i:integer;):integer;varx:real;beginx:=log2(i+1)-1;if x=int(x) then return(x) else return(int(x)+1); 向上取整end;其中log2(n)计算实数n以2为底的对数。说明在顺序存储的结构下，建立一棵新的二叉树的过程比较复杂。我们首先给出以下几个命题：命题一一棵高度为h的满二叉树有2h+1-1个结点。证明：满二叉树的第i层有2i个结点，i=0,1,2,.,h(树根为第0层)，因此高度为h的满二叉树有20+21+.+2h = 2h+1-1个结点。推论一我们从树根起，自上层到下层，逐层从左到右给二叉树的所有结点编号，如图6所示，则近似满二叉树的第h层的从左到右第k个结点的编号为2h+k-1。证明：由于是近似满二叉树，所以第0层到第h-1层是满二叉树，根据命题一知道共有2h-1个结点，因此第h层的从左到右第1个结点的编号为2h-1+1，第h层的从左到右第k个结点的编号为2h-1+k。推论二一棵有n个结点的近似满二叉树，高度为log2(n+1)-1 ,其中 是天花板符号， x表示大于等于x的最小整数。证明：有n个结点的近似满二叉树，若其高度为h，则满足2h-1n2h+1-1,化简得 log2(n+1)-1 h log2(n+1)-1+1，即h=log2(n+1)-1。推论三在近似满二叉树T中，设编号为i的结点处于T的第h层从左到右第k个位置上，则h=log2(i+1)-1 ，k=i-(2h-1)。证明：我们先不考虑编号大于i的结点，则前i个结点构成一棵近似满二叉树，根据推论二知其层数为h=log2(i+1)-1 ，又因为第0层到第h-1层是满二叉树，根据命题一知道共有2h-1个结点，所以编号为i的结点处于第h层的第k=i-(2h-1)个位置上。我们用T(h,k)表示树T的第h层的第k个结点，则有下列命题：命题二Left(h,k)=T(h+1,k)，Right(h,k)=T(h+1,k+2h)，其中Left和Right分别是树T的根结点的左右子树。证明：显然。我们用N(v,T)表示结点v在生成的新树T中的编号，则有下列命题：命题三对于Left中编号为i的结点v，N(v,T)=2h +i，其中h=log2(i+1)-1 ；对于Right中编号为i的结点v，N(v,T)=2h+1+i，其中h=log2(i+1)-1 。证明：在Left中编号为i的结点，根据推论三，他处于Left的第h=log2(i+1)-1 层，第k=i-(2h-1)个位置上。根据命题二该结点处于新树T的第h+1层第k个位置上，所以根据推论一，它在二叉树T中的编号为2h+1+k-1=2*2h+i-(2h-1)-1=2h+i。结点在Right中的情况同理可证。有了命题三，我们就可以完成建树的过程。算法如下：1. 根据推论二计算Left和Right的高度，分别为hLeft和hRight ；2. 设h=maxhLeft,hRight，新树T的高度就为h+1；3. 将Left补成高度为h的满二叉树；4. 若hRighth，则将Right补成高度为h-1的满二叉树；5. 依次扫描Left的每一个结点，根据命题三计算出Left中编号为i的结点在T中的位置，将其复制到T中；6. 依次扫描Right的每一个结点，根据命题三计算出Right中编号为i的结点在T中的位置，将其复制到T中；具体程序见前文的实现。复杂性算法的主要时间花在扫描和赋值结点上，设新树有n个结点，则复杂性为O(n)。二叉树的结点度表示法二叉树的顺序存储结构可看作是二叉树的一种无边表示，即树中边信息是隐含的。二叉树的另一种无边表示称为二叉树的结点度表示。这种表示法将二叉树中所有结点依其后序列表排列，并在每个结点中附加一个0到3之间的整数，以表示结点的状态。该整数为0时，表示相应的结点为一叶结点；为1时，表示相应结点只有一个左儿子；为2时，表示相应结点只有一个右儿子；为3时，表示相应结点有两个儿子。例如，图9(a)中的二叉树的结点度表示如图9(b)所示。图9 二叉树的结点度表示在二叉树的结点度表示下，结点土的右儿子很容易找到，因为依后序列表法则，如果结点i有右儿子，它一定排在结点i的前一个，即i-1为其右儿子。找结点i的左儿子和父亲不像找右儿子那样直接。因为我们所知道的只是左儿子在i之前，而父亲在i之后，所以，结点i的左儿子和父亲必须对结点i之前和之后的结点进行搜索才能找到。说明：这种表示法我不太熟悉，所以运算的实现暂缺。或许你可以帮助我。 函数 Parent(v,T);功能这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为，表示结点v没有父结点。实现说明复杂性函数 Left_Child(v,T);功能这是一个求左儿子结点的函数。函数值为树T中结点v的左儿子。当结点v没有左儿子时，函数值为。实现说明复杂性函数 Right_Child(v,T);功能这是一个求右儿子结点的函数。函数值为树T中结点v的右儿子。当结点v没有右儿子时，函数值为。实现说明复杂性函数 Create(x,Left,Right,T);功能这是一个建树过程。该函数生成一棵新的二叉树T，T的根结点标号为x，左右儿子分别为Left和Right。实现说明复杂性二叉树的链式存储结构由于二叉树的每个结点最多有两个儿子，因此存储二叉树的最自然的方法是链接的方法。在用链接方式存储二叉树时，对于每个结点，除了存储结点标号等信息外，还应设置指向结点左右儿子的指针LeftChild和RightChild。结点的类型说明为:TypeTPosition=NodeType;NodeType=record Label:LabelType; LeftChild,RightChild:TPosition; end;TreeType=TPosition;若用游标来模拟指针，可用一数组来存储二叉树的所有结点，并对此数组作如下说明:TypeTPosition=integer;NodeType=record Label:LabelType; LeftChild,RightChild:TPosition; end;TreeType=TPosition;varSellsapce:array 1.MaxNodeCount of NodeType; cellspace用来存储结点单元例如，图9(a)中二叉树，用指针实现的二叉链表和用游标实现的二叉链表分别如图10(a)和(b)所示。(a)(b)图10 二叉树的链式存储结构若经常要在二叉树中进行Parent操作，可在每个结点上再加一个指向其父结点的指针Parent，形成一个带父亲指针的二叉链表，或称其为一个三叉链表。三叉链表的类型定义如下：TypeTPosition=NodeType;NodeType=record Label:LabelType; Parent,LeftChild,RightChild:TPosition; end;TreeType=TPosition;若用游标来模拟指针，可用一数组来存储二叉树的所有结点，并对此数组作如下说明:TypeTPosition=integer;NodeType=record Label:LabelType; Parent,LeftChild,RightChild:TPosition; end;TreeType=TPosition;varCellspace:array 1.MaxNodeCount of NodeType;cellspace用来存储结点下面我们就针对三叉链表讨论ADT二叉树基本操作的实现。请注意，下面的三叉链是用指针实现的，用游标实现的三叉链与此类似。三叉链表实现ADT二叉树基本操作函数 Parent(v,T);功能这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为，表示结点v没有父结点。实现Function Parent(v:TPosition;var T:TreeType);beginreturn(v.Parent);end;说明直接返回v的父结点指针。复杂性O(1)函数 Left_Child(v,T);功能这是一个求左儿子结点的函数。函数值为树T中结点v的左儿子。当结点v没有左儿子时，函数值为。实现Function Left_Child(v:TPosition;var T:TreeType):TPosition;beginreturn(v.LeftChild);end;说明直接返回v的左儿子指针。复杂性O(1)。函数 Right_Child(v,T);功能这是一个求右儿子结点的函数。函数值为树T中结点v的右儿子。当结点v没有右儿子时，函数值为。实现Function Right_Child(v:TPosition;var T:TreeType):TPosition;beginreturn(v.RightChild);end;说明直接返回v的右儿子指针。复杂性O(1)。函数 Create(x,Left,Right,T);功能这是一个建树过程。该函数生成一棵新的二叉树T，T的根结点标号为x，左右儿子分别为Left和Right。实现Procedure Create(x:LabelType;var Left,Right,T:TreeType);beginnew(T);T.Label:=x;T.LeftChild:=Left;T.RightChild:=Right;T.Parent:=nil;Left.Parent:=T;Right.Parent:=T;end;说明先生成一个标号为x的新结点，作为新树的根结点，然后修改其左右儿子指针，分别指向Left和Right，同时修改Left和Right的父亲指针，使其指向T。复杂性O(1)。我们看到，使用这种三叉链表示树，可以在O(1)时间内完成树的大部分操作，所以我们推荐使用这种方法表示树。果园或森林的二叉树表示从树的左儿子右兄弟表示法和二叉树的链式表示法可知，一般树和二叉树都可以用二叉链表作为其存储结构。因此，以二叉链表为媒介可以将一棵一般树转换为一棵二叉树。例如，图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,.，进行中序遍历的结果。在前序和中序遍历的意义下，果园和与之相应的二叉树是等价的。线索二叉树当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右儿子结点的指针，所以从任一结点出发只能直接找到该结点的左、右儿子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。我们可以证明：在n个结点的二叉链表中含有n+1个空指针。因为含n个结点的二叉链表中含有个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针，因此一共使用了n-1个指针，所以在n个结点的二叉链表中含有n+1个空指针。因此可以利用这些空指针，存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。为了区分一个结点的指针是指向其儿子的指针，还是指向其前驱或后继结点的线索，可在每个结点中增加两个线索标志。这样，线索二叉树结点类型定义为：typeTPosition=thrNodeType;thrNodeType=record Label:LabelType; ltag,rtag:0.1; LeftChild,RightChild:TPosition; end;其中ltag为左线索标志，rtag为右线索标志。它们的含义是: ltag=0，LeftChild是指向结点左儿子的指针； ltag=1，LeftChild是指向结点前驱的左线索。 rtag=0，RightCh