博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
C++中的树、二叉树、二叉树遍历、二叉树前序、中序、后序遍历相互求法
阅读量:6261 次
发布时间:2019-06-22

本文共 3829 字,大约阅读时间需要 12 分钟。

本博文来总结下树、二叉树以及二叉树前序、中序、后序遍历相互求法,即如果知道两个的遍历,如何求第三种遍历方法,比较笨的方法是画出来二叉树,然后根据各种遍历不同的特性来求,也可以编程求出,下面我们分别说明。

1、什么是树?什么是二叉树?

树是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合。

二叉树是指结点的度不超过2的有序树。

(结点的度:树中的一个结点拥有的子树数目。)

2、二叉树的前序、中序、后序遍历的特性 

二叉树前序遍历特性:

 

(1)、访问根节点 

(2)、前序遍历左子树 

(3)、前序遍历右子树 

二叉树中序遍历特性: 

(1)、中序遍历左子树 

(2)、访问根节点 

(3)、中序遍历右子树 

二叉树后序遍历特性:

 

(1)、后序遍历左子树 

(2)、后序遍历右子树 

(3)、访问根节点

3、已知前序、中序遍历,求后序遍历

例:

前序遍历:         GDAFEMHZ

中序遍历:         ADEFGHMZ

3.1、画树求法

第一步、根据前序遍历的特点,我们知道根结点为G

第二步、观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树,G右侧的HMZ必然是root的右子树。

 第三步、观察左子树ADEF,左子树的中的根节点必然是大树的root的leftchild。在前序遍历中,大树的root的leftchild位于root之后,所以左子树的根节点为D。

第四步、同样的道理,root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中,一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树,并且遍历的左子树的第一个节点就是左子树的根节点。同理,遍历的右子树的第一个节点就是右子树的根节点。

第五步、观察发现,上面的过程是递归的。先找到当前树的根节点,然后划分为左子树,右子树,然后进入左子树重复上面的过程,然后进入右子树重复上面的过程。最后就可以还原一棵树了。

该步递归的过程可以简洁表达如下:

1 、确定根,确定左子树,确定右子树。

2 、在左子树中递归。

3 、在右子树中递归。

4 、打印当前根。

那么,我们可以画出这个二叉树的形状:

那么,根据后序的遍历规则,我们可以知道,后序遍历顺序为:AEFDHZMG

3.2、编程求法

示例代码如下。

/***************************************************************************/				/*已知前序、中序遍历,求后序遍历*//***************************************************************************/#include 
#include
#include
using namespace std;struct TreeNode{ struct TreeNode* left; struct TreeNode* right; char elem;};void BinaryTreeFromOrderings(char* inorder, char* preorder, int length){ if(length == 0) { //cout<<"invalid length"; return; } TreeNode* node = new TreeNode;//Noice that [new] should be written out. node->elem = *preorder; int rootIndex = 0; for(;rootIndex < length; rootIndex++) { if(inorder[rootIndex] == *preorder) break; } //Left BinaryTreeFromOrderings(inorder, preorder +1, rootIndex); //Right BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1)); cout<
elem; return;} int main(int argc, char* argv[]){ printf("Question: 已知前序、中序遍历,求后序遍历\n\n"); char* pr="GDAFEMHZ";//前序 char* in="ADEFGHMZ";//中序 cout<<"前序是:"<
<

4、已知中序和后序遍历,求前序遍历

依然是上面的题,这次我们只给出中序和后序遍历:

中序遍历:       ADEFGHMZ

后序遍历:     AEFDHZMG

4.1、画树求法

第一步、根据后序遍历的特点,我们知道后序遍历最后一个结点即为根结点,即根结点为G。
第二步、观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树,G右侧的HMZ必然是root的右子树。
第三步、观察左子树ADEF,左子树的中的根节点必然是大树的root的leftchild。在前序遍历中,大树的root的leftchild位于root之后,所以左子树的根节点为D。
第四步、同样的道理,root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前后序遍历中,一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树,并且遍历的左子树的第一个节点就是左子树的根节点。同理,遍历的右子树的第一个节点就是右子树的根节点。
第五步、观察发现,上面的过程是递归的。先找到当前树的根节点,然后划分为左子树,右子树,然后进入左子树重复上面的过程,然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下:

1、 确定根,确定左子树,确定右子树。

2 、在左子树中递归。

3 、在右子树中递归。

4 、打印当前根。

这样,我们就可以画出二叉树的形状,如上图所示,这里就不再赘述。

那么,前序遍历:         GDAFEMHZ

4.2、编程求法

示例代码如下。

/***************************************************************************/				/*已知中序、后序遍历,求前序遍历*//***************************************************************************/#include 
#include
#include
using namespace std;struct TreeNode{ struct TreeNode* left; struct TreeNode* right; char elem;};TreeNode* BinaryTreeFromOrderings(char* inorder, char* aftorder, int length){ if(length == 0) { return NULL; } TreeNode* node = new TreeNode;//Noice that [new] should be written out. node->elem = *(aftorder+length-1); cout<
elem; int rootIndex = 0; for(;rootIndex < length; rootIndex++)//a variation of the loop { if(inorder[rootIndex] == *(aftorder+length-1)) break; } node->left = BinaryTreeFromOrderings(inorder, aftorder , rootIndex); node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, aftorder + rootIndex , length - (rootIndex + 1)); return node;}int main(int argc, char** argv){ printf("Question: 已知中序、后序遍历,求前序遍历\n\n"); char* in="ADEFGHMZ"; //中序 char* af="AEFDHZMG"; //后序 cout<<"中序是:"<
<

你可能感兴趣的文章
How to mount usb device in CentOS?
查看>>
机器学习中的贝叶斯方法---当后验分布无法计算时如何求得预测模型?
查看>>
Kali无法定位软件包的解决方案
查看>>
Webwork 学习之路【01】Webwork与 Struct 的前世今生
查看>>
串口调试问题 【转】
查看>>
利用客户端缓存对网站进行优化
查看>>
Elasticsearch之head插件安装之后的浏览详解
查看>>
zabbix监控-基本原理介绍
查看>>
循环神经网络(RNN)模型与前向反向传播算法
查看>>
使用bash编写Linux shell脚本--参数和子壳
查看>>
现代软件工程讲义 5 项目经理 Program Manager
查看>>
DotNet语音技术实现(实现电脑发音)
查看>>
Qt中用正則表達式来推断Text的语种,主要通过推断unicode的编码范围
查看>>
ASP.NET中 HyperLink(超链接)的使用
查看>>
Java异常
查看>>
[转载]全面深入了解电脑死机的原因
查看>>
html5-web本地存储
查看>>
CentOS 6.5 安装 Redis 执行 make #error &quot;Newer version of jemalloc required&quot;
查看>>
12.遍历二叉树与二叉树的建立
查看>>
Delphi 关键字详解[整理于 "橙子" 的帖子]
查看>>