chapter6_1.htm

介绍各种数据结构的讲义

        <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没有右邻兄弟时，函数值为0。</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&nbsp; 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;i:=v+1;</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;while 
                (i&lt;=T.NodeCount)and(T.Node[i].Parent&lt;&gt;T.Node[v].Parent) 
                do</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp; 
                inc(i);</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;if 
                i=T.NodeCount+1 then return(0)</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                else return(i);</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之后的结点，遇到第一个与v有相同父结点的结点就是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">同Leftmost_Child一样，该函数复杂性为<i>O</i>(n)，其中n为树的总结点数。</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的根结点是标号为x的新结点v，并令v有i个儿子，这些儿子从左到右分别为树T<sub>1</sub>,T<sub>2</sub>,..,T<sub>i</sub>的根。当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">Procedure<b> 
                </b>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">var</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">k,j,father:integer;</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;with 
                T do</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;NodeCount:=1;</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;Node[1].Label:=x;</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;Node[1].Parent:=0;&nbsp; 
                {生成根结点}</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;for 
                k:=1 to i do</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp; 
                if T<sub>k</sub>.NodeCount&lt;&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; 
                inc(NodeCount);</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
                Node[NodeCount]:=T<sub>k</sub>.Node[1];</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
                Node[NodeCount].Parent:=1;{修改T<sub>k</sub>的根结点的父亲使其指向T的根}</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
                father:=NodeCount;&nbsp; {记下T<sub>k</sub>的根结点的标号}</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; 
                for j:=2 to T<sub>k</sub>.NodeCount do</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp; 
                beign</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp; 
                inc(NodeCount);</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp; 
                Node[NodeCount]:=T<sub>k</sub>.Node[j];</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp; 
                Node[NodeCount].Parent:=Node[NodeCount].Parent+father-1;</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
                {修改T<sub>k</sub>的每一个非根结点的父亲，因为T<sub>k</sub>的根结点的位置改变了}</p>
              <p style="word-spacing: 5; margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp; 
                end;&nbsp;&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">&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的第一个元素位置上；然后对于每一个T<sub>k</sub>，1≤k≤i，如果T<sub>k</sub>不为空则将T<sub>k</sub>的每一个结点复制到T中，同时修改T<sub>k</sub>的每一个元素的父结点，因为T<sub>k</sub>的根结点在T中的下标已经不是1了，而是father，因此T<sub>k</sub>的每一个元素的父结点的下标都应给增加一个增量father-1。</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">如果∑(T<sub>k</sub>的结点数)=n，即生成的新树的结点总数为n，则复杂性为<i>O</i>(n)。</p>
            </blockquote>
          </td>
        </tr>
      </table>
    </center>
  </div>
</blockquote>
<p>Label,Root和MakeNull比较简单，这里就不一一实现了。</p>
<p>我们可以看出，用父亲数组实现树，比较容易实现Parent运算，但是对于Leftmost_Child和Right_Sibling则效率不高，而且这种实现方法很占用内存。但实现上比较简单。</p>
<!-- #EndEditable --> 
</div>
<script src='../../../lib/footer.js'>
</script> 
</body> 
<!-- #EndTemplate --></html>