Question

已知一棵二叉树的前序序列为A B D G C E H I F;中序序列为:D G B A E I H C F,画出二叉树并写出它的后序？

Answer 1

二叉树的后序为G、D、B、I、H、E、F、C、A。

由前前序第一个为A，所以根节点，所以A的左子树为D、G、B，右子树为E、I、H、C、F。第二个根节点为B，又由中序的出B的左子树为D、G，然后得出D的右子树为G，C为A的右子树，依次进行判断，最后的出二叉树的序列。

二叉树图，如下图：

扩展资料：

二叉树性质：

1、二叉树的第i层上至多有2i-1（i≥1）个节点。

2、深度为h的二叉树中至多含有2h-1个节点。

3、若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。

4、具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）。

5、若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

当i=1时，该节点为根，它无双亲节点。

当i>1时，该节点的双亲节点的编号为i/2。

若2i≤n，则有编号为2i的左节点，否则没有左节点。

若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。

参考资料来源：百度百科-二叉树

Answer 2

后序：

GDBIHEFCA