📄 ds6.3.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 size="6" color="#FFFF00">6.3.2
</font></span></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"><b><font color="#FFFF00" size="6">由遍历序列恢复二叉树</font></b></span></p>
<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" 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" 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" 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" 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" style="text-indent:21.0pt"><span lang="EN-US"><b><span style="mso-spacerun: yes"><font size="5" color="#FFFFFF">
</font></span><font size="5" color="#FFFFFF">A B C D E F G H I</font></b></span></p>
<p class="MsoNormal" style="text-indent:21.0pt"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><font size="5"><b>B C A E D G H F
I</b></font></font></span></p>
<p class="MsoNormal"><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" style="text-indent:21.0pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>首先，由先序序列可知，结点</b></font></span><b><font size="5" color="#FFFFFF"><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">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">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">6.10
(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">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">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">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">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">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">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">E</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">G</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">、</span><span lang="EN-US">H</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">、</span><span lang="EN-US">I</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，如图</span><span lang="EN-US">6.10 (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">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">6.10
(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"> <o:p>
</o:p>
</span></font></b></p>
<p align="center"><font size="5" color="#FFFFFF"><b><img border="0" src="ds6.3.1.gif" width="580" height="236"></b></font></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -