左儿子右兄弟表示法．左儿子右兄弟表示法每个结点除了。或二叉链表表示法树的左儿子右兄弟表示法又称为二叉树表示法域外，还含有两个域，分别指向该结点的最左儿子和右邻兄弟。这种表示data。但是实际应用中常用游标法常用二叉链表实现，因此又称为二叉链表表示法)来代替链表，请参见表的游标实现。(静态链表若用指针实现，其类型定义为：TypeTPosition=^NodeType;NodeType=recordLabel:LabelType;Leftmost_Child,Right_Sibling:TPosition;end;TreeType=TPosition;:若用游标实现，其类型定义为TypeTPosition=integer;NodeType=recordLabel:LabelType;Leftmost_Child,Right_Sibling:TPosition;end;CellspaceType=array[1..MaxNodeCount]ofNodeType;TreeType=TPosition;varCellspace:CellspaceType;Tree:TreeType;此时树类型TreeType是整数类型，它指示树根在cellspace中的游标。例如图所示。(c)和5(b)中树的左儿子右兄弟表示法的指针和游标实现分别如图5(a)．(a)(b)(c)树的左儿子右兄弟表示法图5用树的左儿子右兄弟表示法可以直接实现树的大部分操作，只有在对树结点作Parent操作时需遍历树。如果要反复执行Parent操作，可在结点记也可以利用最右儿子单元中的录中再开辟一个指向父结点的指针域，Parent(v)当执行(否则这里总是空指针)。Right_Sibling作为指向父结点的指针的最右兄弟，再通过最右兄弟v时，可以先通过Right_Sibling逐步找出结点在这找到父结点。这个结点就是结点v的父亲。的Right_Sibling(父亲指针)样的表示法下，求一个结点的父亲所需要的时间正比于该结点右边的兄弟个数。不过，这时每个记录中需要多用一位(bit)空间，用以标明该记录中的right_sibling是指向右邻兄弟还是指向父亲。考虑到对于现在的计算机，内存已经不是很重要的限制因素了。我们下面就采操作的效Parent取增加一个parent域的
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
，以改进左儿子右兄弟表示法中率。因此重新定义树的类型如下：若用指针实现，其类型定义为：TypeTPosition=^NodeType;NodeType=recordLabel:LabelType;Parent,Leftmost_Child,Right_Sibling:TPosition;}域增加一个Parent{end;TreeType=TPosition;varTree:TreeType;:若用游标实现，其类型定义为TypeTPosition=integer;NodeType=recordLabel:LabelType;Parent,Leftmost_Child,Right_Sibling:TPosition;{增加一个Parent域}end;CellspaceType=array[1..MaxNodeCount]ofNodeType;TreeType=TPosition;varCellspace:CellspaceType;Tree:TreeType;操作。对于指针实现的树，ADT下面我们只针对上面的指针实现方案实现树的。对于浮标实现的树，可以类似地实现下面的操作。空结点∧表示空指针nil树操作指针实现的左儿子右兄弟表示法实现的ADT函数Leftmost_Child(v,T)功能这是一个求最左儿子结点的函数。函数值为树T中结点v的最左儿子的位置。当v是叶结点时，函数值为nil，表示结点v没有儿子。实现FunctionLeftmost_Child(v:TPosition;varT:TreeType):TPosition;beginreturn(v^.Leftmost_Child);end;说明返回v的最左儿子的位置指针。复杂性O(1)。显然为函数Right_Sibling(v,T)功能这是一个求右邻兄弟的函数，函数值为树T中结点v的右邻兄弟。当v没有右邻兄弟时，函数值为nil。实现FunctionRight_Sibling(v:TPosition;varT:TreeType):TPosition;beginreturn(v^.Right_Sibling);end;说明返回v的右邻兄弟的位置指针。复杂性O(1)。显然为函数Parent(v,T)功能这是一个求父结点的函数，函数值为树T中结点v的父亲在结点表中的位置。当v是没有父结点。v，表示结点nil根结点时，函数值为实现FunctionParent(v:TPosition;varT:TreeType):TPosition;beginreturn(v^.Parent);end;说明返回v的父结点的位置指针。复杂性O(1)。显然为函数Create(i,x,T,T,..,T)i21功能这是一族建树过程。对于每一个非负整数i，该函数生成一个新树T，T的根结点v的标号为x，并令v有i个儿子，这些儿子从左到右分别为树T1,T2,..,Ti的根。当i=0时，v既是树根，又是树叶。实现FunctionCreate(i:integer;varx:LabelType;varT,T,..,T,T:TreeType);i12beginNew(T);{建T的根结点}T^.Label:=x;T^.Parent:=nil;T^.Right_Sibling:=nil;ifi>0thenbeginT^.Leftmost_Child:=T;1fork:=1toidobeginT^.Parent:=T;kifk
nilk复杂性O。(i)显然为Label,Root和MakeNull比较简单，这里就不一一实现了。我们看到，用这种左儿子右兄弟表示法实现树，可以高效地实现树的ADT操作，缺点是占用了用来存储指针的空间。不过我们还是推荐用这种表示法来表示树。
浙公网安备 33021202002483