📄 chapter6_2.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_1.htm";
var next = "chapter6_3.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h3>儿子链表表示法</h3>
<p>树的另一种常用的表示方法就是儿子链表表示法。这种表示法用一个<a href="../list/chapter1.htm">线性表</a>来存储树的所有结点信息，称为结点表。对每个结点建立一个儿子表。儿子表中只存储儿子结点的地址信息，可以是指针，数组下标甚至内存地址。由于每个结点的儿子数目不定，因此儿子表常用单链表来实现，因此这种表示法称为儿子链表表示法。这种实现法与图的邻接表表示法类似。下图是一个儿子链表表示法的示意图。</p>
<blockquote>
<p align="center"><img border="0" src="images/img11.gif" width="485" height="347"></p>
<p align="center">图3 树的儿子链表实现</p>
</blockquote>
<p>图3中儿子链表结构表示的树如图4所示，树中各结点存放于一个<a href="../list/chapter3_1.htm">数组实现的表</a>中，数组下标作为各结点的指针。每一个数组元素（即每一个结点）含有一个儿子表，在图3中儿子表是<a href="../list/chapter3_2.htm">用单链表来实现</a>的，当然也可以用其他<a href="../list/chapter3.htm">表的实现方式</a>来实现儿子表，比如说<a href="../list/chapter3_3.htm">游标方式(静态链表)</a>。但由于每个结点的儿子数目不确定，所以一般不用数组来实现儿子表，但可以用数组来实现结点表，就如图3所示。在图3中可以看到，位于结点表第一个位置的结点(未必是根结点)有两个儿子结点，从左到右的两个儿子结点分别位于结点表的第2和第3个位置。因为图3中的结点表用数组实现，所以结点的标号就是结点在结点表中的数组下标。如图4所示。</p>
<blockquote>
<p align="center"><img border="0" src="images/img5.gif" width="355" height="281"></p>
<p align="center">图4 图3中儿子链表所表示的树</p>
</blockquote>
<p>为了指明树的根结点的位置，我们可以用一个变量Root记录根结点在结点表中的位置。有了根结点的位置，就可以利用儿子表依次找到树中所有的结点。</p>
<p>儿子链表表示的树的类型定义如下：</p>
<div align="center">
<center>
<table border="0" width="90%" cellpadding="5" bgcolor="#E0E0E0" 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">{======================</p>
<p style="margin-top: 5; margin-bottom: 5">NodeListType是一个元素为NodeType类型的线性表，其位置类型为TPosition，</p>
<p style="margin-top: 5; margin-bottom: 5">NodeListType定义了结点表的类型；</p>
<p style="margin-top: 5; margin-bottom: 5">ChildrenListType是一个元素为TPosition类型的线性表， ChildrenListType定义了儿子表的类型</p>
<p style="margin-top: 5; margin-bottom: 5">=======================}</p>
<p style="margin-top: 5; margin-bottom: 5">TPosition=....</p>
<p style="margin-top: 5; margin-bottom: 5">ChildrenListType=...</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">
Children:ChildrenListType;{结点的儿子表}</p>
<p style="margin-top: 5; margin-bottom: 5">
End;</p>
<p style="margin-top: 5; margin-bottom: 5">NodeListType=...</p>
<p style="margin-top: 5; margin-bottom: 5">TreeType=record</p>
<p style="margin-top: 5; margin-bottom: 5">
root:TPosition; {记录树根在结点表中的位置}</p>
<p style="margin-top: 5; margin-bottom: 5">
Node:NodeListType; {结点表}</p>
<p style="margin-top: 5; margin-bottom: 5">
end;
</td>
</tr>
</table>
</center>
</div>
<p style="margin-top: 5; margin-bottom: 5"> 其中NodeListType是一个元素为NodeType类型的线性表，其位置类型为TPosition，NodeListType定义了结点表的类型；ChildrenListType是一个元素为TPosition类型的线性表， ChildrenListType定义了儿子表的类型。以上类型定义并不考虑表的具体实现方式，如果假设结点表和儿子表都用单链表实现，则类型定义可以具体实现如下：</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">{儿子链表实现树的类型定义的一个具体实例，结点表和儿子表都用单链表实现}</p>
<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">ChildrenNodeType=record
{儿子表的结点项的类型}</p>
<p style="margin-top: 5; margin-bottom: 5">
child:TPosition; {指向儿子结点的位置指针}</p>
<p style="margin-top: 5; margin-bottom: 5">
next:^ChildrenNodeType; {指向下一个儿子表项的指针}</p>
<p style="margin-top: 5; margin-bottom: 5">
end;</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">
Children:^ChildrenNodeType;{指向儿子表的指针}</p>
<p style="margin-top: 5; margin-bottom: 5">
Next:TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">
End;</p>
<p style="margin-top: 5; margin-bottom: 5">TreeType=^NodeType;
{树的类型定义为结点指针类型}
</td>
</tr>
</table>
</center>
</div>
<p>注意以上的定义只是一种具体情况，实际应用中结点表和儿子表可能用数组、链表等任何一种表的实现方式实现。</p>
<p>下面我们就讨论结点表和儿子表都用链表实现的儿子链表的ADT操作的实现，之所以用单链表实现结点表和儿子表，是因为这样可以使ADT树的实现较为简洁和高效。至于结点表和儿子表的其他实现方式，可以类似地实现。</p>
<blockquote>
<p align="center"><b>儿子链表实现的ADT树操作</b></p>
</blockquote>
<div align="center">
<center>
<table border="0" width="90%" cellpadding="5">
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>函数 </b>Leftmost_Child(v,T)</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>功能</b></p>
<blockquote>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">这是一个求最左儿子结点的函数。函数值为树T中结点v的最左儿子的位置。当v是叶结点时，函数值为nil，表示结点v没有儿子。</p>
</blockquote>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>实现</b></p>
<blockquote>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">Function
Leftmost_Child(v:TPosition;var T:TreeType):TPosition;</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">begin</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"> return(v^.Children);</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">end;</p>
</blockquote>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>说明</b></p>
<blockquote>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">返回v的儿子表的第一个位置的元素，就是v的最左儿子的位置指针，若v的儿子表为空则返回空结点nil。</p>
</blockquote>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p>显然为<i>O</i>(1)。</p>
</blockquote>
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>函数 </b>Right_Sibling(v,T)</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>功能</b></p>
<blockquote>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">这是一个求右邻兄弟的函数，函数值为树T中结点v的右邻兄弟。当v没有右邻兄弟时，函数值为nil。</p>
</blockquote>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>实现</b></p>
<blockquote>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">Function
Right_Sibling(v:TPosition;var T:TreeType):TPosition;</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">var</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">i:TPosition;</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">k:^ChildrenNodeType;</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">Find:Boolean;</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">begin</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"> i:=T;
{i指向T的第一个结点}</p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -