📄 ds6.4.2.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>数 据 结 构</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>
<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">
<!--mstheme--><font face="宋体"><p:colorscheme
colors="#0000FF,#FFFFFF,#000000,#FFCC66,#00FFFF,#3366FF,#FF0033,#FFFF00"/>
<p align="center"><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 color="#FFFF00" size="6">6.4.2
森林与二叉树的转换</font></span></b></p>
<p align="left"><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></b></p>
<!--mstheme--></font>
<h4><!--mstheme--><font face="宋体" color="#CC6633"><font size="5" color="#FFFFFF"><b><span lang="EN-US">1<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"><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">7.8</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">所示的一棵树，根结点</span><span lang="EN-US">A</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">C</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">、</span><span lang="EN-US">D</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">A</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">的第一个孩子结点，结点</span><span lang="EN-US">C</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">为</span><span lang="EN-US">A</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">D</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">为</span><span lang="EN-US">A</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">的第三个孩子结点。</span></b></font></p>
<p align="left"><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><img border="0" src="ds6.4.6.gif" align="right" width="153" height="116"></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">1.树中所有相邻兄弟之间加一条连线。</span><!--[if gte vml 1]><v:line id="_x0000_s1039"
style='position:absolute;left:0;text-align:left;z-index:6' from="336.45pt,8.6pt"
to="346.1pt,30.25pt" o:allowincell="f"/><![endif]-->
<!--[if gte vml 1]><v:line
id="_x0000_s1038" style='position:absolute;left:0;text-align:left;flip:x;
z-index:5' from="314.65pt,8.05pt" to="325.05pt,31.1pt" o:allowincell="f"/><![endif]-->
<!--[if gte vml 1]><v:line
id="_x0000_s1040" style='position:absolute;left:0;text-align:left;flip:x;
z-index:7' from="394.8pt,7.9pt" to="396pt,27.05pt" o:allowincell="f"/><![endif]-->
<span style="mso-ignore:vglayout;position:absolute;z-index:14;left:0px;margin-left:
525px;margin-top:10px;width:5px;height:28px"><img src="ds6.4.7.gif" v:shapes="_x0000_s1040" width="5" height="28"></span><!--[if gte vml 1]><v:group
id="_x0000_s1026" style='position:absolute;left:0;text-align:left;
margin-left:355.25pt;margin-top:0;width:14.05pt;height:16.8pt;z-index:1'
coordorigin="2150,2547" coordsize="281,336" o:allowincell="f">
<v:shapetype id="_x0000_t202" coordsize="21600,21600" o:spt="202" path="m0,0l0,21600,21600,21600,21600,0xe">
<v:stroke joinstyle="miter"/>
<v:path gradientshapeok="t" o:connecttype="rect"/>
</v:shapetype><v:shape id="_x0000_s1027" 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'>C<o:p></o:p></span></p>
</div>
<![if !mso]></td>
</tr>
</table>
<![endif]></v:textbox>
</v:shape><v:oval id="_x0000_s1028" style='position:absolute;left:2150;top:2603;
width:280;height:280' filled="f"/>
</v:group><![endif]-->
</b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>2.<span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">对树中的每个结点，只保留它与第一个孩子结点</span><!--[if gte vml 1]><v:group id="_x0000_s1032" style='position:absolute;left:0;
text-align:left;margin-left:337.1pt;margin-top:8.65pt;width:14.05pt;height:16.8pt;
z-index:3' coordorigin="2150,2547" coordsize="281,336" o:allowincell="f">
<v:shape id="_x0000_s1033" 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'>F<o:p></o:p></span></p>
</div>
<![if !mso]></td>
</tr>
</table>
<![endif]></v:textbox>
</v:shape><v:oval id="_x0000_s1034" style='position:absolute;left:2150;top:2603;
width:280;height:280' filled="f"/>
</v:group><![endif]-->
<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"><!--[if gte vml 1]><v:group
id="_x0000_s1029" style='position:absolute;left:0;text-align:left;
margin-left:306pt;margin-top:7.9pt;width:14.05pt;height:16.8pt;z-index:2'
coordorigin="2150,2547" coordsize="281,336" o:allowincell="f">
<v:shape id="_x0000_s1030" type="#_x0000_t202" style='position:absolute;
left:2194;top:2547;width:237;height:336' stroked="f">
<v:textbox inset="0,0,0,0">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -