📄 ds6.4.2.htm
字号:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">即为森林中第一棵树的根</span><span lang="EN-US">Root(T1)</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">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">T1</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">中根结点的子树森林</span><span lang="EN-US">F1</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>11</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>12</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>1m1</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">RB</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>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">T<sub>3</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></b></font></p>
<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">图</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.10</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 align="center"><img border="0" src="ds6.4.9.gif" width="520" height="256"></p>
<p align="center"><b><font size="5" color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">图<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.10<span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
</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; 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></span></font></b></p>
<!--mstheme--></font>
<h4><!--mstheme--><font face="宋体" color="#CC6633"><b><span lang="EN-US"><font size="5" color="#FFFFFF">3<span style="mso-spacerun: yes">
</span></font></span><font size="5" color="#FFFFFF"><span style="font-family:黑体;mso-ascii-font-family:Arial">二叉树转换为树和森林</span></font></b><!--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""><b><font size="5" color="#FFFFFF">树和森林都可以转换为二叉树，二者不同的是树转换成的二叉树，其根结点无右分支，而森林转换后的二叉树，其根结点有右分支。显然这一转换过程是可逆的，即可以依据二叉树的根结点有无右分支，将一棵二叉树还原为树或森林，具体方法如下：</font></b></span></p>
<p class="MsoNormal"><b><span style="mso-spacerun: yes" lang="EN-US"><font size="5" color="#FFFFFF">
</font></span><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">（</span><span lang="EN-US">1</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></font></b></p>
<p class="MsoNormal"><b><span style="mso-spacerun: yes" lang="EN-US"><font size="5" color="#FFFFFF">
</font></span><font size="5" color="#FFFFFF"><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></font></b></p>
<p class="MsoNormal" style="margin-left:21.0pt"><b><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF">（</font></span><font size="5" color="#FFFFFF"><span lang="EN-US">3</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">）整理由（</span><span lang="EN-US">1</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></font></b></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""><b><font size="5" color="#FFFFFF">这一方法可形式化描述为：</font></b></span></p>
<p class="MsoNormal"><b><span style="mso-spacerun: yes" lang="EN-US"><font size="5" color="#FFFFFF">
</font></span><font size="5" color="#FFFFFF"><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><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></font></b></p>
<p class="MsoNormal"><b><span style="mso-spacerun: yes" lang="EN-US"><font size="5" color="#FFFFFF">
</font></span><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">（</span><span lang="EN-US">1</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">F</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">为空；</span></font></b></p>
<p class="MsoNormal"><b><span style="mso-spacerun: yes" lang="EN-US"><font size="5" color="#FFFFFF">
</font></span><font size="5" color="#FFFFFF"><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">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">T1</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">T1</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">T1</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">中根结点的子树森林</span><span lang="EN-US">F1</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">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">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">T1</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>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">T<sub>3</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">RB</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">转换而成的森林。</span></font></b></p>
<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"><font size="5" color="#FFFFFF">图</font></span><font size="5" color="#FFFFFF"><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.11</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></font></b>
<p align="center"><img border="0" src="ds6.4.10.gif" width="568" height="299"></p>
<p align="center"><b><font size="5" color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">图<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.11<span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
</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; 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></span></font></b></p>
<p align="center"> </p>
<p align="center"><a href="ds6.4.HTM"><b><font size="5" color="#FFFF00">返回</font></b></a></p>
<!--mstheme--></font>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -