树和二叉树习题思维导图

A 7

B 16

C 15

D 17

解释：因为森林的头节点和左子树由第一颗树组成， 故森林F对应的二叉树根结点的右子树上的结点个数=总节点个数-第一颗树的个数=除第一棵树外的所有树的节点个数和，故选C。

A 二叉树遍历就是按照某种规律访问二叉树中所有的结点，且每个结点仅访问一次

B 二叉树遍历就是随机访问二叉树中所有的结点，且每个结点仅访问一次

C 二叉树遍历就是访问二叉树中部分结点

D 二叉树遍历就是访问二叉树中所有的结点

解释：遍历二叉树（Traversing Binary Tree）是指按某条搜索路径巡访树中每个节点，使得每个节点均被访问一次，而且仅被访问一次。故选A。

A 权

B 序

C 维数

D 次数(或度)

解释：一个结点的子树个数称为该结点的“度”。在二叉树中，每个节点的度定义为该节点的子节点个数。一个节点的度可以是0、1或2，分别对应于叶子节点、单个子节点的父节点和两个子节点的父节点。故选D。

A 互不相交

B 允许相交

C 允许树枝结点相交

D 允许叶结点相交

解释：树（tree）是包含 n(n≥0) [2] 个节点，当 n=0 时，称为空树，非空树中条边的有穷集，在非空树中：

（1）每个元素称为节点（node）。

（2）有一个特定的节点被称为根节点或树根（root）。

（3）除根节点之外的其余数据元素被分为个互不相交的集合，其中每一个集合本身也是一棵树，被称作原树的子树（subtree）。

树也可以这样定义：树是由根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位，这个节点称为该树的根节点，或称为树根。

故由树的定义知，本题选A。

A 6

B 5

C 7

D 8

解释：度为1,2.3.4的结点个数分别为4,2,1,1 ，意思就是有只有一个分支的结点有4个，有两个分支的结点有2个，有3个分支的结点有1个，有4个分支的结点有1个。

结点的度: 结点拥有的子树数（每个结点有多少个分支）。

叶子(终端结点): 度为零的结点（没有分支的结点）。

树的度: 树内各结点的度的最大值。

