📄 chapter2.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 = "chapter1.htm";
var next = "chapter3.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h2>二叉树的数学性质</h2>
<p>二叉树具有以下的重要性质：</p>
<ol>
<li>高度为h≥0的二叉树至少有h+1个结点；</li>
<li>高度不超过h(≥0)的二叉树至多有2<sup>h+1</sup>-1个结点；</li>
<li>含有n≥1个结点的二叉树的高度至多为n-1；</li>
<li>含有n≥1个结点的二叉树的高度至少为<img border="0" src="images/img8.gif" width="5" height="15">logn<img border="0" src="images/img9.gif" width="5" height="15">，因此其高度为Ω(logn)。</li>
</ol>
<p>具有n个结点的不同形态的二叉树的数目在一些涉及二叉树的平均情况复杂性分析中是很有用的。设B<sub>n</sub>是含有n个结点的不同二叉树的数目。由于二叉树是递归地定义的，所以我们很自然地得到关于B<sub>n</sub>的下面的递归方程：</p>
<blockquote>
<p><font size="2"><span style="mso-text-raise: -24.0pt; font-size: 10.5pt; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA" lang="EN-US">
<!--[if gte vml 1]><v:shapetype id="_x0000_t75" coordsize="21600,21600"
o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f"
stroked="f">
<v:stroke joinstyle="miter"/>
<v:formulas>
<v:f eqn="if lineDrawn pixelLineWidth 0"/>
<v:f eqn="sum @0 1 0"/>
<v:f eqn="sum 0 0 @1"/>
<v:f eqn="prod @2 1 2"/>
<v:f eqn="prod @3 21600 pixelWidth"/>
<v:f eqn="prod @3 21600 pixelHeight"/>
<v:f eqn="sum @0 0 1"/>
<v:f eqn="prod @6 1 2"/>
<v:f eqn="prod @7 21600 pixelWidth"/>
<v:f eqn="sum @8 21600 0"/>
<v:f eqn="prod @7 21600 pixelHeight"/>
<v:f eqn="sum @10 21600 0"/>
</v:formulas>
<v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/>
<o:lock v:ext="edit" aspectratio="t"/>
</v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:162.75pt;
height:54pt' o:ole="">
<v:imagedata src="file:///C:/DOCUME~1/胡海星/LOCALS~1/Temp/msoclip1/01/clip_image001.wmz"
o:title=""/>
</v:shape><![endif]-->
<img src="images/img21.gif" v:shapes="_x0000_i1025" width="217" height="72">
(1)</span></font><span lang="EN-US" style="font-size: 10.5pt; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font size="2">
<!--[if gte mso 9]><xml>
<o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1025"
DrawAspect="Content" ObjectID="_1026779785">
</o:OLEObject>
</xml><![endif]-->
</font></span></p>
</blockquote>
<p>即一棵具有n>1个结点的二叉树可以看成是由一个根结点、一棵具有i个结点的左子树和一棵具有n-i-1个结点的右子树所组成。</p>
<p>(1)式的解是<font size="2"><span style="mso-text-raise: -15.0pt; font-size: 10.5pt; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA" lang="EN-US"><!--[if gte vml 1]><v:shapetype id="_x0000_t75" coordsize="21600,21600"
o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f"
stroked="f">
<v:stroke joinstyle="miter"/>
<v:formulas>
<v:f eqn="if lineDrawn pixelLineWidth 0"/>
<v:f eqn="sum @0 1 0"/>
<v:f eqn="sum 0 0 @1"/>
<v:f eqn="prod @2 1 2"/>
<v:f eqn="prod @3 21600 pixelWidth"/>
<v:f eqn="prod @3 21600 pixelHeight"/>
<v:f eqn="sum @0 0 1"/>
<v:f eqn="prod @6 1 2"/>
<v:f eqn="prod @7 21600 pixelWidth"/>
<v:f eqn="sum @8 21600 0"/>
<v:f eqn="prod @7 21600 pixelHeight"/>
<v:f eqn="sum @10 21600 0"/>
</v:formulas>
<v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/>
<o:lock v:ext="edit" aspectratio="t"/>
</v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:78.75pt;
height:36pt' o:ole="">
<v:imagedata src="file:///C:/DOCUME~1/胡海星/LOCALS~1/Temp/msoclip1/01/clip_image001.wmz"
o:title=""/>
</v:shape><![endif]--> </span></font></p>
<blockquote>
<p><font size="2"><span lang="EN-US" style="font-size: 10.5pt; mso-bidi-font-size: 12.0pt; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span style="mso-text-raise:
-15.0pt"><img src="images/img13.gif" v:shapes="_x0000_i1025" width="105" height="48"></span>
<!--[if gte mso 9]><xml>
<o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1025"
DrawAspect="Content" ObjectID="_1026779878">
</o:OLEObject>
</xml><![endif]-->
</span></font> (2)</p>
</blockquote>
<p>即所谓的Catalan数。因此，当n=3时,B<sub>3</sub>=5。于是，含有3个结点的不同的二叉树有5棵，如图4所示。</p>
<blockquote>
<p align="center"><img border="0" src="images/img16.gif" width="353" height="143"></p>
<p align="center">图4 含有3个结点的不同二叉树</p>
</blockquote>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -