已知二叉树的先序序列为ABCDEFGHIJ,中序遍历为CBEDAGHFJI,前构造(画出)该二叉树?快!!!!

2025-02-28 09:07:44
推荐回答(2个)
回答1:

用递归思想来做:
首先先根遍历的第一个节点“A”必定为当前的根节点,然后到中根遍历中找到该节点,“A”前面的“CBED”必定属于左子树,“A”后面的“GHFJI”必定属于右子树。
由于左子树的中根遍历长度为4,故到先根遍历中截取长度为4的遍历,即为左子树的先根遍历,这样就同时找到了左子树的这两种遍历,又可以如法炮制,构造左子树。
对于右子树,同样可以根据他的中根遍历长度截取其先根遍历。

这样就是,构造二叉树的全过程。

回答2:

我想它的后序序列应该是:CEDBHGIJFA
自己再想一下,我忘得差不多了