企业在网站推广,免费的图库网站,深圳网站制作推广,南宁网络推广培训机构0 .概述
介绍下二叉树重构
1. 遍历序列
任何一棵二叉树我们都可以导出先序、中序、后序遍历序列。这三个序列的长度相同#xff0c;他们都是由树中的所有节点依照相应的遍历策略所确定的次序#xff0c;依次排列而成。
若已知某棵树的遍历序列是否可以忠实地还原出这棵树…0 .概述
介绍下二叉树重构
1. 遍历序列
任何一棵二叉树我们都可以导出先序、中序、后序遍历序列。这三个序列的长度相同他们都是由树中的所有节点依照相应的遍历策略所确定的次序依次排列而成。
若已知某棵树的遍历序列是否可以忠实地还原出这棵树地拓扑结构什么情况下可以什么情况下不可以?如果可以具体又应该使用什么方法
2. 先序 | 后序 中序
结论只需中序遍历序列再加上先序与后序遍历序列之一即可忠实还原二叉树地完整拓扑结构。 对于上述结论做证明为此需要做数学归纳 假设对于规模小于N地所有二叉树这个规律都是成立的接下来考虑规模恰好为N的二叉树。 不失一般性可以将二叉树画成上图所示的样子。 先序遍历序列r L R 中序遍历序列L r R 因此根据先序遍历可以明确树根节点是谁进而可以在中序遍历序列中对这个节点进行定位。这个定位非常重要它使我们得以确认左子树所对应的中序遍历子序列以及右子树所对应的中序遍历子序列。也就是说我们可以知道左子树和右子树分别是由哪些节点组成。因此只要这两个遍历序列是合法的反过来在先序遍历序列中就可以很容易地将左子树和右子树所对应地遍历子序列切分开。 ~ 这样成功地将原来全树地重构问题化解为两棵子树地重构问题。不难看出这两棵子树在规模上都符合归纳假设也就是它们都严格地小于N因此根据归纳假设无论是左子树还是右子树的确都可以如此重构出来。 注意无论是左子树还是右子树都有可能是空树这种情况下树的规模应该是0。
不借助中序遍历序列而只凭借先序和后序遍历序列是否也能保证完成对左右子树地正确切分呢答案是不能保证的。 原因是无论L 还是R都有可能是空树比如右子树是空的那么它对应的遍历 先序遍历序列 r L 后序遍历序列 L r 反过来若左子树是空的那么它对应的遍历 先序遍历序列 r R 后序遍历序列 R r 可以看到这里出现了歧义我们无法根据先序遍历序列以及后序遍历序列来区分在这种情况下除去根节点之后的部分究竟是左子树还是右子树。 3. [先序 后序 ] x 真 由先序和后序遍历序列的确也可以还原树的整体结构。比如对于所谓的真二叉树就是这样。 所谓的真二叉树其中每个节点的度数都必须是偶数确切说是除了0就是2度而1度节点是严格禁止的。因此非退化的真二叉树模式无非如上图。注意此时的左子树和右子树要么同时为空要么同时非空前一种情况显而易见因此不妨假设他们都存在。于是这棵树的遍历先序遍历序列和后序遍历序列如下。 左子树的树根节点 l 在先序遍历序列中必然名列第二位置是确定的因此反过来在任何给定的先序遍历序列中都可以便捷地找到它进而在后序遍历序列中对它进行定位。这个节点在它所属地这棵子树地后序遍历子序列中必然垫后。这就意味着可以明确地界定左右子树范围。即左子树由哪些节点构成右子树由哪些节点构成都是可以确定的。当然对称的在后序遍历序列中右子树的树根位置也是确定的因此通过右子树的树根节点依然可以反过来在先序遍历序列中进行定位而且同样地可以确定左右子树地切分位置。 通过上述描述确实可以进行分而治之从而通过递归的形式完整地重构出一棵真二叉树。
