📄 ds6.4.3.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.3
树和森林的遍历</font></span></b></p>
<!--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"><span style="font-family:黑体;mso-ascii-font-family:Arial"><b><font size="5" color="#FFFFFF">树的遍历</font></b></span><!--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:
l22 level1 lfo25;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:
l22 level1 lfo25;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"><img border="0" src="ds6.4.11.gif" width="204" height="159" align="left"></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 E F C D G</font></b></span></p>
<p class="MsoNormal" style="margin-left:21.0pt"> </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:
l10 level1 lfo26;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:
l10 level1 lfo26;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><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>E F B C G D A</font></b></span></p>
<p style="margin-bottom: 20"><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: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-spacerun: yes; mso-fareast-font-family: 宋体" lang="EN-US">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -