树的度,结点,叶子结点,二叉树

2021年7月7日 14点热度 0条评论 来源: CCspaceport

设树T的度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中有多少个叶子结点?
A.4
B.6
C.8
D.10

一棵含有n个结点的树,有n-1个分支,即 n = 14 + 22 + 31 + 41 + 1 = 16;
又由于 n = n0 + n1 + n2 + n3 + n4 = n0 + 8;
n0 + 8 = 16,所有叶子结点个数为8

规律1: (节点个数)m=(边数)n+1
规律2: 度为节点的子女个数,可以看作几个出边就是几个度,叶子节点没有度

三叉树中,度为1的结点有5个,度为2的结点3个,度为3的结点2个,问该树含有几个叶结点?
A. 8
B. 10
C. 12
D. 13

总结点数:1 * 5 + 2 * 3 + 3 * 2 + X * 0 + 1 = 18
叶子结点数:X = 18 - 5 - 3 - 2 = 8

设每个d叉树的结点有d个指针指向子树,有n个结点的d叉树有多少空链域?
A.nd
B.n(d−1)
C.n(d−1)+1
D.以上都不是

每个d叉树的结点有d个链域(就是d条边,每个结点不满d条边的,少几条边就几个空链域)
应该具有边的条数:nd
现有边的条数:n-1
空链域个数:nd-(n-1)= n(d−1)+1

有一个四叉树,度2的结点数为2,度3的结点数为3,度4的结点数为4。问该树的叶结点个数是多少?
A. 10
B. 12
C. 20
D. 21

总结点数=10+22+33+44+0*x+1=30
叶结点数=30-2-3-4=21

以二叉链表作为二叉树的存储结构,在具有 n 个结点的二叉链表中(n>0),空链域的个数为 __
A.n+1
B.n
C.n−1
D.无法确定

n个结点的二叉树
每个结点有两个指针域,所以总共有2n个指针
除了根节点没有被指针指向,其他结点的有一个有效的指针指向
所以有n-1个有效指针
则空链域=2n-(n-1)=n+1

对于任意一棵高度为 5 且有 10 个结点的二叉树,若采用顺序存储结构保存,每个结点占 1 个存储单元(仅存放结点的数据信息),则存放该二叉树需要的存储单元的数量至少是:(A)
A.31
B.16
C.15
D.10

二叉树是一种特殊的树 F

二叉树不是一种特殊的树,二叉树可以为空,树不能为空
树与二叉树的两个主要区别:
1.树中结点的最大度数没有限制,二叉树结点的最大度数为2
2.树的结点无左右之分,二叉树的结点有左右之分

若A和B都是一棵二叉树的叶子结点,则存在这样的二叉树,其前序遍历序列为…A…B…,而中序遍历序列为…B…A…。F

先序中序后序是对根结点而言,叶子结点的顺序保持不变

将一棵完全二叉树存于数组中(根结点的下标为1)。则下标为23和24的两个结点是兄弟。F

根结点为n的左孩子为2n,右孩子为2n+1.
故23和24不可能是兄弟。

一棵有9层结点的完全二叉树(层次从1开始计数),至少有255个结点。F

9层全部满的情况下共有2^8-1=256-1=255个结点。此时是一棵9层的满二叉树,而题目中说的是完全二叉树,所以应该为至多255个结点。

对两棵具有相同关键字集合而形状不同的二叉排序树,按中序遍历它们得到的序列的顺序却是一致的。T

二叉排序树/二叉搜索树:
1.非空左子树的所有键值小于其根结点的键值
2.非空右子树的所有键值大于其根结点的键值
3.左、右子树都是二叉搜索树
4.没有键值相等的结点

中序遍历它以后,也就是排成从小到大的顺序,所以得到的序列的顺序是一致的

二叉搜索树中,新结点总是作为树叶来插入的

二叉搜索树的查找效率和二叉排序树的高度有关

满二叉树:每层都是满的;
完全二叉树:除最后一层外,每层都是满的,并且或者最后一层是满的,或者是在右边缺少连续若干结点;

深度为6的二叉树最多有( )个结点。
64
63
32
31

2^6-1=63

一个具有1025个结点的二叉树的高h为( )个。
11
10
11至1025之间
10至1024之间

若将一棵树 T 转化为对应的二叉树 BT,则下列对 BT 的遍历中,其遍历序列与 T 的后根遍历序列相同的是:
先序遍历
中序遍历
后序遍历
按层遍历

一棵树的后根遍历与这棵树所对应的二叉树的中序遍历相同。因为树转化为二叉树后是没有右子树的,所以最后访问的是树的根结点。

二叉树的顺序存储结构:

  • 这种结构是用一组连续的存储单元(比如数组)存储二叉树结点的数据,结点的父子关系是通过他们的相对位置来反映的,而不需要任何附加的存储单元来存放指针
  • 通常情况下,顺序存储用于完全二叉树的存储
  • 具体实现是从树的根结点开始,从上到下,从左到右,依次给结点编号并将数据存放到一个数组的对应单元中

在N个结点的完全二叉树中,对于下标为i的结点:

  • 当i/2>=1时,i/2单元时其父节点;当i/2=0时,表明该结点是树的根节点,无父节点
  • 当2i<=N时,2i单元是其左孩子;否则无左孩子
  • 当2i+1<=N时,2i+1单元是其右孩子,否则无右孩子

二叉树的链表存储:
每个结点由数据和左右指针三个数据成员组成:

typedef struct TNode *Position;
typedef Position BinTree;//二叉树类型BT
struct TNode{ 
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

二叉树的遍历:先序遍历,中序遍历,后序遍历,层序遍历

利用二叉链表存储树,则根结点的右指针是( )。
指向最左孩子
指向最右孩子

非空

二叉链表根节点的左指针指向树的根节点,右指针指向树的根节点的兄弟
树的根节点没有兄弟,因此为空

树的三种常用存储结构:

  • 双亲表示法
  • 孩子表示法
  • 孩子兄弟表示法

在下列存储形式中,( )不是树的存储形式。
双亲表示法
孩子链表表示法
孩子兄弟表示法
顺序存储表示法

对于一个有N个结点、K条边的森林,共有几棵树?
A.N−K
B.N−K+1
C.N−K−1
D.不能确定

由一颗树的性质:结点=边+1【n= k+ 1】
等价于 n - k =1
故共有 n - k 棵树

设森林F中有三棵树,第一、第二、第三棵树的结点个数分别为M1,M​2和M​3​​ 。则与森林F对应的二叉树根结点的右子树上的结点个数是:
A.M1
​​B.M​1​​ +M​2
​​C.M​2​​ +M​3
​​D.M3
​​

    原文作者:CCspaceport
    原文地址: https://blog.csdn.net/m0_53372088/article/details/118531520
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。