📄 chapter3.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 = "chapter2.htm";
var next = "chapter4.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h2>特殊形态的二叉树</h2>
<p><font face="楷体_GB2312"> <b>满二叉树</b></font>和<font face="楷体_GB2312"><b>近似满二叉树</b></font>是二叉树的两种特殊情形。</p>
<p>一棵高度为h≥0且有2<sup>h+1</sup>-1个结点的二叉树称为<b><font face="楷体_GB2312">满二叉树</font></b>。</p>
<p>若一棵二叉树至多只有最下面的两层结点的度数小于2，并且最下面一层结点都集中在该层的最左边，则称这种二叉树为<font face="楷体_GB2312"><b>近似满二叉树</b></font>(有时也称为<font face="楷体_GB2312"><b>完全二叉树</b></font>)。</p>
<blockquote>
<p align="center"><img border="0" src="images/img17.gif" width="283" height="208"></p>
<p align="center">(a) 满二叉树</p>
<p align="center"><img border="0" src="images/img18.gif" width="260" height="200"></p>
<p align="center">(b) 近似满二叉树</p>
<p align="center"><img border="0" src="images/img19.gif" width="246" height="198"></p>
<p align="center">(c) 非近似满二叉树</p>
<p align="center">图5 特殊形态的二叉树</p>
</blockquote>
<p>例如图5(a)是一棵高度为3的满二叉树。满二叉树的特点是每一层上的结点数都达到最大值，即对给定的高度，它是具有最多结点数的二叉树。满二叉树中不存在度数为1的结点，每个分枝结点均有两棵高度相同的子树，且叶结点都在最下面一层上。图5(b)是一棵近似满二叉树。显然满二叉树是近似满二叉树，但近似满二叉树不一定是满二叉树。在满二叉树的最下层上，从最右结点开始连续往左删去若干个结点后得到的二叉树是一棵近似满二叉树。因此，在近似满二叉树中，若某个结点没有左儿子，则它一定没有右儿子，即该结点是一个叶结点。图5(c)中，结点F没有左儿子而有右儿子L，故它不是一棵近似满二叉树。</p>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -