目录
举例一
1、画坐标系:
2、填表:
3、连线
举例二
1、画坐标系
2、填表
3、连线
原理
这是一个笔试技巧,对代码能力没有什么提高。
可以用,但是代码也要会写,那才是根基。
相对于传统方法,此方法非常的快,不管你到底有多少个节点!
三步走就能解题:
1、画坐标系
2、填结点
3、连结点
举例一
已知先序序列:ABCDEF
已知中序序列:CBAEDF
求这颗二叉树的后序遍历序列?
1、画一个直角坐标系图:
注意:
要按照箭头的方向填入!
一个格子放一个字母!
2、填结点:
注意:
填结点的时候,要向直角坐标系一样,xy轴的坐标要11对应
3、连线
注意:
在链接左子树或者右子树的时候,遵循就近原则!
优先与根结点高度最一致的连线
比如下图链接左树:
B结点是仅次于A结点的最高的结点,所以A结点的左子树就是B
如上图,就是标准答案了,不行你可以验证一下!
举例二
已知
后序:DABEC
中序:DEBAC
求这颗二叉树的前序遍历序列?
和例一的解法不说基本类似,一摸一样肯定是有的。
1、画坐标系
注意:
1.箭头方向一定要和我上面的保持一致!(讲原理的时候说)
2.注意中序遍历永远放到x轴
2、填表
注意事项和例一是一样的,不过多赘述。
3、连线
三步走玩,树C(树的根结点就是最高的结点)就是要求的了,不信,你也可以验证一下。
原理:
原理其是并不高深。
依靠的还是:
中序:左根右
前序:根左右
后序:左右根
只不过运用了图形化展示(以已知前序和中序,求后序为例):
这也是为什么,刚才我要强调箭头的方向的缘故了,如果前序调转成了后序,那么就不是原来的那棵树了。
关于这个方法,如果没有表格,也没有关系,只要坐标系每一个结点对应好就可以了,也不会花太长的时间。