C语言数据机构：由中序遍历和层次遍历能不能唯一确定一颗二叉树？为什么说法不一致哪？

为什么由二叉树的中序和前序遍历序列可以唯一确定一棵二叉树，而由前序和后序遍历则不能？~

序、中序或由中序、后序遍历结果快速还原二叉树的方法。�
二叉树是最为常用的数据结构，它的实际应用非常广泛。二叉树的遍历方式有三种，前序遍历、中序遍历、后序遍历。先序遍历的顺序为：NLR，即先根结点，然后左子树、右子树；中序遍历顺序为：LNR先左子树，然后根结点、右子树；后序遍历顺序为：LRN先左子树、然后右子树、根结点。由前序和中序遍历、由中序和后序遍历序列可以唯一确定一棵二叉树，而由前序和后序遍历序列不能唯一确定一棵二叉树。�
二叉排序树对二叉树作了进一步的限定：根结点的权值大于（或小于）左子树中所有结点的权值；根结点的权值小于（或大于）其右子树中所有结点的权值。�
那么如何根据三种遍历序列之间的关系及二叉排序树来快速还原一棵二叉树？下面以二叉树的前序和中序遍历序列为基础，利用二叉排序树的性质，给出快速还原二叉树的方法。�
1由给定前序和中序序列或中序和后序序列还原二叉树的方法�
例：前序序列：ABDECFGH 中序序列：DEBACGFH （后序序列：EDBGHFCA）�
（1）给中序序列中的每个结点从小到大、从左到右赋以权值，如下：�
D（1）E（2）B（3）A（4）C（5）G（6）F（7）H（8）�
（2）还原时读入的序列为前序序列，从左到右依次读入序列中的各个结点值和相应的权值； �

（3）由读入的序列，根据第1）步中给定的权值按照二叉排序树的构造规则构造二叉排序树。第一个读入的结点为根结点，其他结点分别为左右子树中的结点。设根结点为TT，权值为NN，当前读入结点为SS，权值为MM，若MM
（4）将SS插入到TT的左子树或右子树的过程中，仍然遵循3）中的规则，直至左子树或右子树为空时止。�
（5）读入序列结束时，二叉树还原成功。�

6）对于由中序序列和后序序列还原二叉树是，读入的序列为后序序列，从右向左读入，构造规则同上。还原结果与上述结果完全一致。�

2还原方法的确定依据�
二叉树遍历过程中，在中序序列中，根结点的左子树中的所有结点都在根结点的左侧，根结点的右子树中的所有结点都在根结点的右侧，这个特点恰好与二叉排序树具有相同的性质；在读入序列时，前序序列则从左向右读，这恰好与遍历二叉树的顺序相同；后序序列从右向左读，则按照根结点、右子树、左子树的顺序还原。�
（1）设二叉树共有N个结点（N为大于1的正整数），我们按照还原方法给中序序列中的这N个结点分别赋予权值1,2…N，设根结点的权值为M（1
（2）由二叉树的遍历规则可知，权值为1,2…M-1的结点为根结点的左子树中的结点，而权值为M+1,…N的结点为根结点的右子树中的结点。�
（3）将这N个结点划分成3个子集AA＝（1,2…M-1）BB＝（M）CC＝（M+1,…N），由于前序序列第一个读入的结点必定为二叉根的根结点，所以BB为根结点，AA集为左子树，CC集为右子树。�
（4）同理不断读入前序序列中的结点，依次递归还原BB对应的左子树和CC对应的右子树，最后将三棵子树合并成以BB为根结点、AA的根结点为BB的左子树、CC的根结点为BB的右子树的一棵二叉排序树。�
（5）同理可以得出，由中序序列和后序序还原二叉树的规则也成立。�
（6）在还原过程中，读入序列的顺序也遵循也先根结点，后子树的规律。�
3总结�
在二叉树的一些应用中，如平衡二叉树、红黑树等，常常要观察二叉树的形态，对其进行判断并调整。根据遍历序列和二叉排序树的性质快速还原出二叉树对于研究相关的问题有很大的帮助。

前序和后序在本质上都是将父节点与子结点进行分离，但并没有指明左子树和右子树的能力，因此得到这两个序列只能明确父子关系，而不能确定一个二叉树。 由二叉树的中序和前序遍历序列可以唯一确定一棵二叉树 ，由前序和后序遍历则不能唯一确定一棵二叉树。由二叉树的中序和后序遍历序列可以唯一确定一棵二叉树，由前序和后序遍历则不能唯一确定一棵二叉树。
先序遍历，按照最优先顺序沿一定路径经过路径上所有的站。在二叉树中，先根后左再右。巧记：根左右。首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。
后序遍历是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根。首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。

由中序遍历和层次遍历能够唯一确定一颗二叉树。从下面的算法可知，每一步构造得到的二叉树结果是唯一的。
以下构造部分的答案来自百度知道：
假定树的层次遍历ABCDEFG HIJ中序遍历DBGEHJACIF
两种遍历顺序要结合着分析，才能画出这颗树的图

比如，层次遍历，先访问到A节点，说明A是树的根节点
那么在中序遍历结果里看：
DBGEHJ在A前面，说明这些节点，都在A左子树上
CIF在A的后面，说这些节点，都在A的右子树上
那么，树可以先这样画：
__________A________
________/____\_____
_____DBGEHJ__CIF___