由树的性质知: 结点数为所有结点的度数之和加1，同时注意到叶了结点的度数为0，则总结点数(设叶了结点数为1*4+2*2+3*1+4*1+X*0+1=16，叶子结点数为总结点数减去含有度的节点数：X=16-4-2-1-1=8。故选D。

A n-1

B n+h

C h-1

D n*h

解释：分支树就是节点数减去根节点，即n-1，故选A。

A 30

B 35

C 18

D 20

解释：哈夫曼树是所有节点的度为2或0（叶子节点）的二叉树。

1. 设n_o,n_1,n_2分别指度为0，1，2的节点数。因为二叉树中所有节点的度都小于2，所以其节点总数为n = n_0 + n_1 + n_2，又因为哈夫曼树是所有非叶子节点的度为2，即n_1 = 0，得到n = n_0 + n_2

2. 由于，除了根节点外，二叉树的其余节点都有一个分支进入，设B为分支总数，则n = B + 1。这些分支是由度为1或2的节点射出的，因此又有 B = n_1 + 2n_2。则有n = n_1 + 2n_2 + 1,又因为哈夫曼树是所有非叶子节点的度为2，则n = 2n_2 + 1。

由 1 和 2 消去n_2知，n = 2n_0 - 1的，由题解得，n_0 = 18。故选C。

由此题可知，哈夫曼树的节点数与叶子节点树的关系为：n = 2n_0 - 1

A 二叉树中每个结点的度可以小于2

B 二叉树中至少有一个结点

C 二叉树中每个结点的度均为2

D 二叉树中至少有一个结点的度为2

解释：二叉树中不存在度大于2的节点，即在二叉树中度小于或等于2，同时二叉树可以为空。故选A。

A 5

B 6

C 4

D 7

解释：先将二叉树转化称森林

化为孤立二叉树

二叉树化为树

结果

故选B

A (n+1)/k

B (nk-n+1)/k

C n(k-1)/k

D n-k

解释：因为n = kn_k + 1 和n = n_0 + n_k ，故(nk-n+1)/k。故选B。

A h/2

B 1

C log2h

D h

解释：树的深度：树中结点的最大层数称为树的深度或高度。

由满二叉树的结构可知，满二叉树对应的森林棵树即为满二叉树的高度。故选D。

A n

B n+1

C n-1

D 2n

解释：在线索二叉树中，线索个数即为空指针域的个数， 而在节点数为n的二叉树中，每个节点都有两个指向左右孩子的指针，则共有2n个指针域，而n个节点共有n-1条分支，所以共有2n-(n-1)个空指针域，即有n+1个线索。故选B。

空指针域（null pointer field）是指在数据结构中的指针或引用没有指向任何有效对象或内存地址的情况。在许多编程语言中，空指针用特殊的值（如null）来表示，表示该指针没有指向任何有效的内存位置。

在树结构（如二叉树）中，空指针域通常指的是那些本应该指向子节点的指针，但实际上并没有指向任何子节点的情况。例如，在二叉树中，如果一个节点没有左子节点或右子节点，那么它的左指针域或右指针域将是空的（null）。

在线索二叉树中，空指针域被利用来存储额外的信息，如节点的前驱或后继信息，这样可以将二叉树链式化，方便中序遍历等操作。在这种结构中，原本为空的指针域被用来存储线索，指向中序遍历序列中的前一个或后一个节点。

A 2^h-1

B 2^{h-1}-1

C 2^{h-1}

D 2^{h-1}+1

解释：一棵高度为h的非空平衡二叉树，其每个非叶子结点的平衡因子均为0，说明该二叉树是一棵完满二叉树，则其节点个数为2^h - 1，故选A。

A 998

B 1001

C 1000

D 999

解释：哈夫曼树编码的字符位于叶子节点处，故本题可转化为求哈夫曼树的叶子节点的个数，又由于在哈夫曼树中n = 2n_0 - 1，解得n_0 = 1000，故选C。

A 2^{h-1}+1

B 2^h+1

C 2^{h-1}

D 2^h

解释：由完全二叉树的性质：具有n个节点的完全而二叉树的深度为:[log_2n] + 1，可知h-1<=log_2n<=h，解得2^{h-1}<=n<=2^h，故选C。

A 右孩子

B 左孩子

C 标识

D 指针

解释：由线索二叉树的定义知，线索即为指针，故选D。

A 25

B 12

C 26

D 13

解释：权值数即为哈夫曼树中的叶子节点的个数，由哈夫曼树叶子节点和节点总数的关系：n = 2n_0 - 1知，本题选A。

A 对

B 错

解释：1)树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱

2)树中所有结点可以有零个或多个后继，树适合于表示具有层次结构的数据.，而树中每个结点与其下层的零个或多个结点(即其子女结点)有直接关系。故选B

A 对

B 错

解释：二又树是度为2的有序树，这个说法错误。故选B。

二叉树的度不大于2。

树结构通常结合了另外两种数据结构的优点: 一种是有序数组，另外一种是链表。

A 对

B 错

解释：二叉树某种遍历方式产生的结果是一个线性序列。故选A。

A 对

B 错

解释：哈夫曼树中没有度为1的结点，故由n0 = n2+1以及m=n0+n1+n2，n1=0可推出m=2*n0-1，即一棵有n个叶子节点的哈夫曼树共有2n-1个节点。故选A。

A 对

B 错

解释：不一定。非空二叉树的中序序列的第一个结点不一定是叶子结点。中序遍历二叉树的顺序是先遍历左子树，然后访问根结点，最后遍历右子树。这意味着中序序列的第一个结点是二叉树的最左下结点，它可能是叶子结点，也可能是有子结点的内部结点。

例如，考虑以下二叉树：

这棵树的中序序列是：D, B, E, A, C。其中，第一个结点是D，它是一个叶子结点。

再考虑另一个二叉树：

这棵树的中序序列是：D, B, A, C, E。其中，第一个结点是D，它不是一个叶子结点，因为它有一个右子结点E。

因此，中序序列的第一个结点可以是叶子结点，也可以是内部结点，这取决于树的具体结构。故选B。

A 对

B 错

解释：非空二叉树的先序序列的最后一个结点一定是叶子结点。故选A。

A 对

B 错

解释：度为2的树要求每个节点最多有两个子树，并且至少有一个节点有两个子树。二叉树的要求是度不大于2，节点最多有两个叉，可以是1或0。故选B。