📄 chapter6_3.htm
字号:
<html><!-- #BeginTemplate "/Templates/article_template.dwt" -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="algorithm, data structure, contest, programming, 算法, 数据结构, 程序设计, 竞赛">
<meta name="description" content="discussing the algorithm and data structure of computer programming, as well as all kinds of programming contest.">
<meta name="description" content="讨论程序设计的算法与数据结构，各类程序设计竞赛试题解析和参赛经验介绍。">
<!-- #BeginEditable "doctitle" -->
<title>左儿子右兄弟表示法</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
var previous = "chapter6_2.htm";
var next = "chapter7.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h3>左儿子右兄弟表示法</h3>
<p>树的左儿子右兄弟表示法又称为<font face="楷体_GB2312"><b>二叉树表示法</b></font>或<font face="楷体_GB2312"><b>二叉链表表示法</b></font>。每个结点除了data域外，还含有两个域，分别指向该结点的最左儿子和右邻兄弟。这种表示法常用二叉链表实现，因此又称为<font face="楷体_GB2312"><b>二叉链表表示法</b></font>。但是实际应用中常用游标(静态链表)来代替链表，请参见<a href="../list/chapter3_3.htm">表的游标实现</a>。</p>
<p>若用指针实现，其类型定义为：</p>
<div align="center">
<center>
<table border="0" width="90%" bgcolor="#E0E0E0" cellpadding="5" style="font-size: 10pt">
<tr>
<td width="100%">
<p style="margin-top: 5; margin-bottom: 5">Type</p>
<p style="margin-top: 5; margin-bottom: 5"> TPosition=^NodeType;</p>
<p style="margin-top: 5; margin-bottom: 5"> NodeType=record</p>
<p style="margin-top: 5; margin-bottom: 5">
Label:LabelType;</p>
<p style="margin-top: 5; margin-bottom: 5">
Leftmost_Child,Right_Sibling:TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">
end;</p>
<p style="margin-top: 5; margin-bottom: 5"> TreeType=TPosition;
</td>
</tr>
</table>
</center>
</div>
<p>若用游标实现，其类型定义为:</p>
<div align="center">
<center>
<table border="0" width="90%" bgcolor="#E0E0E0" cellpadding="5" style="font-size: 10pt">
<tr>
<td width="100%">
<p style="margin-top: 5; margin-bottom: 5">Type</p>
<p style="margin-top: 5; margin-bottom: 5"> TPosition=integer;</p>
<p style="margin-top: 5; margin-bottom: 5"> NodeType=record</p>
<p style="margin-top: 5; margin-bottom: 5">
Label:LabelType;</p>
<p style="margin-top: 5; margin-bottom: 5">
Leftmost_Child,Right_Sibling:TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">
end;</p>
<p style="margin-top: 5; margin-bottom: 5"> CellspaceType=array
[1..MaxNodeCount] of NodeType;</p>
<p style="margin-top: 5; margin-bottom: 5"> TreeType=TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">var</p>
<p style="margin-top: 5; margin-bottom: 5"> Cellspace:CellspaceType;</p>
<p style="margin-top: 5; margin-bottom: 5"> Tree:TreeType;
</td>
</tr>
</table>
</center>
</div>
<p>此时树类型TreeType是整数类型，它指示树根在cellspace中的游标。例如图5(a)中树的左儿子右兄弟表示法的指针和游标实现分别如图5(b)和(c)所示。</p>
<p align="center"><img border="0" src="images/img7.gif" width="274" height="232"></p>
<p align="center">(a)</p>
<p align="center"><img border="0" src="images/img8.gif" width="591" height="220"></p>
<p align="center">(b)</p>
<p align="center"><img border="0" src="images/img6.gif" width="633" height="145"></p>
<p align="center">(c)</p>
<p align="center">图5 树的左儿子右兄弟表示法</p>
<p><br>
用树的左儿子右兄弟表示法可以直接实现树的大部分操作，只有在对树结点作Parent操作时需遍历树。如果要反复执行Parent操作，可在结点记录中再开辟一个指向父结点的指针域，也可以利用最右儿子单元中的Right_Sibling作为指向父结点的指针(否则这里总是空指针)。当执行Parent(v)时，可以先通过Right_Sibling逐步找出结点v的最右兄弟，再通过最右兄弟的Right_Sibling(父亲指针)找到父结点。这个结点就是结点v的父亲。在这样的表示法下，求一个结点的父亲所需要的时间正比于该结点右边的兄弟个数。不过，这时每个记录中需要多用一位(bit)空间，用以标明该记录中的right_sibling是指向右邻兄弟还是指向父亲。</p>
<p>考虑到对于现在的计算机，内存已经不是很重要的限制因素了。我们下面就采取增加一个parent域的方案，以改进左儿子右兄弟表示法中Parent操作的效率。因此重新定义树的类型如下：</p>
<p>若用指针实现，其类型定义为：</p>
<div align="center">
<center>
<table border="0" width="90%" bgcolor="#E0E0E0" cellpadding="5">
<tr>
<td width="100%">
<p style="margin-top: 5; margin-bottom: 5">Type</p>
<p style="margin-top: 5; margin-bottom: 5"> TPosition=^NodeType;</p>
<p style="margin-top: 5; margin-bottom: 5"> NodeType=record</p>
<p style="margin-top: 5; margin-bottom: 5">
Label:LabelType;</p>
<p style="margin-top: 5; margin-bottom: 5">
Parent,Leftmost_Child,Right_Sibling:TPosition; {增加一个Parent域}</p>
<p style="margin-top: 5; margin-bottom: 5">
end;</p>
<p style="margin-top: 5; margin-bottom: 5"> TreeType=TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">var</p>
<p style="margin-top: 5; margin-bottom: 5"> Tree:TreeType;
</td>
</tr>
</table>
</center>
</div>
<p>若用游标实现，其类型定义为:</p>
<div align="center">
<center>
<table border="0" width="90%" bgcolor="#E0E0E0" cellpadding="5">
<tr>
<td width="100%">
<p style="margin-top: 5; margin-bottom: 5">Type</p>
<p style="margin-top: 5; margin-bottom: 5"> TPosition=integer;</p>
<p style="margin-top: 5; margin-bottom: 5"> NodeType=record</p>
<p style="margin-top: 5; margin-bottom: 5">
Label:LabelType;</p>
<p style="margin-top: 5; margin-bottom: 5">
Parent,Leftmost_Child,Right_Sibling:TPosition; {增加一个Parent域}</p>
<p style="margin-top: 5; margin-bottom: 5">
end;</p>
<p style="margin-top: 5; margin-bottom: 5"> CellspaceType=array
[1..MaxNodeCount] of NodeType;</p>
<p style="margin-top: 5; margin-bottom: 5"> TreeType=TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">var</p>
<p style="margin-top: 5; margin-bottom: 5"> Cellspace:CellspaceType;</p>
<p style="margin-top: 5; margin-bottom: 5"> Tree:TreeType;
</td>
</tr>
</table>
</center>
</div>
<p>下面我们只针对上面的指针实现方案实现树的ADT操作。对于指针实现的树，空结点∧表示空指针nil。对于浮标实现的树，可以类似地实现下面的操作。</p>
<blockquote>
<p align="center"><b>指针实现的左儿子右兄弟表示法实现的ADT树操作</b></p>
</blockquote>
<div align="center">
<center>
<table border="0" width="90%" style="font-size: 10pt" cellpadding="5">
<tr>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -