content-7-5.htm

实用的离散数学课件

      <p style="line-height: 200%"><font color="#0000FF">&nbsp;&nbsp;&nbsp; </font>在有向树   
      T 中,a、b分别为两个结点， </p>                                            
      <ul> 
        <li> 
          <p style="line-height: 200%">入度为0的结点称为<b><font color="#0000FF">根</font></b>；出度为0的结点称为<b><font color="#0000FF">叶</font></b>；</li> 
        <li> 
          <p style="line-height: 200%">若从 a 到 b 有一条弧，则 a 为 b   
          的<b><font color="#0000FF">父结点</font></b>，b 为 a 的<b><font color="#0000FF">子结点</font></b>；</li>  
        <li> 
          <p style="line-height: 200%">若从 a 到 b 有一条路径，则 a   
          为 b 的<b><font color="#0000FF">祖先</font></b>，b 为 a 的<b><font color="#0000FF">后裔</font></b>；</li>  
        <li> 
          <p style="line-height: 200%">具有共同父结点的各个结点称为<b><font color="#0000FF">兄弟结点</font></b>；</li> 
        <li> 
          <p style="line-height: 200%">由所有的 a 的后裔导出的 T   
          的子图称为 T 的<b><font color="#0000FF">子树</font></b>；</li>  
        <li> 
          <p style="line-height: 200%">由根到结点 a   
          的路径的长度称为 a 的<b><font color="#0000FF">级</font></b>或<b><font color="#0000FF">层次</font></b>；</li>  
        <li> 
          <p style="line-height: 200%">有根到叶的最长的一条通路的长度为<b><font color="#0000FF">树的深度</font></b>；</li> 
      </ul> 
      <p style="line-height: 200%">&nbsp;&nbsp;&nbsp;   
      有向树就像我们的家谱树一样，若在有向树中我们用“上为尊，左为上”的顺序来排列树中的结点，则有向树就可以变成一棵<b><font color="#0000FF">有序树</font></b>了。如：</p> 
      <p style="line-height: 200%" align="center"><img border="0" src="Image/shu16.gif" width="212" height="183"><font color="#0000FF"> 
      &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</font></p> 
      <p style="line-height: 200%" align="center">　</p>
      <p style="line-height: 200%" align="center"><b><font size="5"><a name="二元树">二元树</a></font></b> </p>                                          
      <!--msimagelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
        <li>
            <p style="line-height: 200%"><b>k元树：</b>有向树 T=&lt;V,E&gt;,若有任何一个结点v的出度都小于等于k,则称  
            T 为<b><font color="#0000FF"> k 元树</font></b>.<br> 
            当 k=2 时,称为<b><font color="#0000FF">二元树</font></b>;k=3  
            时,称为<b><font color="#0000FF">三元树.</font></b></li>
        <li>
            <p style="line-height: 200%"><b>k元完全树：</b>有向树 T,若任意一个结点  
            v 满足,如果 v 为叶结点,则出度为0;如果 v  
            为非叶结点,这出度为 k,则称 T 为<font color="#0000FF"><b>k元完全树.<br> 
            </b></font>当 k=2 时, 称为<b><font color="#0000FF">二元完全树</font></b>;k=3  
            时,称为<b><font color="#0000FF">三元完全树</font></b>.</li>
      <!--msimagelist--></table>
      <div align="center">
        <center>
        <table border="1" width="86%">
          <tr>
            <td width="25%" align="center"><img border="0" src="Image/shu19.gif" width="141" height="158"></td>
            <td width="25%" align="center"><img border="0" src="Image/shu20.gif" width="141" height="158"></td>
          </tr>
          <tr>
            <td width="25%" align="center"><img border="0" src="Image/shu21.gif" width="141" height="158"></td>
            <td width="25%" align="center"><img border="0" src="Image/shu22.gif" width="141" height="158"></td>
          </tr>
        </table>
        </center>
      </div>
      <p style="line-height: 200%">&nbsp;&nbsp;&nbsp;  
      在二元树或完全二元树中，结点的位置是有顺序的，在父结点左边的称为<b><font color="#0000FF">左儿子</font></b>，在父结点右边的称为<font color="#0000FF"><b>右儿子</b></font>；左儿子导出的子树称为<font color="#0000FF"><b>左子树</b></font>；右儿子导出的子树称为<font color="#0000FF"><b>右子树</b></font>。 </p>                                          
      <p style="line-height: 200%">　 </p>                                          
      <!--msimagelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
        <li>
            <p style="line-height: 200%"><b>二元树与普通树的相互转换</b></li>
      <!--msimagelist--></table>
      <p style="line-height: 200%">&nbsp;&nbsp;&nbsp;  
      二元树、完全二元树是所有树中使用最多的两种树；因为任意一棵普通的树都可以与二元树进行相互转化；如： </p>                                          
      <p style="line-height: 200%" align="center">&nbsp;<b><font color="#FF0000">左儿子是儿子、右儿子是兄弟</font></b> </p>                                          
      <div align="center">
        <center>
        <table border="1" width="94%">
          <tr>
            <td width="50%">
              <p align="center"><img border="0" src="Image/shu17.gif" width="275" height="190"></td>
            <td width="50%">
              <p align="center"><img border="0" src="Image/shu18.gif" width="184" height="195"></td>
          </tr>
        </table>
        </center>
      </div>
      <p style="line-height: 200%">&nbsp;&nbsp;&nbsp;&nbsp; </p>                                          
      <!--msimagelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
        <li>
            <p style="line-height: 200%"><b>二元树的遍历</b></li>
      <!--msimagelist--></table>
      <p style="line-height: 200%"><b>&nbsp;&nbsp;&nbsp; </b>对二元树的遍历，也即对二元树中结点的访问，按照访问的次序不同有三种方法：</p>
      <ol>
        <li>
          <p style="line-height: 200%"><b><font color="#0000FF">先根次序：</font></b>先访问根，再遍历左子树，再遍历右子树；</li>
        <li>
          <p style="line-height: 200%"><font color="#0000FF"><b>中根次</b></font><b><font color="#0000FF">序：</font></b>先遍历左子树，再访问根，再遍历右子树；</li>
        <li>
          <p style="line-height: 200%"><b><font color="#0000FF">后根次序：</font></b>先遍历左子树，再遍历右子树，再访问根；</li>
      </ol>
      <p style="line-height: 200%">对于下图的三中访问次序分别是：</p>
      <ol>
        <li>
          <p style="line-height: 200%"><b><font color="#0000FF">先根次序：</font></b><input type="text" name="T1" size="37"></li>
        <li>
          <p style="line-height: 200%"><font color="#0000FF"><b>中根次</b></font><b><font color="#0000FF">序：</font></b><input type="text" name="T1" size="37"></li>
        <li>
          <p style="line-height: 200%"><b><font color="#0000FF">后根次序：</font></b><input type="text" name="T1" size="37"></li>
      </ol>
      <p style="line-height: 200%" align="center"><img border="0" src="Image/shu23.gif" width="284" height="215"> </p>                                          
      <p style="line-height: 200%">　 </p>                                          
      <!--msimagelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
        <li>
            <p style="line-height: 200%"><b>表达式的表示</b></li>
      <!--msimagelist--></table>
      <p style="line-height: 200%">&nbsp;&nbsp;&nbsp;  
      一个代数表达式如，a*b-c/d  
      在计算机里表示时可以先用一棵二元树来表示,然后再对二元树进行遍历,最后保存它的遍历顺序即可,如上述表达式的二元树为</p>
      <p style="line-height: 200%" align="center"><img border="0" src="Image/shu25.gif" width="164" height="188"></p>
      <p style="line-height: 200%" align="center">该二元树的</p>
      <p style="line-height: 200%" align="center">先根遍历：&nbsp;&nbsp;&nbsp;&nbsp;  
      中根遍历：&nbsp;&nbsp;&nbsp;&nbsp; 后根遍历：</p> 
      <p style="line-height: 200%" align="center">-*ab/cd&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  
      a*b-c/d&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ab*cd/-</p> 
      <p style="line-height: 200%">　</p>
      <!--msimagelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
        <li>
            <p style="line-height: 200%"><b>搜索树：</b>搜索树是一种比较特殊的二元树，它的每个结点表示一个记录，且在该树中每个结点的记录子都小于其左子树的记录的值，且小于其右子树的记录的值。</p>
            <table border="0" width="100%">
              <tr>
                <td width="38%">
                  <p align="center"><img border="0" src="Image/shu26.gif" width="172" height="262"></td>
                <td width="62%">搜索方法：
                  <p>先将带查找的记录x与根结点比较，若相等则找到；若小于根结点，则到该结点的左子树中搜索；偌大于根结点，则到该结点的右子树中搜索；到了子树中仍然使用类似的方法。</td>
              </tr>
            </table>
        </li>
      <!--msimagelist--></table>
      <p style="line-height: 200%">　 </p>                                          
      <p style="line-height: 200%">　 </p>                                          
      <p style="line-height: 200%">　 </p>                                          
      <p style="line-height: 200%" align="right"><a href="#content-7-4">返回</a> </p>                                           
    </td>                                           
  </tr>                                           
  <tr>                                           
    <td>  
      <p style="line-height: 200%">&nbsp;</p> 
    </td>                                          
  </tr>                                          
</table>                                          
<p style="line-height: 200%">&nbsp;</p>                                          
<p style="line-height: 150%">&nbsp;</p><p align="right"><b><a href="contentFrame-mulu.htm">&lt;&lt;back</a></b>                                          
</body>                                          
</html>