我是新手,问一下一颗二叉树,其中序遍历为:DCBGEAHFIJK,后序序列为:DCEGBFHKJIA.求画出该树?谢啦。

2024-11-15 22:19:34
推荐回答(2个)
回答(1):

解题思路:

因为后序遍历最后一个字母一定是根节点(A),在中序遍历中从A点处分成左右子树,即(DCBGE)和(HFIJK),同样的道理,在后序遍历中倒数第二个字母是I,则I是右子树的根节点,然后把右子树在分成左右子树(HF)和(JK),后序遍历中倒数第三个是J,说明J是根节点……以此类推!!

回答(2):

A
/ \
B I
/ \ / \
C G H J
/ / \ \
D E F K

(先序)先根遍历:(根左右)先访问根,再访问左子树,最后访问右子树,
(中序)中根遍历:(左根右)先访问左子树,再访问根,最后访问右子树,
(后序)后根遍历:(左右根)先访问左子树,再访问右子树,最后访问根,