📄 ds6.2.2.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>数 据 结 构</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>
<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">
<!--mstheme--><font face="宋体"><p:colorscheme
colors="#0000FF,#FFFFFF,#000000,#FFCC66,#00FFFF,#3366FF,#FF0033,#FFFF00"/>
<p align="center"><font color="#FFFFFF" size="6"><b>6.2.2 <span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: 黑体; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">二叉树的性质</span></b></font></p>
<p class="MsoNormal"><b><span style="font-family:黑体"><font size="5" color="#FFFF00">性质<span lang="EN-US">1</span></font></span><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">在</span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">二叉树的第</span><span lang="EN-US">i</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">层上最多有</span><span lang="EN-US">2<sup>i-1</sup></span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">个结点（</span><span lang="EN-US">i</span><span style="font-family:
宋体;mso-hansi-font-family:"Times New Roman"">≥</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">）。</span></font></b></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">
</span></b></font><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>该性质可由数学归纳法证明。证明略。</b></font></span></p>
<p class="MsoNormal"><b><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"><font size="5" color="#FFFF00">性质2</font><font size="5" color="#FFFFFF">
一棵深度为K的二叉树中，最多具有2<sup>K</sup>-1个结点。</font></span></b></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">证明：设第i层的结点数为Xi(1<=i<=K),深度为K的二叉树的结点数为M，Xi最多为2<sup>i</sup>-1，则有：</span></b></font></p>
<p class="MsoNormal" align="center"><img border="0" src="ds6.2.9.gif" width="281" height="58"></p>
<p class="MsoNormal"><b><span style="font-family:黑体"><font size="5" color="#FFFF00">性质<span lang="EN-US">3</span></font></span><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman" lang="EN-US">
</span><span style="font-family:黑体">对</span><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman"">于一棵非空的二叉树，如果叶子结点数为n</span><sub><span lang="EN-US">0</span></sub><span style="font-family:宋体;mso-hansi-font-family:
"Times New Roman"">，度数为<span lang="EN-US">2</span></span><span lang="EN-US" style="font-family: 宋体; mso-hansi-font-family: Times New Roman">的结点数为n</span><sub><span lang="EN-US">2</span></sub><span style="font-family:宋体;mso-hansi-font-family:
"Times New Roman"">，则有<span lang="EN-US">:<o:p>
</o:p>
</span></span></font></b></p>
<p class="MsoNormal" style="text-indent:21.0pt"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><span style="mso-spacerun: yes"><font size="5" color="#FFFFFF"><b>
</b></font></span><font size="5" color="#FFFFFF"><b>n</b></font></span><font size="5" color="#FFFFFF"><b><sub><span lang="EN-US">0</span></sub><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman"">＝<span lang="EN-US">n</span></span><sub><span lang="EN-US">2</span></sub><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman"">＋<span lang="EN-US">1<o:p>
</o:p>
</span></span></b></font></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman" lang="EN-US">
</span><span lang="EN-US" style="font-family: 宋体; mso-hansi-font-family: Times New Roman">证</span><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman"">明<span style="mso-spacerun: yes"> </span>设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有：<o:p>
</o:p>
</span></b></font></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><span style="mso-spacerun: yes">
</span>n=n</span><sub><span lang="EN-US">0</span></sub><span style="font-family:宋体;mso-hansi-font-family:
"Times New Roman"">＋<span lang="EN-US">n</span></span><sub><span lang="EN-US">1</span></sub><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman"">＋<span lang="EN-US">n</span></span><sub><span lang="EN-US">2</span></sub><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><span style="mso-spacerun: yes">
</span>（6-1）<o:p>
</o:p>
</span></b></font></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span style="font-family: 宋体; mso-hansi-font-family: Times New Roman">
在二叉树中，除根结点外，其余结点都有唯一的一个进入分支。设<span lang="EN-US">B</span><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman"">为</span><span lang="EN-US" style="font-family: 宋体; mso-hansi-font-family: Times New Roman">二叉树中的分支数，那么有：<o:p>
</o:p>
</span></span></font></b></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><b><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes">
</span>B=n-1<span style="mso-spacerun: yes">
</span>(6-2)<o:p>
</o:p>
</font></b></span></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span style="font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman"">这些分支是由度为<span lang="EN-US">1</span></span><span lang="EN-US" style="font-family: 宋体; mso-hansi-font-family: Times New Roman">和度为2的结点发出的，一个度为1的结点发出一个分支，一个度为2的结点发出两个分支，所以有：<o:p>
</o:p>
</span></font></b></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><span style="mso-spacerun: yes">
</span>B=n</span><sub><span lang="EN-US">1</span></sub><span style="font-family:宋体;mso-hansi-font-family:
"Times New Roman"">＋<span lang="EN-US">2n</span></span><sub><span lang="EN-US">2</span></sub><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><span style="mso-spacerun: yes">
</span><span style="mso-spacerun:
yes"> </span><span style="mso-spacerun: yes"> </span>（6-3）<o:p>
</o:p>
</span></font></b></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>综合（<span lang="EN-US">6-1),(6-2),(6-3)
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -