已知二叉树的先序序列为ABCDEFGHIJ,中序遍历为CBEDAGHFJI,前构造(画出)该二叉树?快!
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/06 16:57:24
![已知二叉树的先序序列为ABCDEFGHIJ,中序遍历为CBEDAGHFJI,前构造(画出)该二叉树?快!](/uploads/image/z/8711159-23-9.jpg?t=%E5%B7%B2%E7%9F%A5%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%85%88%E5%BA%8F%E5%BA%8F%E5%88%97%E4%B8%BAABCDEFGHIJ%2C%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%E4%B8%BACBEDAGHFJI%2C%E5%89%8D%E6%9E%84%E9%80%A0%EF%BC%88%E7%94%BB%E5%87%BA%EF%BC%89%E8%AF%A5%E4%BA%8C%E5%8F%89%E6%A0%91%3F%E5%BF%AB%21)
已知二叉树的先序序列为ABCDEFGHIJ,中序遍历为CBEDAGHFJI,前构造(画出)该二叉树?快!
已知二叉树的先序序列为ABCDEFGHIJ,中序遍历为CBEDAGHFJI,前构造(画出)该二叉树?快!
已知二叉树的先序序列为ABCDEFGHIJ,中序遍历为CBEDAGHFJI,前构造(画出)该二叉树?快!
用递归思想来做:
首先先根遍历的第一个节点“A”必定为当前的根节点,然后到中根遍历中找到该节点,“A”前面的“CBED”必定属于左子树,“A”后面的“GHFJI”必定属于右子树.
由于左子树的中根遍历长度为4,故到先根遍历中截取长度为4的遍历,即为左子树的先根遍历,这样就同时找到了左子树的这两种遍历,又可以如法炮制,构造左子树.
对于右子树,同样可以根据他的中根遍历长度截取其先根遍历.
这样就是,构造二叉树的全过程.