前序,中序,后序三种遍历的相互转化(思路+递归实现代码)【全】 |
您所在的位置:网站首页 › 表达式二叉树先序遍历 › 前序,中序,后序三种遍历的相互转化(思路+递归实现代码)【全】 |
在二叉树这种数据结构中,有三种遍历方式,分别是前序(也叫先序)遍历,中序遍历,和后序遍历。当然有的地方还会有按层遍历。 前序遍历:根->左->右 中序遍历:左->根->右 后序遍历:左->右->根 按层遍历:从第一层开始一直到最后一层,类似按着完全二叉树的编号一个一个输出先说上面前三种遍历的相互转换, 当已知前序遍历序列和中序遍历序列的时候,可以确定它的后序遍历序列。 当已知后序遍历序列和中序遍历序列的时候,可以确定它的前序遍历序列。 但是当已知前序遍历序列和后序遍历序列的时候,它的中序遍历序列不一定 就不唯一,也就是说已知前序和后序不一定能推出中序。 下面会详细讲解已知前序和中序或者已知后序和中序来求另一种序列的思路还代码。 1.已知后序和中序序列求前序序列。举个栗子,比如说后序序列是3,4,2,6,5,1(左右根)中序序列是3,2,4,1,6,5(左根右) 思路:后序序列的最后一个数字(1)必定为整棵二叉树的根节点,然后在中序序列中找到1的位置可以确定这个根节点的左右子树分别是多少,(此时1的左子树为3 2 4 ,右子数为6 5)然后将3 2 4这颗树在后序序列中寻找可以找到它的左子树的根节点为2,6 5 这颗右子树的根为5以此类推,可以找到所有点。最后得到前序序列:1 2 3 4 5 6 ; 代码如下: #include using namespace std; int post[]={3,4,2,6,5,1}; int in[]={3,2,4,1,6,5}; void pre(int root,int start,int end) { if(start>end) return ; //退出条件,这棵树的范围为0 int i=start; while(iends) return; int i=start; while(i |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |