为什么一棵树可以唯一对应一棵二叉树？

为什么一棵树可以唯一对应一棵二叉树~

二叉树的做成是按照规则来的，按照规则，树的某一个节点作为另一个节点的父节点，或者兄弟节点，或者子节点，这个都是按照逻辑来做成的。
这样的方式是为了保证一棵树做成二叉树之后可以还原成那棵树。
二叉树只是作为树的更高效率的存储方式而已，所以为了保证树结构不会被弄乱，所以按照上面的逻辑，一棵树只能对应一棵二叉树

序、中序或由中序、后序遍历结果快速还原二叉树的方法。�
二叉树是最为常用的数据结构，它的实际应用非常广泛。二叉树的遍历方式有三种，前序遍历、中序遍历、后序遍历。先序遍历的顺序为：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总结�
在二叉树的一些应用中，如平衡二叉树、红黑树等，常常要观察二叉树的形态，对其进行判断并调整。根据遍历序列和二叉排序树的性质快速还原出二叉树对于研究相关的问题有很大的帮助。

二叉树的做成是按照规则来的，按照规则，树的某一个节点作为另一个节点的父节点，或者兄弟节点，或者子节点，这个都是按照逻辑来做成的。
这样的方式是为了保证一棵树做成二叉树之后可以还原成那棵树。
二叉树只是作为树的更高效率的存储方式而已，所以为了保证树结构不会被弄乱，所以按照上面的逻辑，一棵树只能对应一棵二叉树

这就像一个人只对应一个身份证号码、‘、（不好解释哇

其实原理我也搞不清楚，但是变换的时候的确是一对一，可以亲自试验一下。

就是按照兄弟节点法，按照规则一步一步来就只能一种

---

惠州市17777667075： 为什么一棵树可以唯一对应一棵二叉树 - ？
俞蔡宁中： 二叉树的做成是按照规则来的,按照规则,树的某一个节点作为另一个节点的父节点,或者兄弟节点,或者子节点,这个都是按照逻辑来做成的. 这样的方式是为了保证一棵树做成二叉树之后可以还原成那棵树. 二叉树只是作为树的更高效率的存储方式而已,所以为了保证树结构不会被弄乱,所以按照上面的逻辑,一棵树只能对应一棵二叉树

惠州市17777667075： 为什么一棵树可以唯一对应一棵二叉树?看了很久没有看懂.谢谢. - ？
俞蔡宁中：[答案] 二叉树的做成是按照规则来的,按照规则,树的某一个节点作为另一个节点的父节点,或者兄弟节点,或者子节点,这个都是按照逻辑来做成的.这样的方式是为了保证一棵树做成二叉树之后可以还原成那棵树.二叉树只是作为树的更...

惠州市17777667075： 任何一棵二叉树都有一棵树与之对应这句话对吗? - ？
俞蔡宁中： 对, 任何一棵树 都有唯一的与他对应的2叉树, 反过来 .任何二叉数,都有与他对应的树,只是不是唯一的

惠州市17777667075： 怎么唯一确定一棵二叉树?给定一颗二叉树的按层次遍历序列和后序遍历序列,可以确定唯一的一颗二叉树吗? - ？
俞蔡宁中： 给出中序遍历之后再给一个其他的遍历就能够确定了,前序和后续不能确定.完全可以.例如:先序abdecf,中序dbeafc. 分析思路. 1、先序就是根左右,中序就是左根右.所以在先序中a在前即为根.在中序中找到a,则dbe为其左子树,fc为其右子树. 2、dbe左子树在先序中b在前说明b为根,则中序中d为b左子树,e为b右子树. 3、同理fc在先序中c在前说明c为根,中序中f在c前,说明f为c的左子树. 即得如下图: a / \ b c / \ / d e f

惠州市17777667075： 判断题 1.有一颗二叉树前序序列和后序序列可以唯一确定它 2.一棵树中的叶子树一定等于与其对应的 - ？
俞蔡宁中： 1、不对,只有一少部分二叉树可以这样唯一地确定2、也不对,对应二叉树中叶子数一般比原来树的少些

惠州市17777667075： 先序遍历和后序遍历为什么不能唯一地确定一棵树 - ？
俞蔡宁中： 这是因为同样的前序遍历和后序遍历序列,可以对应不同的二叉树. 例如:已知一棵二叉树的前序遍历和后序遍历序列分别为ABC和CBA,则以下四棵二叉树均符合要求: A A A A \ \ / / B B B B \ / / \ C C C C

惠州市17777667075： 一棵二叉树为什么不一定是一棵树? - ？
俞蔡宁中：[答案] 树的逻辑结构特征是:树中任一结点都可以有零个或多个直接后继(孩子)结点,但至多只能有一个直接前趋(双亲)结点.树形结构是非线性结构.二叉树是n(n≥0)个结点的有限集,它或者是空集(n=0),或者由一个根结点及两棵互不相交的分别称作...

惠州市17777667075： 证明:由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树 - ？
俞蔡宁中： 因为知道先序遍历后,第一个根是唯一确定的.然后在中序遍历里这个根将它分为两个部分,第一个根的两棵子树的根也会唯一确定,依次此类推,所有子树的根都唯一确定,二叉树就是唯一的.

惠州市17777667075： 把一棵树转换为二叉树后,这棵树的形态是唯一的吗 - ？
俞蔡宁中： 应该问的是这棵二叉树形态是唯一的吧,这个只要转换规则一致,结果自然唯一

惠州市17777667075： 为什么由二叉树的中序和前序遍历序列可以唯一确定一棵二叉树,而由前序和后序遍历则不能?同样为什么二叉树的中序和后序遍历序列可以唯一确定一棵... - ？
俞蔡宁中：[答案] 前序和后序在本质上都是将父节点与子结点进行分离,但并没有指明左子树和右子树的能力,因此得到这两个序列只能明确父子关系,而不能确定一个二叉树.