📄 chapter5_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 = "chapter5_2.htm";
var next = "chapter5_4.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h3>二叉树的链式存储结构</h3>
<p>由于二叉树的每个结点最多有两个儿子，因此存储二叉树的最自然的方法是链接的方法。在用链接方式存储二叉树时，对于每个结点，除了存储结点标号等信息外，还应设置指向结点左右儿子的指针LeftChild和RightChild。结点的类型说明为:</p>
<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=^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">
LeftChild,RightChild: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">
LeftChild,RightChild:TPosition;</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">Sellsapce:array [1..MaxNodeCount]
of NodeType; {cellspace用来存储结点单元}
</td>
</tr>
</table>
</center>
</div>
<p>例如，<a href="chapter5_2.htm#image9">图9(a)</a>中二叉树，用指针实现的二叉链表和用游标实现的二叉链表分别如图10(a)和(b)所示。</p>
<blockquote>
<p align="center"><img border="0" src="images/img6.gif" width="520" height="261"></p>
<p align="center">(a)</p>
<p align="center"><img border="0" src="images/img7.gif" width="408" height="162"></p>
<p align="center">(b)</p>
<p align="center">图10 二叉树的链式存储结构</p>
</blockquote>
<p>若经常要在二叉树中进行Parent操作，可在每个结点上再加一个指向其父结点的指针Parent，形成一个带父亲指针的二叉链表，或称其为一个<font face="楷体_GB2312">三叉链表</font>。</p>
<p>三叉链表的类型定义如下：</p>
<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=^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,LeftChild,RightChild: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">
Parent,LeftChild,RightChild:TPosition;</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">Cellspace:array [1..MaxNodeCount]
of NodeType;{cellspace用来存储结点}
</td>
</tr>
</table>
</center>
</div>
<p>下面我们就针对三叉链表讨论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="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);</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> return(v^.Parent);</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的父结点指针。</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"> return(v^.LeftChild);</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的左儿子指针。</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">Function 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"> return(v^.RightChild);</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的右儿子指针。</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>
<p style="margin-top: 5; margin-bottom: 5">Procedure Create(x:LabelType;var
Left,Right,T:TreeType);</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> new(T);</p>
<p style="margin-top: 5; margin-bottom: 5"> T^.Label:=x;</p>
<p style="margin-top: 5; margin-bottom: 5"> T^.LeftChild:=Left;</p>
<p style="margin-top: 5; margin-bottom: 5"> T^.RightChild:=Right;</p>
<p style="margin-top: 5; margin-bottom: 5"> T^.Parent:=nil;</p>
<p style="margin-top: 5; margin-bottom: 5"> Left^.Parent:=T;</p>
<p style="margin-top: 5; margin-bottom: 5"> Right^.Parent:=T;</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">先生成一个标号为x的新结点，作为新树的根结点，然后修改其左右儿子指针，分别指向Left和Right，同时修改Left和Right的父亲指针，使其指向T。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">O(1)。</p>
</blockquote>
</td>
</tr>
</table>
</center>
</div>
<p>可以看到，使用这种三叉链表示树，能在O(1)时间内完成树的大部分操作，所以推荐使用这种方法表示树。</p>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -