已知前序序列为ABDGCEF中序序列为DGBAECF试构造此二叉树并写出后序遍历的序列。
构造过程:
- 前序序列第一个元素为根节点,即A。
- 在中序序列中找到A,将其左侧的序列DGB与右侧的序列ECF分别作为左子树和右子树的中序序列。
- 在前序序列中,根节点A后面的元素为左子树的前序序列,即BDG;A后面到序列末尾为右子树的前序序列,即CEF。
- 对左子树和右子树分别重复步骤1-3,直到序列中没有元素。
构造出的二叉树如下:
A
/ \
B C
/ \ / \
D G E F
后序遍历序列为DGBCFEA。
原文地址: https://www.cveoy.top/t/topic/eFlT 著作权归作者所有。请勿转载和采集!