📄 chapter5_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 = "chapter5_1.htm";
var next = "chapter5_3.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h3>二叉树的结点度表示法</h3>
<p>二叉树的顺序存储结构可看作是二叉树的一种无边表示，即树中边信息是隐含的。二叉树的另一种无边表示称为<font face="楷体_GB2312">二叉树的结点度表示</font>。这种表示法将二叉树中所有结点依其后序列表排列，并在每个结点中附加一个0到3之间的整数，以表示结点的状态。该整数为0时，表示相应的结点为一叶结点；为1时，表示相应结点只有一个左儿子；为2时，表示相应结点只有一个右儿子；为3时，表示相应结点有两个儿子。例如，图9(a)中的二叉树的结点度表示如图9(b)所示。</p>
<blockquote>
<p align="center"><a name="image9"></a><img border="0" src="images/img2.gif" width="447" height="441"></p>
<p align="center">图9 二叉树的结点度表示</p>
</blockquote>
<p>在二叉树的结点度表示下，结点土的右儿子很容易找到，因为依后序列表法则，如果结点i有右儿子，它一定排在结点i的前一个，即i-1为其右儿子。找结点i的左儿子和父亲不像找右儿子那样直接。因为我们所知道的只是左儿子在i之前，而父亲在i之后，所以，结点i的左儿子和父亲必须对结点i之前和之后的结点进行搜索才能找到。</p>
<p><b>说明：这种表示法我不了解，所以运算的实现暂缺。<a href="mailto:starfish.h@china.com">或许你可以帮助我。</a></b></p>
<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"> </p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5"> </p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5"> </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"> </p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5"> </p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5"> </p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5">
</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"> </p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5"> </p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5"> </p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5">
</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"> </p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5"> </p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<p style="margin-top: 5; margin-bottom: 5">
</td>
</tr>
</table>
</center>
</div>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -