1. 激活谷首页
  2. 激活谷笔记

二叉搜索树先序后序能确定一棵么_二叉搜索树先序后序能确定一棵么

• 激活谷笔记

二叉搜索树先序后序能确定一棵么_二叉搜索树先序后序能确定一棵么【数据结构与算法】”先序+后序”能否确定二叉树结构？一个简单的判别法0. 引入： 二叉树的遍历搜索是对非线性结构的一种线性化操作，经典算法包括先序、中序、后序搜索。假定已知遍历结果，能否确定二叉树结构？以下是教科书中的回答：已知序列能否确定先序+中序一定可以中序+后序一定可以先序+后序不一定为什么先

【数据结构与算法】”先序+后序”能否确定二叉树结构？一个简单的判别法 　　0. 引入： 二叉树的遍历搜索是对非线性结构的一种线性化操作，经典算法包括先序、中序、后序搜索。假定已知遍历结果，能否确定二叉树结构？以下是教科书中的回答：已知序列能否确定先序+中序一定可以中序+后序一定可以先序+后序不一定为什么先序+后序不一定能推出二叉树？可参考以下例子：
二叉搜索树先序后序能确定一棵么_二叉搜索树先序后序能确定一棵么
二叉搜索树先序后序能确定一棵么_二叉搜索树先序后序能确定一棵么例子在上图(1)(2)中，先序的遍历结果都是AB，后序的遍历结果都是BA，然而对应了两种结构，故无法判定；但当先序序列是ABC，后序序列是BAC时，唯一确定了图(3)。 　　我们当然可以照着结果序列一步步创建二叉树，再判断原树是否唯一；然而这种做法太过麻烦。有没有一种简单的判别法能够根据先后两个序列，迅速地判断它们能否确定二叉树？笔者想出了以下定理：定理：先、后序列能否确定二叉树结构等价于两个序列是否存在长度为2且顺序相反的公共子串。注：当先序序列出现”
...\bold{XY}......” ，后序序列出现”
....\bold{YX}.. “时（紧密相连），一定不能确定二叉树的结构；反之，如果不满足上述条件，则可以确定。 　　定理的严格证明需要用到以下等价判定引理，然后再证明定理与引理等价。 　　2. 引理：先、后序列能否确定二叉树结构等价于二叉树是否只有度为0或2的结点。注：也就是说，如果存在度为1的结点，那么就不能确定了。 　　证明： 　　遍历（递归法）的代码： 　　对于一棵二叉树
\mathcal{T} ，我们把其先序遍历结果记为
\mathbb{D}\mathbb{L}\mathbb{R} ，后序的记为
\mathbb{L}\mathbb{R}\mathbb{D} 。遍历结果序列递归地满足这种顺序。 　　当二叉树中含有一个度为1的结点（记为
\mathcal{P}_{0} ）时，这个结点只有一个孩子结点。我们把这个孩子节点及其延申的子树记为
\mathcal{T}_{0} ，它可以是右孩子也可以是左孩子。
二叉搜索树先序后序能确定一棵么_二叉搜索树先序后序能确定一棵么
二叉搜索树先序后序能确定一棵么_二叉搜索树先序后序能确定一棵么子树T0在右
二叉搜索树先序后序能确定一棵么_二叉搜索树先序后序能确定一棵么
二叉搜索树先序后序能确定一棵么_二叉搜索树先序后序能确定一棵么子树T0在左 　　根据递归代码可知，对于两种树，它们的
\mathbb{D}\mathbb{L}\mathbb{R}中均出现了
...\mathcal{P}_{0}\mathcal{T}_{0}... ，
\mathbb{L}\mathbb{R}\mathbb{D}中也均出现了
...\mathcal{T}_{0}\mathcal{P}_{0}...；可以归纳地证明，如果没有度为1的结点，不会有上述结果。引理的充分性与必要性证明显然。引理本质上与文章开头提到的“一步步创建再判断”没有区别，因为判断是否存在度为1的结点还是要一步步打草稿，过程依然是繁琐而低效的。 　　3. 引理与定理等价 　　证明： 　　考虑2的如下结论：对于一棵二叉树
\mathcal{T} ，我们把其先序遍历结果记为
\mathbb{D}\mathbb{L}\mathbb{R} ，后序的记为
\mathbb{L}\mathbb{R}\mathbb{D} 。遍历结果序列递归地满足这种顺序。 　　(i). 充分性(
\Rightarrow ): 　　“度为1”
\Leftrightarrow 仅有一个孩子结点 　　
\Leftrightarrow 结果序列中某个部分缺失了
\mathbb{R} 或
\mathbb{L} 　　
\Leftrightarrow 该部分的两种序列变为
\mathbb{L}\mathbb{D} 与
\mathbb{D}\mathbb{L} 或
\mathbb{D}\mathbb{R} 与
\mathbb{R}\mathbb{D} ，即定理所述情况。 　　(ii). 必要性(
\Leftarrow ): 　　当先序序列出现”
...\bold{XY}......” ，后序序列出现”
....\bold{YX}.. “时，结点
\bold{X} 必为
\bold{Y} 的双亲；所以它们所共同存在的子树必然递归地满足
\mathbb{D}\mathbb{L}\mathbb{R} 与
\mathbb{L}\mathbb{R}\mathbb{D} 的形式。 　　为了让序列
\mathbb{D}\mathbb{L}\mathbb{R} 与
\mathbb{L}\mathbb{R}\mathbb{D} 相反，必须删除
\mathbb{R} 或
\mathbb{L}，也就是出现了度为1的结点。 　　证毕。 　　4. 代码实现 　　5. 一点思考 　　这是树的定义：树是
n (n \geq 0) 个结点的有限集。当
n = 0 时，称为空树。在任意一棵非空树中应满足：有且仅有一个特定的称为根的结点。当
二叉搜索树先序后序能确定一棵么_二叉搜索树先序后序能确定一棵么1″ eeimg=”1″> 时，其余节点可分为
二叉搜索树先序后序能确定一棵么_二叉搜索树先序后序能确定一棵么0)” eeimg=”1″> 个互不相交的有限集
T_{1},T_{2},…,T_{m} ，其中每个集合本身又是一棵树，并且称为根的子树。 　　可以看到其定义是递归的，自然延伸出了许多递归算法；正因如此，在2与3的证明中，我们才把一个结点及其延申又看作了一棵树。 　　图片来自绘图网站：CS Academy

2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/87419.html

赞 (0)
0
上一篇 2024年 7月 25日
下一篇 2024年 7月 26日

相关推荐

关注微信