已知二叉树先序和中序,求后序遍历_n个结点的二叉树有几种形态

已知二叉树先序和中序,求后序遍历_n个结点的二叉树有几种形态一棵二叉树的先序遍历序列为EFHIGJK,中序遍历序列为HFIEJKG,则该二叉树根结点的右孩子为A.HB.EC.FD.G_已知二叉树的先序和中序序列如下所示,试构造出相应的二叉树

做下列例题之前请先转到:【教程】了解原理和方法。然后再做下面的例题。

【例题1】一棵二叉树的先序遍历序列为EFHIGJK,中序遍历序列为HFIEJKG,则该二叉树根结点的右孩子为()
A. H
B. E
C. F
D. G

【答案】D

解析:
思路:题目给出了先序序列和中序序列求根结点的右孩子。可以通过利用先序序列和中序序列构造出二叉树,然后根结点的右孩子就一目了然了。
详细过程如下:
step1:先序序列为:EFHIGJK,中序序列为:HFIEJKG
通过这两个序列可以得出:E是根结点,HFI是E结点的左子树,JKG是E结点的右子树。
如下图:
在这里插入图片描述
step2:先看E结点的左子树HFI
该左子树HFI的先序序列为:FHI,中序序列为:HFI
通过这两个序列可以得出:F是根结点,H是F结点的左子树,I是F结点的右子树。
如下图:
在这里插入图片描述
step3:再看E结点的右子树JKG
该右子树JKG的先序序列为:GJK,中序序列为:JKG
通过这两个序列可以得出:G是根结点,JK是G结点的左子树,G结点的右子树为空
如下图:在这里插入图片描述
step4:下面再看G结点的左子树JK,将它分解。
该左子树JK的先序序列为:JK,中序序列为:JK
通过这两个序列可以得出:J是根结点,K是J结点的子树,J结点的子树为空。
如下图:
在这里插入图片描述

至此二叉树构造成功,综上:该二叉树根结点的右孩子为:G。
说明:
其实从一开始,我们只需要先分析E结点的右子树,即可很快得到答案,或者说在step3的时候我们就能够得到正确答案了,只是,在我看来答案确实很重要,但做笔记嘛,还是希望有始有终。(强迫心理)
可能想到的问题:对于E结点的左子树和右子树是怎么得出他们的先序序列和中序序列的,以及后面的各个结点的子树是怎么得到他们的先序序列和中序序列的,还有如何通过先序序列和中序序列就能判断出根结点和左右子树?这些问题,页面上方的超链接,转到的文章应该能解答。为了节约时间,就不每篇文章都赘述了。

【例题2】已知一棵二叉树的先序序列与中序序列分别如下,试画出此二叉树。
先序序列: ABCDEFGHIJ
中序序列:CBEDAGHFJI

【答案】
在这里插入图片描述

详细过程:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

今天的文章已知二叉树先序和中序,求后序遍历_n个结点的二叉树有几种形态分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/63788.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注