前序和后序能确定二叉树吗
前序和后序不能确定二叉树。
前序和中序可以唯一确定一颗二叉树,后序和中序可以唯一确定一颗二叉树。
前序和后序是不能唯一确定一颗二叉树的。因为没有中序遍历无法确定左右部分,也就是无法分割。
扩展资料:
二叉树(Binarytree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树,且有左右之分。
二叉树是n个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成,是有序树。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个节点。
定义
二叉树(binarytree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树。
基本形态
二叉树是递归定义的,其节点有左右子树之分,逻辑上二叉树有五种基本形态:
1、空二叉树
2、只有一个根节点的二叉树
3、只有左子树
4、只有右子树
5、完全二叉树
特殊类型
1、满二叉树:如果一棵二叉树只有度为0的节点和度为2的节点,并且度为0的节点在同一层上,则这棵二叉树为满二叉树。
2、完全二叉树:深度为k,有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时,称为完全二叉树。
完全二叉树的特点是叶子节点只可能出现在层序最大的两层上,并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。
为什么已知一棵二叉树的前序遍历和后序遍历序列,不能唯一确定这棵二叉树...
这是因为同样的前序遍历和后序遍历序列,可以对应不同的二叉树。例如:已知一棵二叉树的前序遍历和后序遍历序列分别为ABC和CBA,则以下四棵二叉树均符合要求:A A A A \\ \\ \/ \/ B B B B \\ \/ \/ \\ C C C C ...
已知一棵二叉树的前序遍历和后序遍历,可以构造出一棵二叉树吗?
普通二叉树必须是这三者之一:前序和中序、后序和中序、层次序和中序才能还原出二叉树
为什么只给出前序和后序,不能唯一确定一个二叉树
具体过程就是根据前序和后序的性质来回切分,但是刚刚可以切分到左子树根为B,右子树的根为D,下面切分不下去了,并且序列也出现矛盾了 只有当正则二叉树,也就是只有度为0和度为2结点的二叉树(没有度为1的结点)才能够由正确的前序+后序序列唯一确定 ...
...遍历序列可以唯一确定一棵二叉树,而由前序和后序遍历则不能_百度知...
(5)同理可以得出,由中序序列和后序序还原二叉树的规则也成立。�(6)在还原过程中,读入序列的顺序也遵循也先根结点,后子树的规律。�3总结�在二叉树的一些应用中,如平衡二叉树、红黑树等,常常要观察二叉树的形态,对其进行判断并调整。根据遍历序列和二叉排序树的...
判断题 1.有一颗二叉树前序序列和后序序列可以唯一确定它 2.一棵树...
1、不对,只有一少部分二叉树可以这样唯一地确定 2、也不对,对应二叉树中叶子数一般比原来树的少些
知道二叉树先序,中序,后序其中的两个顺序列,如何画出二叉树
(3)由后序遍历序列和中序遍历序列能够唯一确定一棵二叉树。设后序序列为:a2,……,an , a1; 中序序列为:ap1,…,api, a1, …,apn 。则 a1为根结点;ap1,…,api为左子树的中序序列,a2,…,ai-1为左子树的后序序列。同样,也可确定右子树的中序和后序序列。按照上面方法...
由二叉树的后序序列和中序序列可唯一确定一棵二叉树,试构造相应的二叉树...
后序的最后一个元素是根,依据中序序列,就可把根的左右子树分出来。比如第一题,A是根,其左子树是(DCBFE),右子树是(GHI)。对每一个子树,又可根据这个原则继续分析下去:A的右子树的根是G,(IHG)的最后一个,G的右子树是H,H的右子树是I。。。1、A \/ \\ B G \/ \\ \\H C...
二叉树的先序、中序和后序遍历序列有什么特点?
【答案】先序遍历二叉树的顺序是“根—左子树—右子树”,中序遍历“左子树—根—右子树”,后序遍历顺序是:“左子树—右子树―根”,根据以上原则,解答如下:1)若先序序列与后序序列相同,则或为空树,或为只有根结点的二叉树。2)若中序序列与后序序列相同,则或为空树,或为任一结点至...
若某非空二叉树的先序序列和后序序列正好相同,则该二叉树的形态是什么...
若某非空二叉树的先序序列和后序序列正好相同,则该二叉树的形态是空树或是只有根结点的树。因为:若:根-左-右 == 左-右-根 当且仅当:左子树与右子树都为空树。
证明:由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树
因为知道先序遍历后,第一个根是唯一确定的.然后在中序遍历里这个根将它分为两个部分,第一个根的两棵子树的根也会唯一确定,依次此类推,所有子树的根都唯一确定,二叉树就是唯一的.
潘咏杏香:[答案] 已知先序和后序是不能还原二叉树的.原理:因为不知道左右孩子.
新晃侗族自治县17370146876: 先序遍历和后序遍历为什么不能唯一地确定一棵树 - ?
潘咏杏香: 这是因为同样的前序遍历和后序遍历序列,可以对应不同的二叉树. 例如:已知一棵二叉树的前序遍历和后序遍历序列分别为ABC和CBA,则以下四棵二叉树均符合要求: A A A A \ \ / / B B B B \ / / \ C C C C
新晃侗族自治县17370146876: 各位前辈们 如果给定结点的前序序列和后序序列能否确定一棵二叉树 - ?
潘咏杏香: 能 在二叉树的应用中,常常要求在树中查找具有某种特征的结点,或者对全部结点逐一进行某种处理.这就是二叉树的遍历问题.所谓二叉树的遍历是指按一定的规律和次序访问树中的各个结点,而且每个结点仅被访问一次.“访问”的含义很...
新晃侗族自治县17370146876: 判断题 1.有一颗二叉树前序序列和后序序列可以唯一确定它 2.一棵树中的叶子树一定等于与其对应的 - ?
潘咏杏香: 1、不对,只有一少部分二叉树可以这样唯一地确定2、也不对,对应二叉树中叶子数一般比原来树的少些
新晃侗族自治县17370146876: 什么情况下前序和后序可以决定一颗二叉树 - ?
潘咏杏香: 前序和后序在本质上都是将父节点与子结点进行分离,但并没有指明左子树和右子树的能力,因此得到这两个序列只能明确父子关系,而不能确定一个二叉树.
新晃侗族自治县17370146876: 已知先序和后序序列能建立二叉树吗? - ?
潘咏杏香: 不可能唯一确定一棵二叉树.不信你试试比较简单的:先序AB 后序BA A / B A \ B
新晃侗族自治县17370146876: 怎么唯一确定一棵二叉树?给定一颗二叉树的按层次遍历序列和后序遍历序列,可以确定唯一的一颗二叉树吗? - ?
潘咏杏香: 给出中序遍历之后再给一个其他的遍历就能够确定了,前序和后续不能确定.完全可以.例如:先序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
新晃侗族自治县17370146876: 前、中、后序,知道其中哪两个就可以还原二叉树? - ?
潘咏杏香: 1. 知道一棵二叉树(二叉树的子树也是二叉树)的前序和后序序列,就可以知道这棵二叉树的根.因为前序的第一个结点是当前这棵二叉树的根,后序序列的最后一个结点是根 2. 知道一棵二叉树的根,同时知道其中序序列,就可以知道根的左子树序列和右子树序列.因为中序序列中的根前的结点属于左子树,根后的结点属于右子树(这个由中序序列的遍历性质可知) 3. 所以只要知道前序和中序,或者中序和后序即可还原二叉树 4. 而只知道前序和后序无法保证还原二叉树,例如二叉树A 与 AB BC C 的前序序列都是ABC,而后序序列都是CBA
新晃侗族自治县17370146876: 二叉树 前序ABLECFDGI 后序LEBFCIGHDA 问该树能否唯一确定?不能的话给出反例吧~ - ?
潘咏杏香: 你的这个前序序列+后序序列根本不能唯一地确定二叉树,具体过程就是根据前序和后序的性质来回切分,但是刚刚可以切分到左子树根为B,右子树的根为D,下面切分不下去了,并且序列也出现矛盾了 只有当正则二叉树,也就是只有度为0和度为2结点的二叉树(没有度为1的结点)才能够由正确的前序+后序序列唯一确定
新晃侗族自治县17370146876: 为什么由二叉树的中序和前序遍历序列可以唯一确定一棵二叉树,而由前序和后序遍历则不能?同样为什么二叉树的中序和后序遍历序列可以唯一确定一棵... - ?
潘咏杏香:[答案] 前序和后序在本质上都是将父节点与子结点进行分离,但并没有指明左子树和右子树的能力,因此得到这两个序列只能明确父子关系,而不能确定一个二叉树.