二叉树的后序遍历访问顺序是gdbehfca, 中序遍历访问顺序是dgbaechf, 则其前序遍历？

发布网友发布时间：2022-05-26 11:44

共2个回答

热心网友时间：2023-10-15 13:17

得到的树：a为根节点，b为其左孩子，c为右孩子；d为b左孩子，g为d右孩子；e为c左孩子，f为c右孩子，h为f左孩子
前序是abdgcefh？

热心网友时间：2023-10-15 13:18

中序：左子树--> 根节点--> 右子树

后序：左子树--> 右子树-->根节点

先序：根节点-->左子树-->右子树

由前序遍历结果可知a为根节点，再看中序遍历结果，因为中序遍历顺序是左子树、根、右子树，因此由“中序遍历顺序是dgbaechf”可断定，dgb为该二叉树的左子树中序遍历结果，echf为右子树中序遍历结果。

由前序遍历结果可知，左子树的前序遍历结果是bdg，右子树的前序遍历结果是cefh，因此，可知b为左子树的根，再由“dgb为该二叉树的左子树中序遍历结果”可知，dg为该左子树的左子树的中序遍历结果。

再由dg在前序遍历结果中排列顺序dg可知，d为根，因此由“dg为该左子树的左子树的中序遍历结果”可推出g为d的右孩子。可以完全推断出该二叉树的左子树的结构了。

按照同样方法，可以推断出该二叉树的右子树的结构该二叉树的后序遍历结果是：gdbehfca。

扩展资料：

从根结点开始，假设根结点为第1层，根结点的孩子结点为第2层，如果某一个结点位于第L层，则其孩子结点位于第L+1层。

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

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

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

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

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