把一棵树转换为二叉树后,这棵二叉树的形态是()。
一棵树转换为二叉树后,这棵二叉树的形态唯一
一、 判断题:
( )1. 若二叉树用二叉链表作存贮结构,则在n个结点的二叉树链表中只有n—1个非空指针域。
( )2.二叉树中每个结点的两棵子树的高度差等于1。
( )3.二叉树中每个结点有两棵非空子树或有两棵空子树。
( )4.二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值,且小于其右非空子树(若存在的话)所有结点的关键字值。
( )5.二叉树中所有结点个数是2k-1-1,其中k是树的深度。
二、填空题:
1.由3个结点所构成的二叉树有 种形态。
2.一棵深度为6的满二叉树有 个分支结点和 个叶子。
3.一棵具有257个结点的完全二叉树,它的深度为 。
4.设一棵完全二叉树有700个结点,则共有 个叶子结点。
5.一棵含有n个结点的k叉树,可能达到的最大深度为 ,最小深度为 。
6.二叉树的基本组成部分是:根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种:前序法(即按N L R次序),后序法(即按 次序)和中序法(也称对称序法,即按L N R次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是 。 7.中序遍历的递归算法平均空间复杂度为 。
8.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是 。
三、单项选择题
1. 不含任何结点的空树( )。
(A)是一棵树; (B)是一棵二叉树;
(C)是一棵树也是一棵二叉树; (D)既不是树也不是二叉树
2.二叉树是非线性数据结构,所以( )。
(A)它不能用顺序存储结构存储; (B)它不能用链式存储结构存储;
(C)顺序存储结构和链式存储结构都能存储;D)顺序存储结构和链式存储结构都不能使用
3.把一棵树转换为二叉树后,这棵二叉树的形态是( )。
(A)唯一的 (B)有多种
(C)有多种,但根结点都没有左孩子 (D)有多种,但根结点都没有右孩子
4.从供选择的答案中,选出应填入下面叙述 ? 内的最确切的解答,把相应编号写在答卷的对应栏内。
树是结点的有限集合,它A 根结点,记为T。其余的结点分成为m(m≥0)个
的集合T1,T2,…,Tm,每个集合又都是树,此时结点T称为Ti的父结点,Ti称为T的子结点(1≤i≤m)。一个结点的子结点个数为该结点的 。
供选择的答案
A: ①有0个或1个 ②有0个或多个 ③有且只有1个 ④有1个或1个以上
B: ①互不相交 ② 允许相交 ③ 允许叶结点相交 ④ 允许树枝结点相交
C: ①权 ② 维数 ③ 次数 ④ 序
5.从供选择的答案中,选出应填入下面叙述 ? 内的最确切的解答,把相应编号写在答卷的对应栏内。
二叉树 。在完全的二叉树中,若一个结点没有 ,则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里,一个结点N的左子女是N在原树里对应结点的 ,而N的右子女是它在原树里对应结点的 。
供选择的答案
A: ①是特殊的树 ②不是树的特殊形式 ③是两棵树的总称 ④有是只有二个根结点的树形结构
B: ①左子结点 ② 右子结点 ③ 左子结点或者没有右子结点 ④ 兄弟
C~D: ①最左子结点 ② 最右子结点 ③ 最邻近的右兄弟 ④ 最邻近的左兄弟
⑤ 最左的兄弟 ⑥ 最右的兄弟
答案:A= B= C= D=
树转换成二叉树,根节点是没有右孩子的,这由转换规则应该不难理解,且转换规则是唯一的,所以转换成的二叉树是唯一的。
一棵深度为k,且有2^k-1个结点的二叉树,称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。
而在一棵二叉树中,除最后一层外,若其余层都是满的,并且或者最后一层是满的,或者是在右边缺少连续若干结点,则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树,至少有2k-1个叶子结点,至多有2k-1个结点。
扩展资料
对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树, 则对一棵二叉树的遍历有三种情况:DLR(称为先根次序遍历),LDR(称为中根次序遍历),LRD (称为后根次序遍历)。
参考资料来源:百度百科-二叉树
A.树转换成二叉树,根节点是没有右孩子的,这由转换规则应该不难理解,且转换规则是唯一的,所以转换成的二叉树是唯一的
森林与二叉树的转换
将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可,此时,树中的每个结点最多有两个指针:一个指针指向第一个孩子,另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时,就是一棵二叉树了。特点:一棵树转换成二叉树后,根结点没有右孩子。
森林转化为二叉树的方法
将一棵树转换为二叉树的方法是:1、树中所有相邻兄弟之间加一条连线。2、对树中的每个结点,只保留其与第一个孩子结点之间的连线,删去其与其它孩子结点之间的连线。3、以树的根结点为轴心,将整棵树顺时针旋转一定的角度,使之结构层次分明。由于树中每个结点可能有多棵树,则可用多重链表,即每个...
把一棵树转换为二叉树后,这棵二叉树的形态是()。
树转换成二叉树,根节点是没有右孩子的,这由转换规则应该不难理解,且转换规则是唯一的,所以转换成的二叉树是唯一的。一棵深度为k,且有2^k-1个结点的二叉树,称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且或者最...
把一棵树转换为二叉树后,这棵树的形态是唯一的吗
一棵树转换为二叉树后,这棵二叉树的形态唯一
树、森林与二叉树的转换
树或森林与二叉树之间有一个自然的一一对应关系 任何一个森林或一棵树可惟一地对应到一棵二叉树 反之 任何一棵二叉树也能惟一地对应到一个森林或一棵树 .树 森林到二叉树的转换 ( )将树转换为二叉树 树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟 按照这种关系很自然地就能将树转换成相应...
将一棵树转换为二叉树后,为什么根节点没有右子树
树转化为二叉树时结点左子树是原来的孩子结点,右子树是原来的兄弟结点。即取根节点左孩子向右连接他的兄弟结点(在同一层次的节点,原来互不相连)并把它的子树,而把除左孩子外,原来与根节点相连的线擦除。这样根节点没有右孩子,因为由树转化来的二叉树某个节点A的左子树是原来作为树时A的孩子,...
将一棵树转换为完全二叉树后,根结点没有左子数对吗?
完全二叉树中除了叶节点其余所有节点均有左子树和右子树,叶节点偏向左边,因此除非仅有1各节点,否则根节点就有左子树
这个题怎样做,数据结构将下列树转化为二叉树,怎么做
二叉树的根结点和左子树作为森林的第一棵树,剩下的按同样的方法卸下根结点和左子树作为第二颗树,以此类推;所以转换后的森林是: {e,a,d,c,b,j} {f} {g,h} {i}
在C++中如何将森林转换为二叉树呢?
以下是步骤:1、转换:将森林中的每棵树转换成二叉树;2、连线:第一颗树不动,从第二棵树开始,依次把后一棵树的根节点座位前一棵树的根节点的右孩子,知道所有的二叉树都连在一起,即完成了森林向二叉树的转换。3、旋转:以根节点为轴心,将整棵树顺时针旋转一定角度,得到层次分明的二叉树。...
一棵树的后序遍历与这棵树所对应的二叉树的中序遍历相同吗?
给定一棵树,可以找到唯一一棵二叉树与之对应,同样,森林也与一棵树存在一一对应关系。树与二叉树,森林与二叉树的转化(a)(b)(c)为三棵树,并构成一个森林,(d)(e)(f)分别为(a)(b)(c)对应的二叉树,(g)为森林对应的二叉树。树结构有两种次序遍历树的方法:1、先根遍历:...
穆忠蓝花:[选项] A. 唯一的,且根结点没有右孩子 B. 有多种,但根结点都没有右孩子 C. 唯一的,且根结点可能右孩子 D. 有多种,且根结点可能有右孩子
满洲里市14766658446: 一棵树转换成二叉树后,这棵二叉树的根结点一定没有 - ?
穆忠蓝花:[答案] 根结点一定没有右子树,因为右边的是兄弟,而一棵树中的根是没有兄弟的,除非是在森林中
满洲里市14766658446: 把一棵树转换为二叉树后,这棵树的形态是唯一的吗 - ?
穆忠蓝花:[答案] 应该问的是这棵二叉树形态是唯一的吧,这个只要转换规则一致,结果自然唯一
满洲里市14766658446: 简述树与它转化的二叉树(孩子兄弟表示法)的关系,并说明转化后的二叉树的特点.数据结构中树可以用孩子兄弟法转换成二叉树,他们直接有什么关系且... - ?
穆忠蓝花:[答案] 1、转换后的二叉树没有右子树 2、原树中叶子就变成了没有左子树的结点了 3、树的先根遍历就和这个二叉树的先序一样 4、树的后根遍历就和这个二叉树的中序一样 还有一些别的可以慢慢推导出来