📄 ds6.2.3.1.htm
字号:
<p class="MsoNormal"><b><font size="5" color="#FFFFFF" face="宋体"><span style="mso-hansi-font-family: Times New Roman" lang="EN-US">
对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。如图6.5给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。最坏的情况是右单支树，如图6.6
所示，一棵深度为k的右单支树，只有k个结点，却需分配2<sup>k</sup>－1个存储单元。<o:p>
</o:p>
</span></font></b></p>
<p class="MsoNormal" style="text-indent:21.0pt" align="center"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:"Times New Roman""> <img border="0" src="ds6.2.7.gif" width="474" height="198"><o:p>
</o:p>
</span></p>
<div align="left">
<table border="2" cellspacing="0" cellpadding="0" style="border-collapse: collapse; mso-table-layout-alt: fixed; mso-border-alt: solid windowtext .5pt; mso-padding-alt: 0cm 5.4pt 0cm 5.4pt; border-style: none; border-width: medium; margin-left: 56.15pt" width="478" bordercolorlight="#3366CC" bordercolordark="#000000">
<tr style="height:18.0pt;mso-height-rule:exactly">
<td width="27" valign="top" style="height: 18.0pt; mso-height-rule: exactly; border: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF"><b>A <o:p>
</o:p>
</b></font></span></p>
</td>
<td width="27" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>∧
<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
</td>
<td width="27" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF"><b>B <o:p>
</o:p>
</b></font></span></p>
</td>
<td width="27" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>∧<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
</td>
<td width="27" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>∧<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
</td>
<td width="27" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>∧<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
</td>
<td width="27" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF"><b>C<o:p>
</o:p>
</b></font></span></p>
</td>
<td width="27" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>∧<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
</td>
<td width="27" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>∧<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
</td>
<td width="27" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>∧<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
</td>
<td width="27" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>∧<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
</td>
<td width="27" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>∧<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
</td>
<td width="27" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>∧<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
</td>
<td width="25" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>∧<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
</td>
<td width="18" valign="top" style="mso-border-left-alt: solid windowtext .5pt; height: 18.0pt; mso-height-rule: exactly; border-left-style: none; border-left-width: medium; border-right: .5pt solid windowtext; border-top: .5pt solid windowtext; border-bottom: .5pt solid windowtext; padding-left: 5.4pt; padding-right: 5.4pt; padding-top: 0cm; padding-bottom: 0cm" align="center">
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF"><b>D<o:p>
</o:p>
</b></font></span></p>
</td>
</tr>
</table>
</div>
<p align="center"><img border="0" src="ds6.2.8.gif" width="527" height="59"></p>
<p align="center"> </p>
<p align="center"><b><a href="ds6.2.3.HTM"><font size="5" color="#FFFF00">返回</font></a></b></p>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -