二叉树——根据遍历结果,画出对应的二叉树 转载至:http://canlynet.blog.163.com/blog/static/255013652009112602449178/

这道题目很经典,具体如下:

已知遍历结果如下,试画出对应的二叉树:

前序:A B C E H F I J D G K

中序:A H E C I F J B D K G

解题要点:

1、前序、中序、后序——都针对中间那个节点而言(根节点也是中间的节点)。

前序,指先遍历中间节点,然后左,然后右。

中序,指左——中——右。

后序,指右——中——左。

2、根据两种不同序列的遍历方法,便可画出二叉树。

解题答案如下:(对照着看会好理解这道题目一些的)

 

解题思路:

1、前序中序都首先找出A,推断出:A没有左孩子(否则中序要先遍历其左孩子)。A为根节点(前序先遍历中节点)。

2、A没有左孩子,一定就只有右孩子了(否则哪来那么多后面的字符)。右孩子一定是B,根据前序结果(前序先遍历中节点)。

3、中序的第二个不是B,说明B一定有左孩子(中序先遍历左孩子)。既然有左孩子,那么在前序的B后面那位一定是啦——C,C有左孩子吗?一定有,否则中序的A后面就跟C啦。那么前序的C后面的E一定是C的左孩子(还是深入讲一下:前序是先遍历左,但左还有左的时候,得先遍历左的左,一直深入下去,找到最终的那个左节点,这个一定要明白,否则此题无法解开)。

4、同理:E也有左孩子,就是前序的E后面那位:H!好,既然中序的A后面是H,H一定没有左孩子啦。

5、下面怎么办呢?前序:H后面是F,中序:H后面的E、C已经确定了位置了,再后面是I,怎么办?

6、注意:中序H后面是E,说明H没有右孩子啊!(中序遍历方法!!)同理,E后面是C说明E也没有右孩子,C后面呢,是B吗?如果是,那么C也没有,惊喜了吧,中序当中C后面是I,说明C有右孩子,是谁呢?

7、既然C后面有右孩子,那么在前序中H后面的F一定就是我们要找的右孩子啦(因为前序是找中节点,然后找左孩子,左孩子中又先找中间节点,再找左孩子的左孩子……中——左——右,嵌套思想)。

8、F确定好位置后,那么考虑F有左孩子吗?如果没有,中序的C后面应该跟F,但是中序的C后面跟I,说明F有左节点,那么前序找完F一定要找到这个左节点了,就是说前序的F后面的I一定是F的左节点。

9、I有左孩子吗?中序的C后面跟的是I,说明I就是最终的左孩子了。

10、F有右孩子吗?如果没有,中序I的下一位应该是B,可是并非,所以它有右孩子,那么前序的I后面的J一定是这个右孩子。

11、J有左孩子吗?如果有,中序的F后面不能是J,可是并非如此,所以没有了。J有右孩子吗?如果有,中序的已经找过J啦,下一位就是找右孩子,所以看中序的J后面那一位,发现是B,B不是已经确定好位置了吗,所以啊,没有啦。回到B节点了。

12、前序的J后面的D一定就是B的右孩子(因为回到B了嘛,前序要先把B的右孩子当中节点找到,再去找右孩子的左孩子,再把左孩子当中节点找到……嵌套啊)。

13、D有左孩子吗?如果有,中序的B后面就不可能是D(因为中序要先找到最最最最最左边的那个啊)。所以没有。既然没有,那么前序就要找D的右孩子啦,那就是前序的D后面那个G。

14、G有左孩子吗?如果没有的话,中序的D后面一定是G啦,可是不是,所以它有左孩子,这个左孩子就是前序在找到G后面该找到的那位了,就是K。

OK,二叉树的图画出来了。

总结二叉树查找关键点:

1、每次都要假设,假设了立即推翻,如果假设有,发现不能成立的话,就推翻了这个假设,即确定了一个节点的存在与否。

2、一定要明白前序、中序、后序的遍历方法,要透彻的领悟到嵌套的思想,比如找左孩子,结果找到的左孩子还有左孩子,那么要先找左孩子的左孩子,如果左孩子的左孩子还有左孩子,那么……以此类推。

3、假设一定就一次,便可深入,否则就带有一定的猜测,然后证实的成分了,容易晕掉。

4、每次确定好一个位置都是100%确定的,所以画出来,不要犹豫,然后在前序、中序上做相应标记,知道自己下一个该确定那个字符的位置了。

5、解这个题目,一定不能着急,心要稳,别深入,没有更好的深入的方法(我没找到而已,哈哈)。每次找到一个节点就直接问,他有左孩子吗?如果有,那么在中序的查找中一定就该找他了,结果发现不是,所以推翻。如果没有,那么在前序一定就该找到这个节点了。方法就这一个而已,可以解开题目。

6、这个方法对后序查找也生效。

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。