根据先序和中序序列生成二叉树

~ 在二叉树中，有三种主要的遍历方式（假设父节点为N，左孩子为L，右孩子为R）：

先序遍历：N -> L -> R

中序遍历：L -> N -> R

后序遍历：L -> R -> N

假设现有一颗二叉树如上图所示，上述二叉树的先序遍历和中序遍历结果为：

先序遍历：ABCDEF

中序遍历：CBDAEF

分析： 先序遍历服从规则“根左右”，所以，对于一个先序遍历得到的数组，第一个元素一定是根节点；中序遍历服从规则”左根右“，所以由此可知，对于一个中序遍历得到的数组，根节点左边的元素都属于根节点的左子树，而根节点右边的元素都属于根节点的右子树。所以，可以先通过先序遍历的第一个元素确定根节点，然后通过中序遍历结合根节点，获得当前根节点的左右子树，再将子树看成一棵独立的树，继续使用先序遍历判断根节点，中序遍历判断子树的方式，最终建立起整棵树 。

详细算法如下：

1、先序或中序为空则返回，否则，通过先序序列创建根结点，再通过根节点在中序遍历的位置找出左右子树。

2、在根绝点的左子树中，找左子树的根结点（在先序中找），转步骤1。

3、在根节点的右子树中，找右子树的根结点（在先序中找），转步骤1。

根据上述算法，可以看出创建出二叉树的关键在于先序序列和中序序列的划分，在对序列进行划分的时候要注意边界的问题。

递归方式

非递归方式

---

石拐区13423986491： 请问根据输入的二叉树前序和中序序列如何来构造二叉树?谢谢! - ？
驹汤戴芬： 前序的第一个字母为树的根节点,然后查看中序序列中这个字母的位置,它之前的为左子树,之后的为右子树,然后分别对这两个子树的前序和中序序列做同样的步骤即可.

石拐区13423986491： 如何根据前序遍历序列和中序遍历序列确定二叉树 - ？
驹汤戴芬：[答案] 假设某二叉树的先序遍历序列是abdgcefh,中序遍历序列是dgbaechf,画出二叉树,并给出其后序遍历序列.以下面的例题为例进行讲已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf,求二叉树及后序遍历...

石拐区13423986491： 怎么由先序和中序来找二叉树 - ？
驹汤戴芬： 遍历顺序中,先序是中左右,中序是左中右,所以方法就是通过先序找到根节点(根节点必然存在,且必为子树遍历的第一个节点),然后通过中序里面相应根节点的位置来区分左右子树,左边为其左子树,右边必为其右子树.例如A是根,那么中序看,左子树是DFEGB,右子树是CIKJH,之后就利用递归的思路,单拿出左子树来分析;DFEGB在先序中B打头所以B是根节点,那么从中序可知,这个树只有左子树DFEG;D为根,只有右子树FEG;E为根,左叶子是F,右叶子是G.再看CIKJH,由先序知C为根,由中序知只有右子树IKJH,再观察先序H为根,中序则只有左子树IKJ,这个树的根为I,只有右子树KJ,J为根,K为它的左叶子,全部分析完毕.

石拐区13423986491： 先序法建立一棵二叉树 - ？
驹汤戴芬： 代码如下 最好要把它弄懂 否则就没意义了 加油!#include <iostream> using namespace std; struct tree { int data; tree *lchild,*rchild; }; class Ttree { private: tree *root; tree *creat(tree *bt); public: Ttree(){root=creat(root);} int depth(tree *root); int depth...

石拐区13423986491： 怎么用中序和后续生成二叉树?我只会用前序 - ？
驹汤戴芬： 已知一棵二叉树的后序序列和中序序列,构造该二叉树的过程如下: 1. 根据后序序列的最后一个元素建立根结点; 2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列; 3. 在后序序列中确定左右子树的后序序列; 4. 由左子树的后序...

石拐区13423986491： 已知二叉树的前序和中序,构造该二叉树的方法是什么 - ？
驹汤戴芬： 以下面的例题为例进行讲解: 已知一棵二叉树的先序遍历序列和中序遍历序列分别是ABDCEF、BDAECF,求二叉树及后序遍历序列. 分析:先序遍历序列的第一个字符为根结点.对于中序遍历,根结点在中序遍历序列的中间,左边部分是根...

石拐区13423986491： 先序中序建立二叉树？
驹汤戴芬： #include<stdio.h> #include<stdlib.h> #define size 100 typedef struct node//定义结点 { char data; struct node *lchild,*rchild; } JD,*BitTree; int search(char ino[],char pre)//在中序序列中查找先序中该元素所在位置 { int i=0; while(ino[i]!=pre&&ino[i]) i++; ...

石拐区13423986491： 关于二叉树的问题(怎么根据先序和中序遍历的结果建立二叉树?) - ？
驹汤戴芬： #include #includetypedef char TElemType;//Status是函数的类型,其值是函数结果状态码 typedef int status;//函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define ...

石拐区13423986491： 先序构建二叉树 - ？
驹汤戴芬： 传值调用啊.void CreatePre(BitTree T),不会修改T的值,void main()里将&T传递进去不会改变BitNode T在内存中位置,只是改变了复制进去的指针((CreatePre局部变量)BitTree T=&(main局部变量)T)的值;递归CreatePre(T->lchild);...

石拐区13423986491： 知道二叉树先序,中序,后序其中的两个顺序列,如何画出二叉树 - ？
驹汤戴芬： (1)由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树. (2)由先序遍历序列和中序遍历序列能够唯一确定一棵二叉树.设先序序列为:a1,a2,……,an , 中序序列为:ap1,…,api, a1, …,apn .则a1为根结点;ap1,…,api为左子树的中序序...