📄 chapter5_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 = "chapter5.htm";
var next = "chapter5_2.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h3>二叉树的顺序存储结构<a name="imp-array"></a></h3>
<p>此结构是将二叉树的所有结点，按照一定的次序，存储到一片连续的存储单元中。因此，必须将结点排成一个适当的线性序列，使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。这种结构特别适用于<a href="chapter3.htm">近似满二叉树</a>。</p>
<p>在一棵具有n个结点的近似满二叉树中，我们从树根起，自上层到下层，逐层从左到右给所有结点编号，就能得到一个足以反映整个二叉树结构的线性序列，如图6所示。其中每个结点的编号就作为结点的名称。</p>
<blockquote>
<p align="center"><a name="image6"></a><img border="0" src="images/img22.gif" width="555" height="380"></p>
<p align="center">图6 近似满二叉树的结点编号</p>
</blockquote>
<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">TPosition=integer;</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">
NodeList:array [1..MaxNodeCount] of LabelType; {存储结点的数组}</p>
<p style="margin-top: 5; margin-bottom: 5">
end;
</td>
</tr>
</table>
</center>
</div>
<p>将数组下标作为结点名称(编号)，就可将二叉树中所有结点的标号存储在一维数组中。例如，图6中的二叉树的顺序存储结构如图7所示。</p>
<blockquote>
<p align="center"><img border="0" src="images/img23.gif" width="496" height="64"></p>
<p align="center">图7 近似满二叉树的顺序存储结构</p>
</blockquote>
<p><br>
在二叉树的这种表示方式下，各结点之间的逻辑关系是隐含表示的。<a href="chapter3.htm">近似满二叉树</a>中，除最下面一层外，各层都充满了结点。可能除最底层外，每一层的结点个数恰好是上一层结点个数的2倍。因此，从一个结点的编号就可推知其父亲，左、右儿子，和兄弟等结点的编号。例如，对于结点i我们有：</p>
<ol>
<li>
<p style="margin-top: 5; margin-bottom: 5">仅当i=1时，结点i为根结点；
</li>
<li>
<p style="margin-top: 5; margin-bottom: 5">当i>1时，结点i的父结点为<img border="0" src="images/img8.gif" width="5" height="15">i/2<img border="0" src="images/img9.gif" width="5" height="15">；
</li>
<li>
<p style="margin-top: 5; margin-bottom: 5">结点i的左儿子结点为2i；
</li>
<li>
<p style="margin-top: 5; margin-bottom: 5">结点i的右儿子结点为2i+1；
</li>
<li>
<p style="margin-top: 5; margin-bottom: 5">当i为奇数且不为1时，结点i的左兄弟结点为i-1；
</li>
<li>
<p style="margin-top: 5; margin-bottom: 5">当i为偶数时，结点i的右兄弟结点为i+1。
</li>
</ol>
<p>由上述关系可知，近似满二叉树中结点的层次关系足以反映结点之间的逻辑关系。因此，对近似满二叉树而言，顺序存储结构既简单又节省存储空间。</p>
<p>对于一般的二叉树，采用顺序存储时，为了能用结点在数组中的位置来表示结点之间的逻辑关系，也必须按近似满二叉树的形式来存储树中的结点。显然，这将造成存储空间的浪费。在最坏情况下，一个只有k个结点的右单枝树却需要2<sup>k</sup>-1个结点的存储空间。例如，只有3个结点的右单枝树，如图8(a)所示，添上一些实际不存在的虚结点后，成为一棵近似满二叉树，相应的顺序存储结构如图8(b)所示。</p>
<p align="center"><img border="0" src="images/img1.gif" width="563" height="216"></p>
<p align="center">图8 一般二叉树的顺序存储结构</p>
<p>下面我们就用这种顺序存储结构来实现二叉树的常用操作。在这种表示法中，整数0表示空结点∧。对于非近似满二叉树，我们将其补为近似满二叉树，并规定一个特殊的标号&，用来表示补充的结点，&要根据标号的具体类型来确定。</p>
<p align="center"><b>顺序存储结构实现ADT二叉树的操作</b></p>
<div align="center">
<center>
<table border="0" width="90%" cellpadding="5">
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>函数</b> Parent(v,T);</p>
<p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">这是一个求父结点的函数，函数值为树T中结点v的父亲。当v是根结点时，函数值为∧，表示结点v没有父结点。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">Function Parent(v:TPosition;var
T:TreeType):TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> return(v div 2);</p>
<p style="margin-top: 5; margin-bottom: 5">end;</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">根据这种表示法，我们知道，当i>1时，结点i的父结点为<img border="0" src="images/img8.gif" width="5" height="15">i/2<img border="0" src="images/img9.gif" width="5" height="15">。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">显然为<i>O</i>(1)。</p>
</blockquote>
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>函数</b> Left_Child(v,T);</p>
<p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">这是一个求左儿子结点的函数。函数值为树T中结点v的左儿子。当结点v没有左儿子时，函数值为∧。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">Function Left_Child(v:TPosition;var
T:TreeType):TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> if (2*v>T.NodeCount)or(T.NodeList[2*v]=&)
then return(0)</p>
<p style="margin-top: 5; margin-bottom: 5">
else return(2*v);</p>
<p style="margin-top: 5; margin-bottom: 5">end;</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">如果结点v的左儿子存在，则其下标为2*v。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">显然为<i>O</i>(1)。</p>
</blockquote>
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>函数</b> Right_Child(v,T);</p>
<p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">这是一个求右儿子结点的函数。函数值为树T中结点v的右儿子。当结点v没有右儿子时，函数值为∧。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">Procedure Right_Child(v:TPosition;var
T:TreeType):TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> if (2*v+1>T.NodeCount)or(T.NodeList[2*v+1]=&)
then return(0)</p>
<p style="margin-top: 5; margin-bottom: 5">
else return(2*v+1);</p>
<p style="margin-top: 5; margin-bottom: 5">end;</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">如果结点v的左儿子存在，则其下标为2*v+1。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">显然为<i>O</i>(1)。</p>
</blockquote>
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>函数</b> Create(x,Left,Right,T);</p>
<p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">这是一个建树过程。该函数生成一棵新的二叉树T，T的根结点标号为x，左右儿子分别为Left和Right。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
<blockquote>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -