📄 ds6.4.2.htm
字号:
<![if !mso]>
<table cellpadding=0 cellspacing=0 width="100%">
<tr>
<td><![endif]>
<div>
<p class=MsoNormal align=center style='text-align:center'><span
lang=EN-US style='font-size:9.0pt;mso-bidi-font-size:10.0pt'>E<o:p></o:p></span></p>
</div>
<![if !mso]></td>
</tr>
</table>
<![endif]></v:textbox>
</v:shape><v:oval id="_x0000_s1031" style='position:absolute;left:2150;top:2603;
width:280;height:280' filled="f"/>
</v:group><![endif]-->
<!--[if gte vml 1]><v:group
id="_x0000_s1035" style='position:absolute;left:0;text-align:left;
margin-left:387pt;margin-top:7.9pt;width:14.05pt;height:16.8pt;z-index:4'
coordorigin="2150,2547" coordsize="281,336" o:allowincell="f">
<v:shape id="_x0000_s1036" type="#_x0000_t202" style='position:absolute;
left:2194;top:2547;width:237;height:336' stroked="f">
<v:textbox inset="0,0,0,0">
<![if !mso]>
<table cellpadding=0 cellspacing=0 width="100%">
<tr>
<td><![endif]>
<div>
<p class=MsoNormal align=center style='text-align:center'><span
lang=EN-US style='font-size:9.0pt;mso-bidi-font-size:10.0pt'>G<o:p></o:p></span></p>
</div>
<![if !mso]></td>
</tr>
</table>
<![endif]></v:textbox>
</v:shape><v:oval id="_x0000_s1037" style='position:absolute;left:2150;top:2603;
width:280;height:280' filled="f"/>
</v:group><![endif]-->
</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">之间的连线，删去它与其它孩子结点之间的连线。</span></b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">3.</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">以树的根结点为轴心，将整棵树顺时针转动一定</span></b></font><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font size="5" color="#FFFFFF"><b>的角度，使之结构层次分明。</b></font></span></p>
<p><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font size="5" color="#FFFFFF"><b>
可以证明，树作这样的转换所构成的二叉树是唯一的。图<span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">7.9(a)</span>、<span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">(b)</span>、<span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">(c)</span>给出了图<span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">7.8</span>所示的树转换为二叉树的转换过程示意图。</b></font></span></p>
<p align="center"><img border="0" src="ds6.4.8.gif" width="592" height="166"></p>
<p class="MsoNormal" style="margin-left:21.0pt"><font color="#FFFFFF" size="4"><b><span style="mso-spacerun: yes" lang="EN-US">
</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">(a)</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"></span></b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">相邻兄弟加连线</span><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><span style="mso-spacerun:
yes"> </span>(b)</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"></span></b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">删去双亲与其它孩子的连线</span><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><span style="mso-spacerun: yes">
</span>(c)</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman"></span></b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">转换后的二叉树</span></font></p>
<p class="MsoNormal" align="center" style="margin-left:21.0pt;text-align:center"><b><font color="#FFFFFF" size="4"><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">图</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">7.9<span style="mso-spacerun: yes">
</span></span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">图</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">7.8</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">所示树转换为二叉树的过程示意</span></font></b></p>
<p class="MsoNormal"> <b><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">由上面的转换可以看出，在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必为空。</span></font></b></p>
<font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA" lang="EN-US">
</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">事实上，一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的。</span></b></font><!--mstheme--></font>
<h4><!--mstheme--><font face="宋体" color="#CC6633"><font size="5" color="#FFFFFF"><b><span lang="EN-US">2<span style="mso-spacerun: yes">
</span></span><span style="font-family:黑体;mso-ascii-font-family:Arial">森林转换为二叉树</span></b></font><!--mstheme--></font></h4>
<!--mstheme--><font face="宋体">
<p class="MsoNormal" style="text-indent:21.0pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>由森林的概念可知，森林是若干棵树的集合，只要将森林中各棵树的根视为兄弟，每棵树又可以用二叉树表示，这样，森林也同样可以用二叉树表示。</b></font></span></p>
<p class="MsoNormal" style="text-indent:21.0pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>森林转换为二叉树的方法如下：</b></font></span></p>
<p class="MsoNormal" style="margin-left:47.25pt;text-indent:-26.25pt;mso-list:
l41 level1 lfo22;tab-stops:list 47.25pt"><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">（</span><span lang="EN-US"></span><span lang="EN-US" style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">1</span><span lang="EN-US"></span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">）</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">将森林中的每棵树转换成相应的二叉树。</span></b></font></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">（</span><span lang="EN-US">2</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。</span></b></font></p>
<p class="MsoNormal" style="margin-left:21.0pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>这一方法可形式化描述为：</b></font></span></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">如果</span><span lang="EN-US">F</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">＝</span><span lang="EN-US">{
T<sub>1</sub></span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">T<sub>2</sub></span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">…</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">T<sub>m</sub>
}</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">是森林，则可按如下规则转换成一棵二叉树</span><span lang="EN-US">B</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">＝（</span><span lang="EN-US">root</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">LB</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">RB</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">）。</span></b></font></p>
<p class="MsoNormal" style="margin-left:47.25pt;text-indent:-26.25pt;mso-list:
l31 level1 lfo41;tab-stops:list 47.25pt"><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">（</span><span lang="EN-US" style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">1</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">）</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">若</span><span lang="EN-US">F</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">为空，即</span><span lang="EN-US">m</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">＝</span><span lang="EN-US">0</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，则</span><span lang="EN-US">B</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">为空树；</span></b></font></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">（</span><span lang="EN-US">2</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">）若</span><span lang="EN-US">F</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">非空，即</span><span lang="EN-US">m</span><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman"">≠</span><span lang="EN-US">0</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，则</span><span lang="EN-US">B</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">的根</span><span lang="EN-US">root</span><span style="font-family:
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -