二叉树后序遍历为EHGCBJFIAD,中序遍历为EHDGCAJBIF,则先序为
1个回答
关注
![]()
展开全部
亲，您好
，很高兴回答你的问题 二叉树后序遍历为EHGCBJFIAD,中序遍历为EHDGCAJBIF,则先序为
，很高兴回答你的问题 二叉树后序遍历为EHGCBJFIAD,中序遍历为EHDGCAJBIF,则先序为
（1）先序遍历：先访问根节点然后是左孩子节点最后是右孩子节点即为：根->左->右
（2）中序遍历：先访问左孩子节点然后是根节点最后是右孩子节点即为：左->根->右
（3）后序遍历：先访问左孩子节点然后是右孩子节点最后是根节点即为：左->右->根
对于每一个节点都是上面所述的顺序遍历（指的是根，左孩子，右孩子的访问顺序）
下面是求先序中序后序遍历的样例：
根据上图先序遍历的结果是：先看A（根节点）{A}然后A的左边，左边第一个根节点是B把B加入到结果中{A B}，然后是B的左孩子D{A B D}B没有右孩子不用考虑，接着是D的左孩子G加入到结果中去{A B D G},左边遍历完毕考虑右边第一个右边节点是C（因为C为A的右孩子所以在考虑完A的左孩子之后自然该右孩子）{A B D G C}，接着考虑C的左孩子E{A B D G C E}该考虑E了但是E没有孩子所以考虑C的右孩子F{A B D G C E F}遍历完成！
中序遍历和先序遍历几乎一样只不过先考虑左孩子然后是根节点最后是右孩子，所以模拟一遍之后的结果应该是{G D B A E C F}
后序遍历为{G D B E F C A}
下面来介绍如何根据已知的两种遍历结果如何来写另一种遍历的结果和还原树的形态；
例如一种树的中序遍历结果为：D E B A C;后序遍历结果为：D A B E C;
求先序遍历结果：
首先后序遍历的最后一个元素肯定是根节点所以根节点为C然后来到中序遍历的结果里面查找C所处的位置看完后会发现他只有左孩子（所有元素均在左边）之后回到后序遍历里面下一个根节点就是紧挨着C的那一个所以E就是C的左孩子接下来继续回看中序遍历查看E所处的位置结果发现它的左边是D无疑D就是它的左孩子右边有两个B和A这时候需要回到后序遍历发现紧挨着的是B所以B是E的右孩子（因为右孩子之后就是根节点所以B一定是E的右孩子）最后A就是B右孩子（这一个是在中序里面看出来的B的左边没有A是在B的右边的）
所以先序遍历结果是{C E D B A}
树的形状建好之后就会是：
总结：在已知两种遍历顺序求另一种的时候肯定会有一个中序遍历的顺序是已经知道的因为要查看一个节点的左孩子和右孩子分别是什么；
还有一点就是先序
咨询记录 · 回答于2022-06-19
二叉树后序遍历为EHGCBJFIAD,中序遍历为EHDGCAJBIF,则先序为
亲，您好，很高兴回答你的问题 二叉树后序遍历为EHGCBJFIAD,中序遍历为EHDGCAJBIF,则先序为（1）先序遍历：先访问根节点然后是左孩子节点最后是右孩子节点即为：根->左->右（2）中序遍历：先访问左孩子节点然后是根节点最后是右孩子节点即为：左->根->右（3）后序遍历：先访问左孩子节点然后是右孩子节点最后是根节点即为：左->右->根对于每一个节点都是上面所述的顺序遍历（指的是根，左孩子，右孩子的访问顺序）下面是求先序中序后序遍历的样例：根据上图先序遍历的结果是：先看A（根节点）{A}然后A的左边，左边第一个根节点是B把B加入到结果中{A B}，然后是B的左孩子D{A B D}B没有右孩子不用考虑，接着是D的左孩子G加入到结果中去{A B D G},左边遍历完毕考虑右边第一个右边节点是C（因为C为A的右孩子所以在考虑完A的左孩子之后自然该右孩子）{A B D G C}，接着考虑C的左孩子E{A B D G C E}该考虑E了但是E没有孩子所以考虑C的右孩子F{A B D G C E F}遍历完成！中序遍历和先序遍历几乎一样只不过先考虑左孩子然后是根节点最后是右孩子，所以模拟一遍之后的结果应该是{G D B A E C F}后序遍历为{G D B E F C A}下面来介绍如何根据已知的两种遍历结果如何来写另一种遍历的结果和还原树的形态；例如一种树的中序遍历结果为：D E B A C;后序遍历结果为：D A B E C;求先序遍历结果：首先后序遍历的最后一个元素肯定是根节点所以根节点为C然后来到中序遍历的结果里面查找C所处的位置看完后会发现他只有左孩子（所有元素均在左边）之后回到后序遍历里面下一个根节点就是紧挨着C的那一个所以E就是C的左孩子接下来继续回看中序遍历查看E所处的位置结果发现它的左边是D无疑D就是它的左孩子右边有两个B和A这时候需要回到后序遍历发现紧挨着的是B所以B是E的右孩子（因为右孩子之后就是根节点所以B一定是E的右孩子）最后A就是B右孩子（这一个是在中序里面看出来的B的左边没有A是在B的右边的）所以先序遍历结果是{C E D B A}树的形状建好之后就会是：总结：在已知两种遍历顺序求另一种的时候肯定会有一个中序遍历的顺序是已经知道的因为要查看一个节点的左孩子和右孩子分别是什么；还有一点就是先序
，很高兴回答你的问题 二叉树后序遍历为EHGCBJFIAD,中序遍历为EHDGCAJBIF,则先序为（1）先序遍历：先访问根节点然后是左孩子节点最后是右孩子节点即为：根->左->右（2）中序遍历：先访问左孩子节点然后是根节点最后是右孩子节点即为：左->根->右（3）后序遍历：先访问左孩子节点然后是右孩子节点最后是根节点即为：左->右->根对于每一个节点都是上面所述的顺序遍历（指的是根，左孩子，右孩子的访问顺序）下面是求先序中序后序遍历的样例：根据上图先序遍历的结果是：先看A（根节点）{A}然后A的左边，左边第一个根节点是B把B加入到结果中{A B}，然后是B的左孩子D{A B D}B没有右孩子不用考虑，接着是D的左孩子G加入到结果中去{A B D G},左边遍历完毕考虑右边第一个右边节点是C（因为C为A的右孩子所以在考虑完A的左孩子之后自然该右孩子）{A B D G C}，接着考虑C的左孩子E{A B D G C E}该考虑E了但是E没有孩子所以考虑C的右孩子F{A B D G C E F}遍历完成！中序遍历和先序遍历几乎一样只不过先考虑左孩子然后是根节点最后是右孩子，所以模拟一遍之后的结果应该是{G D B A E C F}后序遍历为{G D B E F C A}下面来介绍如何根据已知的两种遍历结果如何来写另一种遍历的结果和还原树的形态；例如一种树的中序遍历结果为：D E B A C;后序遍历结果为：D A B E C;求先序遍历结果：首先后序遍历的最后一个元素肯定是根节点所以根节点为C然后来到中序遍历的结果里面查找C所处的位置看完后会发现他只有左孩子（所有元素均在左边）之后回到后序遍历里面下一个根节点就是紧挨着C的那一个所以E就是C的左孩子接下来继续回看中序遍历查看E所处的位置结果发现它的左边是D无疑D就是它的左孩子右边有两个B和A这时候需要回到后序遍历发现紧挨着的是B所以B是E的右孩子（因为右孩子之后就是根节点所以B一定是E的右孩子）最后A就是B右孩子（这一个是在中序里面看出来的B的左边没有A是在B的右边的）所以先序遍历结果是{C E D B A}树的形状建好之后就会是：总结：在已知两种遍历顺序求另一种的时候肯定会有一个中序遍历的顺序是已经知道的因为要查看一个节点的左孩子和右孩子分别是什么；还有一点就是先序
你好亲，
如果我的解答对您有所帮助，还请给个赞(在左下角进行评价哦)，期待您的赞，您的举手之劳对我很重要,您的支持也是我进步的动力。如果觉得我的解答还满意,可以点我头像一对一咨询。最后再次祝您身体健康,心情愉快!
如果我的解答对您有所帮助，还请给个赞(在左下角进行评价哦)，期待您的赞，您的举手之劳对我很重要,您的支持也是我进步的动力。如果觉得我的解答还满意,可以点我头像一对一咨询。最后再次祝您身体健康,心情愉快!
已赞过
评论
收起
你对这个回答的评价是？
