判断根节点
谢金欣 正式会员 2016-07-18 08:50:30
8836 3 0

老师,什么时候根据中序序列判断根节点,什么时候根据前序序列判断根节点,什么时候根据后序序列判断根节点啊?谢谢

问题来自: 二叉树的遍历

共 3 个回答

    最佳答案

    旺仔小馒头 资深会员 2836天前

    二叉树题目要具体题目具体面对,具体口诀我给你想想怎么说能简单一些。在这之前我先给你拿这道题举例一下二叉树的常规解法。

    blob.png

    这种题先根据条件画树。先找到当前树的根节点,然后确定为左子树,右子树,然后针对左子树进行上述细化操作,然后针对右子树进行上述细化操作。最后根据得出的条件画树。解题时要注意,在前序遍历中,是把所有左子树节点遍历完之后再遍历右子树,而且遍历的左子树的第一个节点就是左子树的根节点。同样的,遍历的右子树的第一个节点就是右子树的根节点。就拿这道题来说。首先,题目根节点在一层,再根据根据前序序列为ABCDEFG,所以根节点为A。又因为中序序列为DCBAEFG,所以最左边节点为D,后序遍历最后一个节点是A,则后序遍历结果为DCBGFEA。然后,因为中序遍历DCBAEFG,所以节点A左侧的ABCD必然是的左子树,A右侧的EFG必然是的右子树。接着,分析左子树ABCD,左子树的中的根节点必然是总树的左节点。在前序遍历中,大树的左节点必然位于根节点之后,所以左子树的根节点为B。同样的道理,右子树EFG中的根节点也可以通过前序遍历求得。这就画出图了吧? A B E C FD G

     


    谢金欣 正式会员 2835天前

    回复 旺仔小馒头:老师,要是没有前序遍历,只有中序和后序该咋办啊?

    旺仔小馒头 资深会员 2835天前

    这个需要具体题目具体对待,不好一概而论的,你有具体的题目吗?

您还没有登录,所以不能回复该问题
我要回复

  • 0

    点赞

  • 扫一扫分享朋友圈

    二维码

  • 分享

相关问题