数据结构与程序设计7.htm

Data Structure Question

            <p class=MsoNormal><span lang=EN-US>r:array[I</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman"'>…</span><span lang=EN-US>n] of integer</span></p>
            <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>要求：</span><span
lang=EN-US>1</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>、额外空间的需求为</span><span
lang=EN-US>O(1)</span></p>
            <p class=MsoNormal><span lang=EN-US><span style='mso-tab-count:1'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              </span><span
style="mso-spacerun: yes">&nbsp; </span>2</span><span style='font-family:宋体;
mso-ascii-font-family:"Times New Roman"'>、时间复杂度必须为</span><span lang=EN-US>O(n),</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>并且还要加以简单的证明。</span></p>
            <p class=MsoNormal><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>九（</span><span
lang=EN-US>15</span></b><b><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman"'>分）</span><span lang=EN-US><o:p></o:p></span></b></p>
            <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>设分类二叉树中的结点的结构为：</span></p>
            <p class=MsoNormal><span lang=EN-US>left<span style='mso-tab-count:1'>&nbsp;&nbsp; 
              </span>data<span
style='mso-tab-count:2'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>right</span></p>
            <table border=1 cellspacing=0 cellpadding=0 style='border-collapse:collapse;
 border:none;mso-border-alt:solid windowtext .5pt;mso-padding-alt:0cm 5.4pt 0cm 5.4pt'>
              <tr> 
                <td width=31 valign=top style='width:23.4pt;border:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt'> 
                  <p class=MsoNormal><![if !supportEmptyParas]>&nbsp;<![endif]><span
  lang=EN-US><o:p></o:p></span></p>
                </td>
                <td width=36 valign=top style='width:27.0pt;border:solid windowtext .5pt;
  border-left:none;mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'> 
                  <p class=MsoNormal><![if !supportEmptyParas]>&nbsp;<![endif]><span
  lang=EN-US><o:p></o:p></span></p>
                </td>
                <td width=60 valign=top style='width:45.0pt;border:solid windowtext .5pt;
  border-left:none;mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'> 
                  <p class=MsoNormal><![if !supportEmptyParas]>&nbsp;<![endif]><span
  lang=EN-US><o:p></o:p></span></p>
                </td>
              </tr>
            </table>
            <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>其中，</span><span
lang=EN-US>left,right</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman"'>分别给出本结点的左右儿子结点的地址。</span><span lang=EN-US>Data</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>类型为整数。</span></p>
            <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>已知分类二叉树根结点地址为</span><span
lang=EN-US>root</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>，且它的所有结点的</span><span
lang=EN-US>data</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>域之值互不相等。设计一个程序，删除</span><span
lang=EN-US>data</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>域之值为</span><span
lang=EN-US>T</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>的结点，且保持删除后的二叉树仍为分类二叉树。</span></p>
            <p class=MsoNormal><b><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>十（</span><span
lang=EN-US>15</span></b><b><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman"'>分）</span><span lang=EN-US><o:p></o:p></span></b></p>
            <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>设中序穿线二叉树结点结构为：</span></p>
            <p class=MsoNormal><span lang=EN-US>left<span style='mso-tab-count:2'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              </span>ltag<span
style='mso-tab-count:2'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>data<span
style='mso-tab-count:2'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>rtag<span
style='mso-tab-count:2'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>right</span></p>
            <table border=1 cellspacing=0 cellpadding=0 style='border-collapse:collapse;
 border:none;mso-border-alt:solid windowtext .5pt;mso-padding-alt:0cm 5.4pt 0cm 5.4pt'>
              <tr> 
                <td width=43 valign=top style='width:32.4pt;border:solid windowtext .5pt;
  padding:0cm 5.4pt 0cm 5.4pt'> 
                  <p class=MsoNormal><![if !supportEmptyParas]>&nbsp;<![endif]><span
  lang=EN-US><o:p></o:p></span></p>
                </td>
                <td width=60 valign=top style='width:45.0pt;border:solid windowtext .5pt;
  border-left:none;mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'> 
                  <p class=MsoNormal><![if !supportEmptyParas]>&nbsp;<![endif]><span
  lang=EN-US><o:p></o:p></span></p>
                </td>
                <td width=48 valign=top style='width:36.0pt;border:solid windowtext .5pt;
  border-left:none;mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'> 
                  <p class=MsoNormal><![if !supportEmptyParas]>&nbsp;<![endif]><span
  lang=EN-US><o:p></o:p></span></p>
                </td>
                <td width=60 valign=top style='width:45.0pt;border:solid windowtext .5pt;
  border-left:none;mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'> 
                  <p class=MsoNormal><![if !supportEmptyParas]>&nbsp;<![endif]><span
  lang=EN-US><o:p></o:p></span></p>
                </td>
                <td width=72 valign=top style='width:54.0pt;border:solid windowtext .5pt;
  border-left:none;mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'> 
                  <p class=MsoNormal><![if !supportEmptyParas]>&nbsp;<![endif]><span
  lang=EN-US><o:p></o:p></span></p>
                </td>
              </tr>
            </table>
            <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>其中：</span></p>
            <p class=MsoNormal><span lang=EN-US>ltag= 0</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman"'>，则</span><span lang=EN-US>left</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>中存放的是该结点的左儿子结点地址</span></p>
            <p class=MsoNormal style='margin-left:45.0pt;text-indent:-18.0pt;mso-list:l3 level1 lfo7;
tab-stops:list 45.0pt'><![if !supportLists]><span lang=EN-US style='mso-hansi-font-family:
宋体'>1<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              </span></span><![endif]><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>则</span><span
lang=EN-US>left</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>中存放的是该结点的按中序次序的前驱结点地址</span></p>
            <p class=MsoNormal><span lang=EN-US>rtag=0</span><span style='font-family:宋体;
mso-ascii-font-family:"Times New Roman"'>，则</span><span lang=EN-US>right</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>中存放的是该结点的右儿子的结点地址</span></p>
            <p class=MsoNormal style='margin-left:39.75pt;text-indent:-18.0pt;mso-list:
l0 level1 lfo8;tab-stops:list 39.75pt'><![if !supportLists]><span lang=EN-US
style='mso-hansi-font-family:宋体'>1<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
              </span></span><![endif]><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>则</span><span
lang=EN-US>right</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>中存放的是该结点的按中序次序的后继结点地址</span></p>
            <p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>现已知中序穿线二叉树的根结点地址</span><span
lang=EN-US>root</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>。设计一个程序，打印出该穿线二叉树的中序结构。注意，不得再使用</span><span
lang=EN-US>0(n)</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>级及其</span><span
lang=EN-US>0(n)</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>级以上的辅助空间，否则作零分处理。（这里</span><span
lang=EN-US>N</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman"'>指穿线二叉树的结点规模。）<br><br><br>※来源：<a href="http://edu.yesky.com/jinxiu/kaoyan">天极网考研 http://edu.yesky.com/jinxiu/kaoyan</font></a></p><p align=right>-<a href="javascript:window.close()"><font color="#000000">关闭窗口</font></a>-<font color="#ffffff">.....</font></p><br><br><DIV align=center><IFRAME frameBorder=0 height=60 marginHeight=0 marginWidth=0 scrolling=no src="../../ad2.htm" width=468 bordercolor="#000000"></IFRAME></DIV><br></td>
  </tr>
</table>
</center></div>
<div align=center><table width=100%><tr bgcolor=blue><td></td></tr><td class=unnamed1 width=1%></td><tr><td width=100%><p align=center><code><span style=font-size:9pt>&copy; 2000 雅舍资讯 版权所有 转载请注明出处<br>All rights reserved</span></code></td></tr></table></div>
<div id="Layer01" style="position:absolute; left:14px; top:85px; width:100px; height:15px; z-index:5; background-color: #FFFFFF; layer-background-color: #FFFFFF; border: 1px none #FFFFFF;><font color="red"><font color=blue>当前在线</font></font><script
src="http://61.139.59.105/mssoft/online/online.asp?id=yasee"></script><font color=blue>人</DIV></body>
</html>