ds6.1.htm

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

      <h5><!--mstheme--><font face="宋体" color="#6666FF"><font size="5" color="#FFFFFF" face="宋体"><b><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman">嵌套集合表示法:</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">所谓嵌套集合是指一些集合的集体，对于其中任何两个集合，或者不相交，或者一个包含另一个。用嵌套集合的形式表示树，就是将根结点视为一个大的集合，其若干棵子树构成这个大集合中若干个互不相交的子集，如此嵌套下去，即构成一棵树的嵌套集合表示。图</span><span lang="EN-US">7.2  
      (a)</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">就是一棵树的嵌套集合表示。</span></b></font><!--mstheme--></font></h5>
      <!--mstheme--><font face="宋体"><!--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="宋体"><!--mstheme--></font>
      <h5><!--mstheme--><font face="宋体" color="#6666FF"><font size="5" color="#FFFFFF" face="宋体"><b><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman">凹入表示法:</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">树的凹入表示法如图</span><span lang="EN-US">7.2  
      (c)</span><span style="mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">所示。树的凹入表示法主要用于树的屏幕和打印输出。</span></b></font><!--mstheme--></font></h5>
      <!--mstheme--><font face="宋体"><!--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="宋体"><!--mstheme--></font>
      <h5 align="left"><!--mstheme--><font face="宋体" color="#6666FF"><font size="5" color="#FFFFFF" face="宋体"><b><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman">广义表表示法</span><span style="mso-bidi-font-size: 10.0pt; mso-ascii-font-family: Times New Roman">:</span><span style="mso-bidi-font-size: 10.0pt; 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; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">7.2  
      (b)</span><span style="mso-bidi-font-size: 10.0pt; 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></b></font><!--mstheme--></font></h5>
      <!--mstheme--><font face="宋体"><!--mstheme--></font><!--msthemelist--></td>
  </tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体"><!--mstheme--></font>
<h5 align="center"><!--mstheme--><font face="宋体" color="#6666FF"><img border="0" src="ds6.1.2.gif" width="354" height="288"><!--mstheme--></font></h5>
<!--mstheme--><font face="宋体">
<p class="MsoNormal" style="margin-left: 0" align="left"><b><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">基本术语：</span></font></b></p>
<ol>
  <li>
    <p class="MsoNormal" style="margin-left: 0" align="left"><b><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">树的结点包含一个数据元素及若干指向其子树的分支。</span></font></b></li>
  <li>
    <p class="MsoNormal" style="margin-left: 0" align="left"><b><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">结点拥有的子树数称为结点的度（Degree）。</span></font></b></li>
  <li>
    <p class="MsoNormal" style="margin-left: 0" align="left"><b><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">度为0的结点称为叶子（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点。</span></font></b></li>
  <li>
    <p class="MsoNormal" style="margin-left: 0" align="left"><b><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">树的度是树内各结点的度的最大值；</span></font></b></li>
  <li>
    <p class="MsoNormal" style="margin-left: 0" align="left"><b><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">结点的子树的根称为该结点的孩子(Child)，相应的，该结点称为孩子的双亲(Parent)；同一双亲的孩子之间互称兄弟。</span></font></b></li>
  <li>
    <p class="MsoNormal" style="margin-left: 0" align="left"><b><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">结点的层次从根开始定义起，根为第一层，根的孩子为第二层，依此；树中结点的最大层次称为树的深度或高度。</span></font></b></li>
  <li>
    <p class="MsoNormal" style="margin-left: 0" align="left"><b><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">如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树。</span></font></b></li>
  <li>
    <p class="MsoNormal" style="margin-left: 0" align="left"><b><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">森林是m(m&gt;=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。</span></font></b></li>
</ol>
<p class="MsoNormal" style="margin-left: 0" align="left">　</p>
<p class="MsoNormal" style="margin-left: 0" align="center"><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"><a href="ds6.HTM"><font size="5" color="#FFFF00">返回</font></a></span></b></p>
<p align="left">　</p>
<!--mstheme--></font>

</body>

</html>