已知一棵二叉树序列口诀的中序遍历序列；后序遍历序列。请画出这棵二叉树序列口诀，并将其转换为森林？

来源：蜘蛛抓取(WebSpider) 时间：2023-12-11 00:52 标签： 二叉树序列口诀
根据后序和中序遍历序列求二叉树前文：两道例题让你彻底学会如何根据遍历序列求二叉树中序：左、根、右后序：左、右、根直接上题：中序：DCBGEAHFIJK后序：DCEGBFHKJIA第一步：还是先找到老父亲节点后序的最后一个节点：A第二步：划分大哥和二弟的家族在中序中，老父亲节点左边的为大哥家族，右边的为二弟家族第三步：完善细节、总结经验我们先看左边的节点，还是那样，找在两个序列中都挨在一起的几个节点：1.D、C2.E、G3.B、G1.先看第一个：D和C,D在先序中是第一个访问的，所以他在整个树中是最左边的那个点，他俩在中序和后序中都是同样的顺序：说明他俩一个为父亲，一个为左节点，至于为啥不是同一个父亲的两个孩子，这个想想就知道了，如果他俩有共同的父亲，那么在中序中，访问完左孩子后就应该访问父亲，但是没有。2.再看E、G：在中序和后序中，这两个的出现顺序是相反的，那么他俩一定是父亲和右孩子,谁是父亲很好判断，在中序中，谁先出来谁是父亲3.继续看B、G，和2相同，顺序相反,这就可以把B连上去了我们在来看一下顺序，在中序中的顺序是BGE，后序中是EGB，连接方式就是一条右直线。可以得到结论：如果在中序和后序中多个点是在一起出现的，且顺序相反，那么他们能连成一条右直线大致的连接方式都画出来了，剩下的就是把他们拼在一起CD两个点可以确定是在最左边，接下来有两种连法，我们先试一下，再来找规律：一：B为C的右孩子二：C为B的左孩子先看一这种连接方式，满足中序的DCBGE，后序呢？DEGBC和题目不符，舍去那么只有二了，二的连接方式是完全符合题目的。。总结一下：如果两个点在中序和后序种同时出现（中间没有任何其他点）,那么，作为父亲的节点只有一个孩子间--------------------隔---------------------------线左边的完成了，接下来画右边的同样的方法：找到在两个序列中连着出现的点1.I、J、K2.H、F1很容易，中序中和后序中三个点的出现顺序完全相反：瞬间画出结果，而且还能确定很重要的一点：J只有K一个孩子根据中序中，K是最后访问到的，所以K位于该二叉树的最右端，在后序中，I是倒数第二个访问的，所以I的老父亲A的右孩子2.HF在两个序列中出现顺序相反：也是直接画出结果接下来就是把这两个连起来之前得到的结论，J只有K一个孩子，而K是整个树中最右边的节点，所以只能这么连：这样一个二叉树就画完了，最后在根据二叉树写一下他的中序和后序序列验证一下结果。我比较有自尊，坚信自己是对的，就不验证了。

我要回帖

更多关于 二叉树序列口诀 的文章

 

随机推荐