用先序遍历输入二叉树的先序遍历,然后恢复二叉树的先序遍历,得到它的中序遍历和后序遍历

从键盘输入先序序列以二叉链表作为存储结构,建立二叉树的先序遍历(以先序来建立)并对其进行遍历(先序中序,后序)然后将遍历结果打印输出。要求采用遞归或非递归两种方法实现

  • 这两个都是二叉树的先序遍历的,楼主可以看看!

ORACLE_DBA教程 清华大学出版社 《ORACLE数据库系統基础》俞盘祥 《数据库管理及应用开发》沈佩娟 汤荷美电子工业出版社 《ORACLE数据库管理员教程》 孙宏昌 金 毳

已知二叉树的先序遍历的前序/后序遍历和中序遍历求后序/前序遍历

首先,我们看看前序、中序、后序遍历的特性:

好了先说说用前序遍历和中序遍历求后序遍历

前序遍历是先访问根节点,然后再访问子树的而中序遍历则先访问左子树再访问根节点

那么把前序的 a 取出来,然后查找 a 在中序遍历中的位置僦得到 dgb a echf

那么我们就知道 dgb 是左子树 echf 是右子树因为数量要吻合

所以前序中相应的 dbg 是左子树 cefh 是右子树

然后就变成了一个递归的过程,具体代码洳下:


 
 //根节点是第一个元素
 
 
 
 //变成后序遍历要最后输出节点的值

而已知后序遍历和中序遍历求前序遍历的过程差不多但由于后序遍历是最後才访问根节点的

所以要从后开始搜索,例如上面的例子后序遍历为 gbdehfca,中序遍历为 dgbaechf

后序遍历中的最后一个元素是根节点a,然后查找中序中a的位置

把中序遍历分成 dgb a echf而因为节点个数要对应

后序遍历分为 gbd ehfc a,gbd为左子树ehfc为右子树,这样又可以递归计算了

其他一些附带的代码上媔已经有这里就不重复贴了,具体代码如下:


 
 
 //根节点是最后一个元素
 
 //变成前序遍历要先输出节点的值
 
 

我要回帖

更多关于 二叉树的先序遍历 的文章

 

随机推荐