chapter5_1.htm

介绍各种数据结构的讲义

            <p style="margin-top: 5; margin-bottom: 5">Procedure Create(x:LabelType;var 
              Left,Right,T:TreeType);</p>
            <p style="margin-top: 5; margin-bottom: 5">begin</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;T.NodeList[1]:=x;</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;T.NodeCount:=Left.NodeCount+Right.NodeCount+1;</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;h_left:=cal(Left.NodeCount);</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;h_right:=cal(Right.NodeCount);{分别计算Left和Right的高度}</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;if h_left&gt;h_Right 
              then h:=h_left else h:=h_right;{新树T的高度为h+1}</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;for i:=Left.NodeCount+1 
              to (1 shl (h+1))-1 do Left.NodeList[i]:=&amp;；</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;Left.NodeCount:=(1 
              shl (h+1))-1;</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp; {将Left补成高度为h的满二叉树；其中shl是左移位运算，用来计算2的幂}</p>
            <p style="margin-top: 5; margin-bottom: 5">if h_right&lt;h then</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; begin</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp; for 
              i:=Right.NodeCount+1 to (1 shl h)-1 do Right.NodeList[i]:=&amp;；</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;&nbsp;&nbsp; Right.NodeCount:=(1 
              shl h)-1;</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; end;</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp; {若Right的高度小于h，则将Right补成高度为h-1的满二叉树}</p>
            <p style="margin-top: 5; margin-bottom: 5">　</p>
            <p style="margin-top: 5; margin-bottom: 5">{=======</p>
            
        <p style="margin-top: 5; margin-bottom: 5">对于Left中编号为i的结点v，它在新树T中的编号为2<sup>h 
          </sup>+i，其中h=<img border="0" src="images/img10.gif" width="5" height="14">log<sub>2</sub>(i+1)-1<img border="0" src="images/img11.gif" width="5" height="14"> 
          ；对于Right中编号为i的结点v，它在新树T中的编号为2<sup>h+1</sup>+i，其中h=<img border="0" src="images/img10.gif" width="5" height="14">log<sub>2</sub>(i+1)-1<img border="0" src="images/img11.gif" width="5" height="14"> 
          。</p>
            <p style="margin-top: 5; margin-bottom: 5">=======}</p>
            <p style="margin-top: 5; margin-bottom: 5">　</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;for i:=1 to Left.NodeCount 
              do</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; T.NodeList[(1 
              shl cal(i))+i]:=Left.NodeList[i];</p>
            <p style="margin-top: 5; margin-bottom: 5">{计算出Left中编号为i的结点在T中的位置，将其复制到T中}</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;for i:=1 to Right.NodeCount 
              do</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;&nbsp; T.NodeList[(1 
              shl (cal(i)+1))+i]:=Right.NodeList[i];</p>
            <p style="margin-top: 5; margin-bottom: 5">{计算出Right中编号为i的结点在T中的位置，将其复制到T中}</p>
            <p style="margin-top: 5; margin-bottom: 5">end;</p>
            <p style="margin-top: 5; margin-bottom: 5">　</p>
            
        <p style="margin-top: 5; margin-bottom: 5">其中cal(i)用来计算含有i个结点的近似满二叉树T的高度，cal(i)=<img border="0" src="images/img10.gif" width="5" height="14">log<sub>2</sub>(i+1)-1<img border="0" src="images/img11.gif" width="5" height="14">,可以实现如下：</p>
            <p style="margin-top: 5; margin-bottom: 5">　</p>
            <p style="margin-top: 5; margin-bottom: 5">Function cal(i:integer;):integer;</p>
            <p style="margin-top: 5; margin-bottom: 5">var</p>
            <p style="margin-top: 5; margin-bottom: 5">x:real;</p>
            <p style="margin-top: 5; margin-bottom: 5">begin</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;x:=log2(i+1)-1;</p>
            <p style="margin-top: 5; margin-bottom: 5">&nbsp;if x=int(x) then 
              return(x) else return(int(x)+1); {向上取整}</p>
            <p style="margin-top: 5; margin-bottom: 5">end;</p>
            <p style="margin-top: 5; margin-bottom: 5">　</p>
            <p style="margin-top: 5; margin-bottom: 5">其中log2(n)计算实数n以2为底的对数。</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">　</p>
            <p style="margin-top: 5; margin-bottom: 5">在顺序存储的结构下，建立一棵新的二叉树的过程比较复杂。我们首先给出以下几个命题：</p>
            <p style="margin-top: 5; margin-bottom: 5">　</p>
            <p style="margin-top: 5; margin-bottom: 5"><b>命题一</b></p>
            <blockquote> 
              
          <p style="margin-top: 5; margin-bottom: 5">一棵<a href="../tree/chapter2.htm">高度</a>为h的<a href="chapter3.htm">满二叉树</a>有2<sup>h+1</sup>-1个结点。</p>
            </blockquote>
            <p style="margin-top: 5; margin-bottom: 5">证明：</p>
            <blockquote> 
              <p style="margin-top: 5; margin-bottom: 5">满二叉树的第i层有2<sup>i</sup>个结点，i=0,1,2,...,h(树根为第0层)，因此高度为h的满二叉树有2<sup>0</sup>+2<sup>1</sup>+..+2<sup>h 
                </sup>= 2<sup>h+1</sup>-1个结点。</p>
            </blockquote>
            <p style="margin-top: 5; margin-bottom: 5"><b>推论一</b></p>
            <blockquote> 
              
          <p style="margin-top: 5; margin-bottom: 5">我们从树根起，自上层到下层，逐层从左到右给二叉树的所有结点编号，如<a href="#image6">图6</a>所示，则<a href="chapter3.htm">近似满二叉树</a>的第h层的从左到右第k个结点的编号为2<sup>h</sup>+k-1。</p>
            </blockquote>
            <p style="margin-top: 5; margin-bottom: 5">证明：</p>
            <blockquote> 
              <p style="margin-top: 5; margin-bottom: 5">由于是近似满二叉树，所以第0层到第h-1层是满二叉树，根据命题一知道共有2<sup>h</sup>-1个结点，因此第h层的从左到右第1个结点的编号为2<sup>h</sup>-1+1，第h层的从左到右第k个结点的编号为2<sup>h</sup>-1+k。</p>
            </blockquote>
            <p style="margin-top: 5; margin-bottom: 5"><b>推论二</b></p>
            <blockquote> 
              
          <p style="margin-top: 5; margin-bottom: 5">一棵有n个结点的近似满二叉树，高度为<img border="0" src="images/img10.gif" width="5" height="14">log<sub>2</sub>(n+1)-1<img border="0" src="images/img11.gif" width="5" height="14"> 
            ,其中<img border="0" src="images/img10.gif" width="5" height="14"> <img border="0" src="images/img11.gif" width="5" height="14">是天花板符号，<img border="0" src="images/img10.gif" width="5" height="14"> 
            x<img border="0" src="images/img11.gif" width="5" height="14">表示大于等于x的最小整数。</p>
            </blockquote>
            <p style="margin-top: 5; margin-bottom: 5">证明：</p>
            <blockquote> 
              
          <p style="margin-top: 5; margin-bottom: 5">有n个结点的近似满二叉树，若其高度为h，则满足2<sup>h</sup>-1&lt;n≤2<sup>h+1</sup>-1,化简得 
            log<sub>2</sub>(n+1)-1 ≤ h &lt; [log<sub>2</sub>(n+1)-1]+1，即h=<img border="0" src="images/img10.gif" width="5" height="14">log<sub>2</sub>(n+1)-1<img border="0" src="images/img11.gif" width="5" height="14">。</p>
            </blockquote>
            <p style="margin-top: 5; margin-bottom: 5"><b>推论三</b></p>
            <blockquote> 
              
          <p style="margin-top: 5; margin-bottom: 5">在近似满二叉树T中，设编号为i的结点处于T的第h层从左到右第k个位置上，则h=<img border="0" src="images/img10.gif" width="5" height="14">log<sub>2</sub>(i+1)-1<img border="0" src="images/img11.gif" width="5" height="14"> 
            ，k=i-(2<sup>h</sup>-1)。</p>
            </blockquote>
            <p style="margin-top: 5; margin-bottom: 5">证明：</p>
            <blockquote> 
              
          <p style="margin-top: 5; margin-bottom: 5">我们先不考虑编号大于i的结点，则前i个结点构成一棵近似满二叉树，根据推论二知其层数为h=<img border="0" src="images/img10.gif" width="5" height="14">log<sub>2</sub>(i+1)-1<img border="0" src="images/img11.gif" width="5" height="14"> 
            ，又因为第0层到第h-1层是满二叉树，根据命题一知道共有2<sup>h</sup>-1个结点，所以编号为i的结点处于第h层的第k=i-(2<sup>h</sup>-1)个位置上。</p>
            </blockquote>
            <p style="margin-top: 5; margin-bottom: 5">我们用T(h,k)表示树T的第h层的第k个结点，则有下列命题：</p>
            <p style="margin-top: 5; margin-bottom: 5">　</p>
            <p style="margin-top: 5; margin-bottom: 5"><b>命题二</b></p>
            <blockquote> 
              <p style="margin-top: 5; margin-bottom: 5">Left(h,k)=T(h+1,k)，Right(h,k)=T(h+1,k+2<sup>h</sup>)，其中Left和Right分别是树T的根结点的左右子树。</p>
            </blockquote>
            <p style="margin-top: 5; margin-bottom: 5">证明：</p>
            <blockquote> 
              <p style="margin-top: 5; margin-bottom: 5">显然。</p>
            </blockquote>
            <p style="margin-top: 5; margin-bottom: 5">我们用N(v,T)表示结点v在生成的新树T中的编号，则有下列命题：</p>
            <p style="margin-top: 5; margin-bottom: 5">　</p>
            <p style="margin-top: 5; margin-bottom: 5"><b>命题三</b></p>
            <blockquote> 
              
          <p style="margin-top: 5; margin-bottom: 5">对于Left中编号为i的结点v，N(v,T)=2<sup>h 
            </sup>+i，其中h=<img border="0" src="images/img10.gif" width="5" height="14">log<sub>2</sub>(i+1)-1<img border="0" src="images/img11.gif" width="5" height="14"> 
            ；对于Right中编号为i的结点v，N(v,T)=2<sup>h+1</sup>+i，其中h=<img border="0" src="images/img10.gif" width="5" height="14">log<sub>2</sub>(i+1)-1<img border="0" src="images/img11.gif" width="5" height="14"> 
            。</p>
            </blockquote>
            <p style="margin-top: 5; margin-bottom: 5">证明：</p>
            <blockquote> 
              
          <p style="margin-top: 5; margin-bottom: 5">在Left中编号为i的结点，根据推论三，他处于Left的第h=<img border="0" src="images/img10.gif" width="5" height="14">log<sub>2</sub>(i+1)-1<img border="0" src="images/img11.gif" width="5" height="14"> 
            层，第k=i-(2<sup>h</sup>-1)个位置上。根据命题二该结点处于新树T的第h+1层第k个位置上，所以根据推论一，它在二叉树T中的编号为2<sup>h+1</sup>+k-1=2*2<sup>h</sup>+[i-(2<sup>h</sup>-1)]-1=2<sup>h</sup>+i。结点在Right中的情况同理可证。</p>
            </blockquote>
            <p style="margin-top: 5; margin-bottom: 5">　</p>
            <p style="margin-top: 5; margin-bottom: 5">有了命题三，我们就可以完成建树的过程。算法如下：</p>
            <ol>
              <li> 
                <p style="margin-top: 5; margin-bottom: 5">根据推论二计算Left和Right的高度，分别为h<sub>Left</sub>和h<sub>Right 
                  </sub>；
              </li>
              <li> 
                <p style="margin-top: 5; margin-bottom: 5">设h=max{h<sub>Left</sub>,h<sub>Right</sub>}，新树T的高度就为h+1；
              </li>
              <li> 
                <p style="margin-top: 5; margin-bottom: 5">将Left补成高度为h的满二叉树；
              </li>
              <li> 
                <p style="margin-top: 5; margin-bottom: 5">若h<sub>Right</sub>&lt;h，则将Right补成高度为h-1的满二叉树；
              </li>
              <li> 
                <p style="margin-top: 5; margin-bottom: 5">依次扫描Left的每一个结点，根据命题三计算出Left中编号为i的结点在T中的位置，将其复制到T中；
              </li>
              <li> 
                <p style="margin-top: 5; margin-bottom: 5">依次扫描Right的每一个结点，根据命题三计算出Right中编号为i的结点在T中的位置，将其复制到T中；
              </li>
            </ol>
            <p style="margin-top: 5; margin-bottom: 5">具体程序见前文的实现。</p>
          </blockquote>
          <p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
          <blockquote> 
            <p style="margin-top: 5; margin-bottom: 5">算法的主要时间花在扫描和赋值结点上，设新树有n个结点，则复杂性为<i>O</i>(n)。</p>
          </blockquote>
        </td>
      </tr>
    </table>
  </center>
</div>
<!-- #EndEditable --> 
</div>
<script src='../../../lib/footer.js'>
</script> 
</body> 
<!-- #EndTemplate --></html>