📄 chapter6_1.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.htm";
var next = "chapter6_2.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h3>父亲数组表示法</h3>
<p>设T是一棵树，表示T的一种最简单的方法是用一个一维数组存储每个结点，数组的下标就是结点的位置指针，每个结点中有一个指向各自的父亲结点的数组下标的域，这样可使Parent操作非常方便。类型定义如下：</p>
<blockquote>
<div align="center">
<center>
<table border="0" width="90%" style="font-size: 10pt" 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:TPosition; {该结点的父亲的数组下标,对于根结点该域为0}</p>
<p style="margin-top: 5; margin-bottom: 5">
End;</p>
<p style="margin-top: 5; margin-bottom: 5"> TreeType=Record</p>
<p style="margin-top: 5; margin-bottom: 5">
NodeCount:integer; {树的结点的总数目}</p>
<p style="margin-top: 5; margin-bottom: 5">
Node:Array [1..MaxNodeCount] of NodeType;{存储树的结点}</p>
<p style="margin-top: 5; margin-bottom: 5">
End;
</td>
</tr>
</table>
</center>
</div>
</blockquote>
<p>由于树中每个结点的父亲是唯一的，所以上述的父亲数组表示法可以唯一地表示任何一棵树。在这种表示法下，寻找一个结点的父结点只需要<i>O</i>(1)时间。在树中可以从一个结点出发找出一条向上延伸到达其祖先的道路，即从一个结点到其父亲，再到其祖父等等。求这样的道路所需的时间正比于道路上结点的个数。在树的父亲数组表示法中，对于涉及查询儿子和兄弟信息的树操作，可能要遍历整个数组。为了节省查询时间，可以规定指示儿子的数组下标值大于父亲的数组下标值，而指示兄弟结点的数组下标值随着兄弟的从左到右是递增的。</p>
<blockquote>
<p align="center"><b>父亲数组实现的ADT树操作</b></p>
<div align="center">
<center>
<table border="0" width="90%" style="font-size: 10pt" cellpadding="5">
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>函数
</b>Parent(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是根结点时，函数值为0，表示结点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
Parent(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(T.Node[v].Parent);</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">由于每个结点都有一个域存储了其父亲结点的标号(数组下标)，因此Parent操作实现非常简单。</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">显然为O(1)。</p>
</blockquote>
</td>
</tr>
<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是叶结点时，函数值为0，表示结点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"> i:=v+1;</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"> while
(i<=T.NodeCount)and(T.Node[i].Parent<>v) do inc(i);</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"> if
i=T.NodeCount+1 then return(0)</p>
<p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">
else return(i);</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">因为没有保存每个结点的子结点的信息，因此只能依次扫描每个结点，根据我们的约定，子结点一定排在父结点的后面，且兄弟结点的下标从左到右依次递增，因此第一次遇到的父亲是n的结点就是n的最左结点。</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">该算法的复杂性取决于while循环。若设T.NodeCount=n，显然，在最坏情况下循环执行n-v次，最好情况下执行1次，平均情况下执行<img border="0" src="images/img2.gif" width="5" height="14">(n-v)/2<img border="0" src="images/img3.gif" width="5" height="14">，所以无论何种情况下，复杂性都为<i>O</i>(n)。</p>
</blockquote>
</td>
</tr>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -