[数据结构与算法]《数据结构》二叉树的性质及计算题考察

目录

先把二叉树性质列举一下：

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）

2.下列数据结构中，不适合采用顺序存储结构的是（ ）

3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）

4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）

5.一个具有767个节点的完全二叉树，其叶子节点个数为（）

先把二叉树性质列举一下：

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i- 1)个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1

3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0=n2+1, 即：度为0比度为2的永远多一个，别人总结出来的规律(记住就可以)

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log2(n + 1).(PS postscript 附言: log2(n + 1)是log以2为底，n+1为对数)

5.因为完全二叉树最后一层连续，所以度为1的节点只有一个或0个，a1=0 或者 1

6. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对

于序号为i的结点有：

1. 若i>0，i位置节点的双亲序号：(i-1)/2 (因为偶数除2向0取整，所以无论奇数还是偶数都是这个公式求双亲节点的数组下标)；i=0，i为根节点编号，无双亲节点

2. 若2i+1=n否则无左孩子

3. 若2i+2=n否则无右孩子

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）

A.?不存在这样的二叉树

B. 200

C. 198

D. 199

解：设度为0的节点个数为a0，度为2的节点个数为a2，a0=a2+1，199+1=200；选B

2.下列数据结构中，不适合采用顺序存储结构的是（ ）

A. 非完全二叉树

B. 堆

C. 队列

D. 栈

解:只有二叉树不是顺序存储,选A。

3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）

A. n

B. n+1

C. n-1

D. n/2

解：

假设度为0节点有a0个

假设度为1节点有a1个

假设度为2节点有a2个

2n = a0+a1+a2

2n = a0+a1+a0-1

2n=2a0-1+a1

因为完全二叉树最后一排的叶节点必须连续，所以度为1的节点只能是1个或者0个，此处如果a1是0，2n=2a0-1,

a0=(2n-1)/2,a0不可能是小数，所以a1必须是1，因此2n=2a0,a0=n;选A。

4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）

A. 11

B. 10

C. 8

D. 12

解：上一个题那样算虽然能算出叶节点个数a0，但不只是最后一排有叶节点，倒数第二排也有叶节点，所以就算求出来了也没法用，只能用代数法：

过程：①设高度是h(规定根节点层数是1)，已知高度h的二叉树最多有2^h-1个节点，设完全二叉树最后一排比满二叉树少了X个节点，所以有 2^h-1-X=531，即X=2^h-1-531=2^h-532 X最小是1(完全二叉树最后一排最少比满二叉树少1个节点)，X最大是 2^(h-1)-1 (当完全二叉树最后一排只有一个节点时，第 i 行最多有2^(i-1)个节点)

②然后我们不妨带入选项：A:h=11时，X最大是2^10-1=1024-1=1023，带入前面的等式X=2^11-532=2048-532=1516，X最大是1023,1516已经超了，不符合，所以排除A。

同理B:h=11时，X最大是2^9-1=512-1=511，带入前面的等式X=2^10-532=1024-532=492，492

C:h=8时，X最大是2^7-1=128-1=127，带入前面的等式X=2^8-532=256-532= -276，X是负数了，不符合，所以排除C。

D:h=12时同A，也不符合。 选B。

5.一个具有767个节点的完全二叉树，其叶子节点个数为（）

A. 383

B. 384

C. 385

D. 386

解：

假设度为0节点有a0个

假设度为1节点有a1个

假设度为2节点有a2个

767= a0+a1+a2

767= a0+a1+a0-1

767=2a0-1+a1

只有当a1是0时，a0才不为小数，可直接求出a0=384，选B。

答案：

1.B

2.A

3.A

4.B

5.B