全部问题 > 当前问题

判断根节点

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

谢金欣 2016-7-18 08:50:30

共 3 个回答

最佳答案

旺仔小馒头 2016-7-18 16:32:37

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

blob.png

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

 


谢金欣 2016-7-19 08:35:34

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

旺仔小馒头 2016-7-19 11:45:34

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

问题来自: 二叉树的遍历