📄 ds6.4.3.htm
字号:
</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>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
<!--msthemelist--><tr>
<!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
<td valign="top" width="100%"><!--mstheme--><font face="宋体"><!--mstheme--></font>
<h4><!--mstheme--><font face="宋体" color="#CC6633"><b><font size="5" color="#FFFFFF"><span style="font-family:黑体;mso-ascii-font-family:Arial">森林的遍历</span></font></b><!--mstheme--></font></h4>
<!--mstheme--><font face="宋体"><!--mstheme--></font><!--msthemelist--></td>
</tr>
<!--msthemelist--></table>
<!--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>
<!--mstheme--></font>
<h5><!--mstheme--><font face="宋体" color="#6666FF"><b><font size="5" color="#FFFFFF"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; mso-fareast-font-family: 黑体"><span style="mso-spacerun: yes">
</span>1</span><span style="mso-bidi-font-size: 10.0pt; font-family: 黑体; mso-ascii-font-family: Times New Roman">．前序遍历</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; mso-fareast-font-family: 黑体"><o:p>
</o:p>
</span></font></b><!--mstheme--></font></h5>
<!--mstheme--><font face="宋体">
<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>
<ol>
<li>
<p class="MsoNormal" style="margin-left:47.25pt;text-indent:-26.25pt;mso-list:
l28 level1 lfo28;tab-stops:list 47.25pt"><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></li>
<li>
<p class="MsoNormal" style="margin-left:47.25pt;text-indent:-26.25pt;mso-list:
l28 level1 lfo28;tab-stops:list 47.25pt"><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></li>
<li>
<p class="MsoNormal" style="margin-left:47.25pt;text-indent:-26.25pt;mso-list:
l28 level1 lfo28;tab-stops:list 47.25pt"><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></li>
</ol>
<p class="MsoNormal" style="margin-left:21.0pt"><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><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><font size="5" color="#FFFFFF"><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman""><img border="0" src="ds6.4.12.gif" align="left" width="304" height="109"></span></font></b></p>
<p class="MsoNormal" style="margin-left:21.0pt"><span lang="EN-US"><b><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes">
</span>A B C D E F G H J I K</font></b></span></p>
<p class="MsoNormal" style="margin-left:21.0pt"> </p>
<p class="MsoNormal" style="margin-left:21.0pt"> </p>
<!--mstheme--></font>
<h5><!--mstheme--><font face="宋体" color="#6666FF"><font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; mso-fareast-font-family: 黑体" lang="EN-US">
</span></b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; mso-fareast-font-family: 黑体"><b>2</b></span><b><span style="mso-bidi-font-size: 10.0pt; font-family: 黑体; mso-ascii-font-family: Times New Roman">．中序遍历</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; mso-fareast-font-family: 黑体"><o:p>
</o:p>
</span></b></font><!--mstheme--></font></h5>
<!--mstheme--><font face="宋体">
<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>
<ol>
<li>
<p class="MsoNormal" style="margin-left:47.25pt;text-indent:-26.25pt;mso-list:
l27 level1 lfo29;tab-stops:list 47.25pt"><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></li>
<li>
<p class="MsoNormal" style="margin-left:47.25pt;text-indent:-26.25pt;mso-list:
l27 level1 lfo29;tab-stops:list 47.25pt"><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></li>
<li>
<p class="MsoNormal" style="margin-left:47.25pt;text-indent:-26.25pt;mso-list:
l27 level1 lfo29;tab-stops:list 47.25pt"><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></li>
</ol>
<p class="MsoNormal" style="margin-left:21.0pt"><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><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 lang="EN-US"><b><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes">
</span>B A D E F C J H K I G</font></b></span></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>
<p align="left"> </p>
<p align="center"><b><a href="ds6.4.HTM"><font size="5" color="#FFFF00">返回</font></a></b></p>
<!--mstheme--></font>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -