给定一个中序遍历,所对应的二叉树是不是唯一的?
序、中序或由中序、后序遍历结果快速还原二叉树的方法。�
二叉树是最为常用的数据结构，它的实际应用非常广泛。二叉树的遍历方式有三种，前序遍历、中序遍历、后序遍历。先序遍历的顺序为：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总结�
在二叉树的一些应用中，如平衡二叉树、红黑树等，常常要观察二叉树的形态，对其进行判断并调整。根据遍历序列和二叉排序树的性质快速还原出二叉树对于研究相关的问题有很大的帮助。
树的后序遍历是指先依次后序遍历每棵子树，然后访问根结点。当树用二叉树表示法(也叫孩子兄弟表示法)存储时，可以找到唯一的一棵二叉树与之对应，我们称这棵二叉树为该树对应的二叉树。那么根据这个法则可知，树的后序遍历序列等同于该树对应的二叉树的中序遍历。
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上。
⑴访问结点本身（N），
⑵遍历该结点的左子树（L），
⑶遍历该结点的右子树（R）。
以上三种操作有六种执行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上。
扩展资料：
二叉树前序访问如下：
从根结点出发，则第一次到达结点A，故输出A;
继续向左访问，第一次访问结点B，故输出B；
按照同样规则，输出D，输出H；
当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I；
I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E；
向E左子树，故输出J；
按照同样的访问规则，继续输出C、F、G。
二叉树中序访问如下：
从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；
到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H；
H右子树为空，则返回至D，此时第二次到达D，故输出D；
由D返回至B，第二次到达B，故输出B；
按照同样规则继续访问，输出J、E、A、F、C、G。
参考资料来源：百度百科-二叉树
参考资料来源：百度百科-二叉树遍历
不是唯一的。
比如下面这两个二叉树
其中序遍历都是BAC。
什么是先、中、后根遍历?什么是左子树、右子树和二叉树?
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回，否则：（1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树 如右图所示二叉树，中根遍历结果：DBEAFC 3、后根遍历一般指后序遍历，指在访问根结点、遍历左子树与遍历右子树三者中，首先遍历左子树，然后遍历...
有一二叉树,中序遍历为DBAECF,前序遍历为ABDCEF,求后续遍历
我们看到前序遍历的结果为ABDCEF，可以知道根节点是A，再看中序遍历的结果为DBAECF，可以看到根节点A在中间，两个节点DB肯定在根节点的左子树，节点ECF肯定在根节点的右子树。再看前序遍历的结果，根节点A后访问B（所以B肯定是D的根节点），最后是D，所以再看中序遍历（先中序遍历左子树），所以D...
二叉树中,什么是前序,中序。后序!
3、特点为后续遍历的特点是执行操作时，肯定已经遍历过该节点的左右子节点，故适用于要进行破坏性操作的情况，比如删除所有节点 二叉树是数据结构中常被问到的相关知识点，也是需要了解的一个知识点，可以总结一下二叉树的前序、中序、后序遍历的相互求法，即如果知道两个的遍历，如何求第三种遍历方法...
已知一棵二叉树的层次遍历序列ABCDEFG,中序遍历为BAFGDCE,则这个二叉树...
ABCDFGE\/\/ 中序遍历序列: BAFGDCE\/\/ 后序遍历序列: BGFDECA\/\/ 层次遍历序列: ABCDEFG\/\/\/ 二叉树示意图:\/\/ A\/\/ \/ \\\/\/ B C\/\/ \/ \\\/\/ D E\/\/ \/\/\/ F\/\/ \\\/\/ G\/\/#include <stdio.h>#include <stdlib.h>#define OK 1#define OVERFLOW -2typede...
已知二叉树的中序序列,后序序列,怎么求前序序列
求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。...
用汇编实现二叉树的先序,中序,后序遍历
void PreOrderTraverse(BiTree T){\/\/先序遍历 if(T){ cout<<T->data<<' ';PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);} } void InOrderTraverse(BiTree T){\/\/中序遍历 if(T){ InOrderTraverse(T->lchild);cout<<T->data<<' ';InOrderTraverse(T->rchild);} } voi...
前序和中序相同的二叉树
这种二叉树只有一种可能，那就是每个节点都有两个子节点，且每个节点的左子节点和右子节点分别对应前序遍历和中序遍历的下一个节点。换句话说，这种二叉树是一种完全二叉树。对于完全二叉树来说，如果我们将树的节点按照从上到下、从左到右的顺序编号，那么前序遍历和中序遍历的结果将会相同。因为前...
...序遍历序列与中序遍历序列相同且树中结点数大于1,则该二叉树的...
【答案】：D 本题考查二叉树基本运算。先序遍历二叉树时，先访问根结点，然后先序遍历根的左子树，最后遍历根的右子树。因此，二叉树的先序遍历序列中第一个结点是树根结点。中序遍历二叉树时，首先中序遍历根结点的左子树，然后访问根结点，最后中序遍历根的右子树。因此，若已知二叉树的根结点，则...
数据结构中"遍历"是什么意思?
所谓遍历，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。
一棵二叉树的先序遍历序列为ABCDEF,中序遍历序列为CBAEDF,则后序遍历...
先序列号为这个，那么在编辑的时候，可以先进行用顺序的方式，然后再进行。后序序列是CBA。根据前序，可以确定A为根，A在中序中的位置，可以确定CB为A的左子树上的结点，没有右子树。确定A之后，再看中序第二值为B，查看B在中序中的位置，C在B左边，确定C为B的左子树。
员亚欣洛： 不是唯一的. 比如下面这两个二叉树 其中序遍历都是BAC.
深圳市13545671791： 已知中序遍历求二叉树先序遍历和后序遍历 - ？
员亚欣洛： 首先理解概念: 前序遍历:访问根结点的操作发生在遍历其左右子树之前. 中序遍历:访问根结点的操作发生在遍历其左右子树之中(间). 后序遍历:访问根结点的操作发生在遍历其左右子树之后. eg:后序遍历为DBCEFGHA,中序遍历为EDCBAHFG,求前序遍历(网上例子) 解:首先 看后序遍历DBCEFGHA,A为总根节点然后 寻找中序遍历EDCBAHFG中A位置,则EDCB在A的左枝,HFG在A的右枝;重复前两步,从后序遍历最后一位找,在中序遍历寻找对应点,得出左右分枝...最后得到AECDBHGF,再自己验证即可...
深圳市13545671791： 如何根据前序遍历序列和中序遍历序列确定二叉树 - ？
员亚欣洛： 假设某二叉树的先序遍历序列是abdgcefh,中序遍历序列是dgbaechf,画出二叉树,并给出其后序遍历序列. 分析过程: 以下面的例题为例进行讲解: 已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf,求二叉树及后...
深圳市13545671791： 由遍历序列求二叉树 - ？
员亚欣洛： 先序:中左右:1243576 中序:左中右:4215736 看先序,第一位为1,1就为二叉树的第一位.在看中序,可得该二叉树左边为:2,4;右边为:5,7,3,6;将中序分为两部分:2,4与3,5,7,6,这样1的两个子结点为2和3.看中序,4在2前面,4就在2的左边,5和7在3的前面,那么5和7就在3的左边,6在3的右边.最后要确定5和7的位置,看先序,5在7的前面,因此5在3的左边,7在5的左边.由此得树:1/ \2 3/ / \4 5 6/7 根据后序:左右中,得:4275631时间比较紧,这是以前我的最佳回答,只要把你的数据替换以下就好了,祝你成功
深圳市13545671791： 对下列二叉树进行中序遍历的结果为【】 F连着C,E E连着G C连着A,D A连着B D连着H,P - ？
员亚欣洛：[答案] 你的..这个问题描述的好抽象的,如果按我理解的那个图的话,(F为树根,F连着C E;C连着A D;E左侧连着G,右侧木有东东连;A左侧连着B,右侧也木有东东;D连着H,P)答案应该是这个吧:BACHDPFGE,二叉树的树根是F吧,进行中序遍历...
深圳市13545671791： C++中二叉树的前序(后序、中序)遍历分别是什么意思?相应的树图怎么看? - ？
员亚欣洛： 二叉树的遍历是指按照一定次序访问树中所有结点,并且每个节点仅被访问一次的过程. 1、先序遍历(前序) (1)访问根节点; (2)先序遍历左子树; (3)先序遍历右子树. 2、中序遍历 (1)中序遍历左子树; (2)访问根节点; (3...
深圳市13545671791： 中序二叉树 - ？
员亚欣洛： 对于例题的后序遍历的答案是,gdbehfca. 解答过程: 1)定义解释:树的遍历的三种情况,是根据左子树、右子树、根这3者的不同访问次序来定义的.根左右(根先访问),则为先序遍历;左根右,则为中序遍历;左右根,则为后序遍历. ...
深圳市13545671791： 一个数据结构二叉树的问题:已知一个二叉树的先序遍历为ABDFGEHC,中序遍历为FDGBEHAC, - ？
员亚欣洛： A/,D是根先序遍历为ABDFGEHC A是根中序遍历为FDGBEHAC 可知A的左子树是FDGBEH 右叶结点C F是 叶结点 后序遍历为 FGDHEBCA 结合上面FGDHEB中B是根;D E/ \B C/ \,可知FDG就B的左子树 EH是右子树 后序中有FGD,所以,E是根 结果为, G是右叶 后序中的HE说明H是叶,F是左叶,再看中序FDGBEH(找B的左右); \ \
深圳市13545671791： 为什么说森林的中序遍历对应的是二叉树的中序遍历.按照图中不是应该对应森林的后序遍历吗? - ？
员亚欣洛： 你得到的树其实已经是把之前得到的二叉树转化为一个普通的树了,虽然刚好这棵树也是二叉树.准确的表述是二叉树森林的中序遍历与完整二叉树中序遍历对应.
深圳市13545671791： C语言数据机构:由中序遍历和层次遍历能不能唯一确定一颗二叉树?为什么说法不一致哪? - ？
员亚欣洛： 由中序遍历和层次遍历能够唯一确定一颗二叉树.从下面的算法可知,每一步构造得到的二叉树结果是唯一的. 以下构造部分的答案来自: 假定树的层次遍历ABCDEFG HIJ中序遍历DBGEHJACIF 两种遍历顺序要结合着分析,才能画...
