二叉树序列中的“层序序列”是什么?在自考题中遇到：已知一颗二叉树的中序序列为“abcdefg",层序序列为“bafegcd”,请画出该二叉树.我们学的是前、中、后序列,没记得有层序序列.

Question

二叉树序列中的“层序序列”是什么?
在自考题中遇到：已知一颗二叉树的中序序列为“abcdefg",层序序列为“bafegcd”,请画出该二叉树.我们学的是前、中、后序列,没记得有层序序列.

Answer 1

Chi's_喵!!
首先 层序序列其实就是按照层次来排序 不过比较少见 ：
例如这个二叉树：A
/ \
B C
/ / \
D E F
\
G
它的层序序列就是：ABCDEFG 就是按从上到下(从顶到底) 从左到右 来排序
您的题目是“已知一颗二叉树的中序序列为“abcdefg",层序序列为“bafegcd”,请画出该二叉树”
解题步骤如下：
首先 中序遍历(即“中序序列” 应该叫遍历正规点吧) 就是LDR(左根右 以下简称“LDR”)
层序遍历上面解释了 就是按层次来遍历的
然后 先看 层序遍历“bafegcd” 由此可知 B在最前面 即B是整个二叉树的根结点
咱可以把 中序遍历“abcdefg"根据LDR分为三份：A (左) B(根) CDEFG(右)
因此 先画出B：B
(根)
接下来
根据中序遍历“abcdefg”可知A是B的右孩子
因此 二叉树变为这样：B (根)
/ \
(左) A CDEFG(右)
(因为在层序遍历“bafegcd”中 C和D排在后面 是底层部分的 因此不会是B的右孩子 但肯定是B的右孩子之后分支出来的)
然后 再看层序遍历“bafegcd” F排在A的后面 亦排在EGCD的前面 即和A同层或在A的下一层
而根据中序遍历“abcdefg” 可知 A没有孩子 可判断F不会在A的下一层 只能和A同层
A (左) B(根) CDEFG(右)里的 CDEFG(右)可以变为：CDE(左) F(根) G(右)
因此可得下图：B
/ \
A F(根)
/ \
(左)CDE G(右)
接下来根据层序遍历“bafegcd” 可知E在CD的前面 又和G同层 说明CD肯定是E的子孙
根据中序遍历的LDR 又可以将：CDE 分成：CD(左) E(根)
因此可得下图：B
/ \
A F
/ \
(根)E G
/
(左)CD
根据层序遍历“bafegcd” 可知 C在D的左边 或者在D的上边
[层序遍历从上到下(从顶到底) 从左到右]
再根据中序遍历“abcdefg" 还有上图 CD(左) E(根)
可知 E只有左孩子而没有右孩子 因此 C在D的左边条件是不成立的 只能在D的上边
因此 CD又可以分为：C(根) D(右)
最后可得下图：B
/ \
A F
/ \
E G
/
C
\
D
至此解题完毕~
顺便列出所有遍历：
先序遍历：BAFECDG
中序遍历：ABCDEFG
后序遍历：ADCEGFB
层序遍历：BAFEGCD
(解题过程如有任何错误或疑问请尽情提出~)
纯手打~希望能帮到您~!