📄 chapter5.htm
字号:
<html><!-- #BeginTemplate "/Templates/article_template.dwt" -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="algorithm, data structure, contest, programming, 算法, 数据结构, 程序设计, 竞赛">
<meta name="description" content="discussing the algorithm and data structure of computer programming, as well as all kinds of programming contest.">
<meta name="description" content="讨论程序设计的算法与数据结构，各类程序设计竞赛试题解析和参赛经验介绍。">
<!-- #BeginEditable "doctitle" -->
<title>树的遍历</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
var previous = "chapter4.htm";
var next = "chapter6.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h2>树的遍历</h2>
<p>树的遍历是树的一种重要的运算。所谓<font face="楷体_GB2312">遍历</font>是指对树中所有结点的系统的访问，即依次对树中每个结点访问一次且仅访问一次。树的3种最重要的遍历方式分别称为<font face="楷体_GB2312">前序遍历</font>、<font face="楷体_GB2312">中序遍历</font>和<font face="楷体_GB2312">后序遍历</font>。以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的<font face="楷体_GB2312">前序列表</font>，<font face="楷体_GB2312">中序列表</font>和<font face="楷体_GB2312">后序列表</font>。相应的结点次序分别称为结点的前序、中序和后序。</p>
<p>树的这3种遍历方式可递归地定义如下：</p>
<ul>
<li>
<p style="margin-top: 5; margin-bottom: 5">如果T是一棵空树，那么对T进行前序遍历、中序遍历和后序遍历都是空操作，得到的列表为空表。
</li>
<li>
<p style="margin-top: 5; margin-bottom: 5">如果T是一棵单结点树，那么对T进行前序遍历、中序遍历和后序遍历都只访问这个结点。这个结点本身就是要得到的相应列表。
</li>
<li>
<p style="margin-top: 5; margin-bottom: 5">否则，设T如图6所示，它以n为树根，树根的子树从左到右依次为T<sub>1</sub>,T<sub>2</sub>,..,T<sub>k</sub>，那么有：
<ol>
<li>
<p style="margin-top: 5; margin-bottom: 5">对T进行前序遍历是先访问树根n,然后依次前序遍历T<sub>1</sub>,T<sub>2</sub>,..,T<sub>k</sub>。
</li>
<li>
<p style="margin-top: 5; margin-bottom: 5">对T进行中序遍历是先中序遍历T<sub>1</sub>，然后访问树根n，接着依次对T<sub>2</sub>,T<sub>2</sub>,..,T<sub>k</sub>进行中序遍历。
</li>
<li>
<p style="margin-top: 5; margin-bottom: 5">对T进行后序遍历是先依次对T<sub>1</sub>,T<sub>2</sub>,..,T<sub>k</sub>进行后序遍历，最后访问树根n。
</li>
</ol>
</li>
</ul>
<p style="margin-top: 5; margin-bottom: 5" align="center"><img border="0" src="images/img9.gif" width="304" height="227"></p>
<p style="margin-top: 5; margin-bottom: 5" align="center">图6 树T</p>
<p>前序遍历和中序遍历可形式地依次描述如下</p>
<p>三种遍历可以形式地描述如下，其中用到了<a href="chapter4.htm">树的ADT操作</a>：</p>
<div align="center">
<center>
<table border="0" width="90%" style="font-size: 10pt" cellpadding="5">
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5">Procedure Preorder_Traversal(v:NodeType);
{前序遍历算法}</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> Visite(v); {访问节点v}</p>
<p style="margin-top: 5; margin-bottom: 5"> i:=Leftmost_Child(v);</p>
<p style="margin-top: 5; margin-bottom: 5"> while i<>∧ do</p>
<p style="margin-top: 5; margin-bottom: 5"> begin</p>
<p style="margin-top: 5; margin-bottom: 5"> Preorder_Traversal(i);{从左到右依次访问v的每一个儿子节点i}</p>
<p style="margin-top: 5; margin-bottom: 5"> i:=Right_Sibling(i);</p>
<p style="margin-top: 5; margin-bottom: 5"> end;</p>
<p style="margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5">Procedure Inorder_Traversal(v:NodeType);
{中序遍历算法}</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5">if Leftmost_Child(v)=∧
{判断v是否是叶节点}</p>
<p style="margin-top: 5; margin-bottom: 5"> then Visite(v)</p>
<p style="margin-top: 5; margin-bottom: 5"> else</p>
<p style="margin-top: 5; margin-bottom: 5"> begin</p>
<p style="margin-top: 5; margin-bottom: 5">
Inorder_Traversal(Leftmost_Child(v)); {中序遍历v的左边第一个儿子节点}</p>
<p style="margin-top: 5; margin-bottom: 5">
Visite(v); {访问节点v}</p>
<p style="margin-top: 5; margin-bottom: 5">
i:=Right_Sibling(Leftmost_Child(v)); {i=v的左边第二个儿子}</p>
<p style="margin-top: 5; margin-bottom: 5">
while i<>∧ do</p>
<p style="margin-top: 5; margin-bottom: 5">
begin</p>
<p style="margin-top: 5; margin-bottom: 5">
Inorder_Traversal(i);</p>
<p style="margin-top: 5; margin-bottom: 5">
{从左边第二个开始到最右边一个为止依次访问v的每一个儿子节点i}</p>
<p style="margin-top: 5; margin-bottom: 5">
i:=Right_Sibling(i);</p>
<p style="margin-top: 5; margin-bottom: 5">
end;</p>
<p style="margin-top: 5; margin-bottom: 5"> end;</p>
<p style="margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5">Procedure Postorder_Traversal(v:NodeType);
{后序遍历算法}</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> i:=Leftmost_Child(v);</p>
<p style="margin-top: 5; margin-bottom: 5"> while i<>∧ do</p>
<p style="margin-top: 5; margin-bottom: 5"> begin</p>
<p style="margin-top: 5; margin-bottom: 5"> Preorder_Traversal(i);{从左到右依次访问v的每一个儿子节点i}</p>
<p style="margin-top: 5; margin-bottom: 5"> i:=Right_Sibling(i);</p>
<p style="margin-top: 5; margin-bottom: 5"> end;</p>
<p style="margin-top: 5; margin-bottom: 5"> Visite(v); {访问节点v}</p>
<p style="margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
</table>
</center>
</div>
<p>为了将一棵树中所有结点按某种次序列表，只须对树根调用相应过程。例如对图7中的树进行前序遍历、中序遍历和后序遍历将分别得到前序列表：A
B E F I J C D G H；中序列表：E B I F J A C G D H；后序列表：E I J F B C G H D A。</p>
<blockquote>
<p align="center"><img border="0" src="images/img4.gif" width="377" height="269"></p>
<p align="center">图7 一棵树</p>
</blockquote>
<p> 下面介绍一种方法可以产生上述3种遍历方式的结点列表。设想我们从树根出发，依逆时针方向沿树的外缘绕行(例如围绕图7中的树绕行的路线如图8所示)。绕行途中可能多次经过同一结点。如果我们按第一次经过的时间次序将各个结点列表，就可以得到前序列表；如果按最后一次经过的时间次序列表，也就是在即将离开某一结点走向其父亲时将该结点列出，就得到后序列表。为了产生中序列表，要将叶结点与内部结点加以区别。叶结点在第一次经过时列出，而内部结点在第二次经过时列出。</p>
<blockquote>
<p align="center"><img border="0" src="images/img10.gif" width="312" height="278"></p>
<p align="center">图8 树的遍历</p>
</blockquote>
<p>在上述3种不同次序的列表方式中，各树叶之间的相对次序是相同的，它们都按树叶之间从左到右的次序排列。3种列表方式的差别仅在于内部结点之间以及内部结点与树叶之间的次序有所不同。</p>
<p>对一棵树进行前序列表或后序列表有助于查询结点间的祖先子孙关系。假设结点v在后序列表中的序号(整数)为postorder(v)，我们称这个整数为结点v的<font face="楷体_GB2312">后序编号</font>。例如在图7中，结点E，I和J的后序编号分别为1，2和3。</p>
<p>结点的后序编号具有这样的特点：设结点v的真子孙个数为desc(v)，那么在以v为根的子树中的所有结点的后序编号恰好落在postorder(v)-desc(v)与postorder(v)之间。因此为了检验结点x是否为结点y的子孙，我们只要判断它们的后序编号是否满足：</p>
<blockquote>
<blockquote>
<p>postorder(y)-desc(y)≤postorder(x)≤postorder(y)</p>
</blockquote>
</blockquote>
<p><font face="楷体_GB2312"> <b>前序编号</b></font>也具有类似的性质。</p>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -