ds6.2.2.htm

这是清华大学所用的数据结构的电子版教材

<o:p>
</o:p> 
</span></b></font></span></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
&quot;Times New Roman&quot;"><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  
</span>n</span><sub><span lang="EN-US">0</span></sub><span style="font-family:宋体;mso-hansi-font-family:
&quot;Times New Roman&quot;">＝<span lang="EN-US">n</span></span><sub><span lang="EN-US">2</span></sub><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">＋<span lang="EN-US">1</span></span></b></font></p>
<p class="MsoNormal"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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"><font size="5" color="#FFFF00">满二叉树：</font></span><font size="5" color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">6.2</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">a</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">b</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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></span></font></b></p>
<p class="MsoNormal" align="center"><img border="0" src="ds6.2.3.gif" width="528" height="249"></p>
<p class="MsoNormal" align="left"><span style="mso-bidi-font-size: 10.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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"><font size="5" color="#FFFF00">完全二叉树</font><font size="5" color="#FFFFFF">：</font></span><font size="5" color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">k</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">n</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">i</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">1</span><span style="mso-bidi-font-size: 10.0pt; 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 lang="EN-US">i≤n</span></span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">i</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">6.3</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">a</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">b</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">6.2</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">b</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; 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></font></b></span></p>
<p class="MsoNormal" align="center"><img border="0" src="ds6.2.4.gif" width="514" height="249"></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:黑体"><span style="mso-spacerun: yes">&nbsp;</span></span><b><span style="font-family:黑体"><font size="5" color="#FFFF00">性质</font></span></b><b><span style="font-family:黑体" lang="EN-US"><font size="5" color="#FFFF00">4</font></span></b><span style="mso-spacerun: yes" lang="EN-US">&nbsp;  
</span><span style="font-family:宋体;
mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;"><font size="5" color="#FFFFFF"><b>具有</b></font></span><font size="5" color="#FFFFFF"><b><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">个结点的完全二叉树的深度</span><span lang="EN-US">k</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">为</span><span lang="EN-US">[log<sub>2</sub>n]+1</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">。</span></b></font></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes" lang="EN-US">&nbsp;&nbsp;&nbsp;  
</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">证明</span><span style="mso-spacerun: yes" lang="EN-US">&nbsp;  
</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">根据完全二叉树的定义和性质</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">可知，当一棵完全二叉树的深度为</span><span lang="EN-US">k</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">、结点个数为</span><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">时，有</span></b></font></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  
</span>2<sup>k</sup></span><sup><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">－</span><span lang="EN-US">1</span></sup><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">－</span><span lang="EN-US">1&lt;n</span><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">≤</span><span lang="EN-US">2<sup>k</sup>-1</span></b></font></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;"><font color="#FFFFFF"><b><font size="5">即</font></b></font></span><font color="#FFFFFF"><b><font size="5"><span lang="EN-US"><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  
</span>2<sup>k</sup></span><sup><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">－</span><span lang="EN-US">1</span></sup><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">≤</span><span lang="EN-US">n&lt;2<sup>k</sup></span></font></b></font></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;"><font size="5" color="#FFFFFF"><b>对不等式取对数，有</b></font></span></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span lang="EN-US"><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  
</span><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;</span>k</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">－</span><span lang="EN-US">1</span><span style="font-family:
宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">≤<span lang="EN-US">log</span></span><sub><span lang="EN-US">2</span></sub><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
&quot;Times New Roman&quot;">n&lt;k<o:p>
</o:p>
</span></b></font></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;"><font size="5" color="#FFFFFF"><b>由于<span lang="EN-US">k</span></b></font></span><font size="5" color="#FFFFFF"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">为</span><span lang="EN-US" style="font-family: 宋体; mso-hansi-font-family: Times New Roman">整数，所以有k＝[log</span><sub><span lang="EN-US">2</span></sub><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">n]+1.<o:p>
</o:p>
</span></b></font></p>
<p align="left"><b><font size="5" color="#FFFF00">性质5</font><font size="5" color="#FFFFFF"> 
如果对一棵有n个结点的完全二叉树（其深度为）的结点按层序编号（从第1层到第<span lang="EN-US" style="font-family: 宋体; mso-hansi-font-family: Times New Roman">[log</span><sub><span lang="EN-US">2</span></sub><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:&quot;Times New Roman&quot;">n]+1层，每层从左到右</span>），则对任一结点i（1&lt;=i&lt;=n），有</font></b></p> 
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p align="left"><font size="5" color="#FFFFFF"><b>如果i=1，则结点i是二叉树的根，无双亲；如果i&gt;1，则其双亲PARENT(i)是结点[i/2];</b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p align="left"><font size="5" color="#FFFFFF"><b>如果2i&gt;n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i;</b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p align="left"><font size="5" color="#FFFFFF"><b>如果2i+1&gt;n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1;</b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p align="center"><b><font size="5"><a href="ds6.2.HTM"><font color="#FFFF00">返回</font></a></font></b></p>
<!--mstheme--></font>

</body>

</html>