左儿子右兄弟表示法.doc

左儿子右兄弟表示法树的左儿子右兄弟表示法又称为二叉树表示法或二叉链表表示法。每个结点除了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)。这