再看层次遍历，A后面是B，说明B是A左子树的根节点
从上图中的先序遍历顺序DBGEHJ中看到：
D在B的前面，说明D在B的左子树上
GEHJ在B的后面，说明它们在B的右子树上
那么，树又可以画成：
_________A________
_______/____\_____
_____B________CIF__
____/__\____________
___D__GEHJ_________

如此循环，直到将整个树都画完全
结果如下：

_____________A_______________
___________/____\_____________
________B_________C__________
______/___\_________\_________
_____D_____E_________F_______
__________/__\_________\______
_________G____H_________I____
_______________\______________
_________________J____________

结论：唯一
例：
层次：ABC　构成二叉树（设B与C或为A的子树，或为A的结点）
A A A A A
/ / / \ \ \
B B B C B B
/ \ \ /
C C C C
对应的中序序列:
（1）CBA （2） BCA （3） BAC （4） ABC （5） ACB

证明：
　　由于层次遍历的第一个元素一定为根（A），所以，我们分别证明以上五种情况在层次遍历的约束下，一定只能构造一棵树。
　　(1)由于A为根，所以CB一定为A的子孙。根据层次序列BC的顺序BC或为兄弟，或为父子关系。i)如果BC为兄弟，则其中序顺序一定是B*C，因此与（1）矛盾；ii)如果BC为父子关系，则B一定为父，C一定为子。再根据中序的顺序CB可以确定C为B的左孩子，因此。CBA与ABC一定能唯一确定一棵二叉树，即第一棵二叉树。
（2）同理可以证明其它情况一定是唯一对应。

I是F的左子树

---

靖宇县18328074482： C语言数据机构:由中序遍历和层次遍历能不能唯一确定一颗二叉树?为什么说法不一致哪? - ？
习软必存： 由中序遍历和层次遍历能够唯一确定一颗二叉树.从下面的算法可知,每一步构造得到的二叉树结果是唯一的. 以下构造部分的答案来自: 假定树的层次遍历ABCDEFG HIJ中序遍历DBGEHJACIF 两种遍历顺序要结合着分析,才能画...

靖宇县18328074482： 由中序遍历和层次遍历还原二叉树.C语言实现 - ？
习软必存： #include#include#include#include#include typedef int data_t; typedef struct node { data_t data; struct node *lchild, *rchild; }btree; btree *create_btree(void); void preorder_btree(btree *bt); void inorder_btree(btree *bt); void postorder_btree(btree *bt); ...

靖宇县18328074482： C语言根据层次遍历和中序遍历求二叉树的前序遍历和后序遍历.下面有我的建树函数,有注释的. - ？
习软必存： #include＂cstdio＂#include＂vector＂#include＂cstring＂#include＂algorithm＂ using namespace std; const int maxn =30; struct node{ int data; node* lchild; node* rchild; }; int n; int in[maxn]; bool vis[maxn]={false}; vector lev; node* create(vector ...

靖宇县18328074482： c语言 关于二叉树的创建和遍历(中序遍历) - ？
习软必存： 这个还是我学《数据结构》时做的有关二叉树的练习呢,本来是全的,包括树的初始化,建立,遍历(中序、前序、后序和层次),还有输出,复制,删除节点,求深度,树的删除等等,看你只问了有关创建和中序遍历的,所以选了一部分给你...

靖宇县18328074482： c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法 - ？
习软必存： #include<malloc.h> // malloc()等 #include<stdio.h> // 标准输入输出头文件,包括EOF(=^Z或F6),NULL等 #include<stdlib.h> // atoi(),exit() #include<math.h> // 数学函数头文件,包括floor(),ceil(),abs()等#define ClearBiTree DestroyBiTree // 清空二...

靖宇县18328074482： C语言数据结构(二叉树的遍历) - ？
习软必存： 层次遍历应该没有递归算法 递归实际就是一种深度优先的算法 而层次遍历实际是广度优先的遍历算法,所以递归不适用 比如假设有递归算法,现遍历i层的开始,对i层第一个元素遍历后需调用递归函数遍历其孩子,递归调用完成后才继续遍历i层第二个元素,这样就不是层次遍历了

靖宇县18328074482： 用C语言编:构造一棵二叉树的二叉链表,并输出此二叉树的中序遍历序列和后序遍历序列.数据元素为字符型 - ？
习软必存： 先序创建一颗二叉树遍历;#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define OVERFLOW -2#define OK 1#define ERROR 0 typedef int status; typedef char TElemtype; typedef struct BiTNode{ TElemtype data; struct BiTNode *lchild,*...

靖宇县18328074482： C语言中,前序遍历,中序遍历各什么意思? - ？
习软必存： 前序遍历:先访问根节点,然后访问左子树,再访问右子树. 中序遍历:先访问左子树,然后访问根节点,再访问右子树.

靖宇县18328074482： 已知二叉树的先序遍历序列和中序遍历序列,求层次遍历 跪求大牛!(C语言) - ？
习软必存： typedef struct Tree_node{int data;struct Tree_node *lchild;struct Tree_node *rchild; }NODE,*LINK; //按层遍历 void LevelShow(LINK root) {LINK queue[N+1],p;int front=0,rear=0; //队列首尾指针if(root==NULL){printf(＂树不存在,请创建...

靖宇县18328074482： 用数据结构(C语言版)编一程序能实现先序、中序、后序遍历二叉树并能打印出运行结果. - ？
习软必存： #include <stdio.h> #include <stdlib.h> #define STACK_MAX_SIZE 30 #define QUEUE_MAX_SIZE 30 #ifndef elemType typedef char elemType; #endif /************************************************************************/ /* 以下是关于二叉树操作的11...