文章内容
一、根据前序遍历和中序遍历确定二叉树
前序(根节点-左节点-右节点):A B D E H C F G
中序(左节点-根节点-右节点):D B E H A F C G
1、第一步:根据前序确定祖宗节点
根据前序就可以判断遍历的第一个就是祖宗节点,为A ,然后我们就可以把中序遍历以A节点分开。
2、第二步:确定左子树的根节点
再看前序A的后一个节点,为B,根据前序的性质为左子树的根节点,所以我们把中序遍历的B再次像之前那样截取出来。
3、第三步:确定左子树的右边节点
由以上图可知,可以知道D就是左边的节点了
4、第四步:确定左子树的右边节点
ABD根据前序全部遍历完毕。再次依据上述方法构造左子树。在前序遍历和中序遍历H都在E的右边,为E的右节点。
5、第五步:确定右子树
根据前序下一个字母为C,那么右子树的根节点就为C,然后再根据中序排序找出字母割分左右。
全部步骤都已完成
二、根据后序遍历和中序遍历确定二叉树
中序(左节点-根节点-右节点):D B E H A F C G
后序(左节点-右节点-根节点):D H E B F G C A
1、第一步:根据后序确定祖宗节点
根据后序的性质,最后一个为祖宗节点,为A。然后我们割分中序的左右子树。
2、第二步:同时割分左右子树
根据上面的区分我们同时割分后序,把左右子树的节点区分出来。
3、第三步:确定左右子树根节点
由第二步可知,C和B为右子树和左子树的根节点,区分FG和DHE。画出中序的B和C节点,可以判断这两个节点左右节点各为多少。
4、第四步:确定左右子树所有子节点
只有EH的判断了,根据中序排序(左节点-根节点-右节点)的规律,为以防万一,再加上后序排序(左节点-右节点-根节点)的规律。先以后序来看,E是根节点,那么H因为排在E的前面就不太清楚是E的左还是右节点,再来看中序,中序的H排在E的后面,就可以判定H是E的右节点,这是因为中序是左节点-根节点-右节点,如果H是E的左节点那必然排在E的前面,中序先遍历左节点。