chapter6_3.htm

介绍各种数据结构的讲义

        <td width="100%" bgcolor="#E0E0E0"> 
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>函数 </b>Leftmost_Child(v,T)</p>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>功能</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">这是一个求最左儿子结点的函数。函数值为树T中结点v的最左儿子的位置。当v是叶结点时，函数值为nil，表示结点v没有儿子。</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>实现</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">Function 
              Leftmost_Child(v:TPosition;var T:TreeType):TPosition;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">begin</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;return(v^.Leftmost_Child);</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">end;</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>说明</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">返回v的最左儿子的位置指针。</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
          <blockquote> 
            <p>显然为<i>O</i>(1)。</p>
          </blockquote>
        </td>
      </tr>
      <tr> 
        <td width="100%" bgcolor="#E0E0E0"> 
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>函数 </b>Right_Sibling(v,T)</p>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>功能</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">这是一个求右邻兄弟的函数，函数值为树T中结点v的右邻兄弟。当v没有右邻兄弟时，函数值为nil。</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>实现</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">Function 
              Right_Sibling(v:TPosition;var T:TreeType):TPosition;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">begin</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;return(v^.Right_Sibling);</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">end;</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>说明</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">返回v的右邻兄弟的位置指针。</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
          <blockquote> 
            <p>显然为<i>O</i>(1)。</p>
          </blockquote>
        </td>
      </tr>
      <tr> 
        <td width="100%" bgcolor="#E0E0E0"> 
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>函数</b> 
            Parent(v,T)</p>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>功能</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">这是一个求父结点的函数，函数值为树T中结点v的父亲在结点表中的位置。当v是根结点时，函数值为nil，表示结点v没有父结点。</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>实现</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">Function 
              Parent(v:TPosition;var T:TreeType):TPosition;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">begin</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;return(v^.Parent);</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">end;</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>说明</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">返回v的父结点的位置指针。</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
          <blockquote> 
            <p>显然为<i>O</i>(1)。</p>
          </blockquote>
        </td>
      </tr>
      <tr> 
        <td width="100%" bgcolor="#E0E0E0"> 
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>函数</b> 
            Create(i,x,T<sub>1</sub>,T<sub>2</sub>,..,T<sub>i</sub>)</p>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>功能</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">这是一族建树过程。对于每一个非负整数i，该函数生成一个新树T，T的根结点v的标号为x，并令v有i个儿子，这些儿子从左到右分别为树T1,T2,..,Ti的根。当i=0时，v既是树根，又是树叶。</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>实现</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">Function 
              Create(i:integer;var x:LabelType;var T<sub>1</sub>,T<sub>2</sub>,..,T<sub>i</sub>,T:TreeType);</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">begin</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;New(T); 
              {建T的根结点}</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;T^.Label:=x;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;T^.Parent:=nil;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;T^.Right_Sibling:=nil;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;if 
              i&gt;0 then</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp; 
              begin</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp; 
              T^.Leftmost_Child:=T<sub>1</sub>;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp; 
              for k:=1 to i do</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp; 
              begin</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              T<sub>k</sub>^.Parent:=T;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              if k&lt;i then T<sub>k</sub>^.Right_Sibling:=T<sub>k+1</sub></p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              else T<sub>k</sub>^.Right_Sibling:=nil;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp; 
              end;&nbsp;&nbsp;&nbsp;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;end;</p>
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">end;</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>说明</b></p>
          <blockquote> 
            <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">这个过程首先生成新树的根结点，其中存储的数据为x；然后对于每一个T<sub>k</sub>，1≤k≤i，将T<sub>k</sub>的根结点的父亲指向T，将T<sub>k</sub>的根结点的右兄弟指向T<sub>k+1</sub>(对于k=i的T<sub>k</sub>其右兄弟为nil)。这里我们假设输入的参数T<sub>k</sub>&lt;&gt;nil，1≤k≤i。</p>
          </blockquote>
          <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
          <blockquote> 
            <p>显然为<i>O</i>(i)。</p>
          </blockquote>
        </td>
      </tr>
    </table>
  </center>
</div>
<p>Label,Root和MakeNull比较简单，这里就不一一实现了。</p>
<p>我们看到，用这种左儿子右兄弟表示法实现树，可以高效地实现树的ADT操作，缺点是占用了用来存储指针的空间。不过我们还是推荐用这种表示法来表示树。</p>
<!-- #EndEditable --> 
</div>
<script src='../../../lib/footer.js'>
</script> 
</body> 
<!-- #EndTemplate --></html>