最新消息: USBMI致力于为网友们分享Windows、安卓、IOS等主流手机系统相关的资讯以及评测、同时提供相关教程、应用、软件下载等服务。

二叉树习题及答案

IT圈 admin 31浏览 0评论

2024年4月7日发(作者:考潍)

1.

设一棵完全二叉树共有

699

个结点,则在该二叉树中的叶子结点数?

1

根据

二叉树的第

i

层至多有

2^(i − 1)

个结点;深度为

k

的二叉树至多有

2^k − 1

个结点;

个结点(根结点的深度为

1

这个性质:

这个性质:

因为

2^9-1 < 699 < 2^10-1 ,

所以这个完全二叉树的深度是

10

,前

9

层是一个满

二叉树,

二叉树,

这样的话,前九层的结点就有

这样的话,

前九层的结点就有

2^9-1=511

个;而第九层的结点数是

个;

而第九层的结点数是

2^(9-1)=256 

所以第十层的叶子结点数是

699-511=188

个;

个;

现在来算第九层的叶子结点个数。

现在来算第九层的叶子结点个数。

由于第十层的叶子结点是从第九层延伸的,所以应该去掉第九层中还有子树的结

点。因为第十层有

188

个,所以应该去掉第九层中的

188/2=94

个;

个;

所以,第九层的叶子结点个数是256-94=162,加上第十层有

256-94=162

,加上第十层有188个,最后结果

是350个

2

完全二叉树:若二叉树中最多只有最下面两层的结点的度可以小于

2

,并且最

下面一层的结点(叶结点)

下面一层的结点

(叶结点)都依次排列在该层最左边的位置上,

(叶结点)

都依次排列在该层最左边的位置上,这样的二叉树为

都依次排列在该层最左边的位置上,

这样的二叉树为

完全二叉树。

完全二叉树。

比如图:

比如图:

完全二叉树除叶结点层外的所有结点数(叶结点层以上所有结点数)为奇数,

此题中,

699

是奇数,叶结点层以上的所有结点数为保证是奇数,则叶结点数必

是偶数,这样我们可以立即选出答案为

B

如果完全二叉树的叶结点都排满了,则是满二叉树,

如果完全二叉树的叶结点都排满了,

则是满二叉树,易得满二叉树的叶结点数是

其以上所有层结点数

+1

比如图:

比如图:

此题的其实是一棵满二叉树,我们根据以上性质,699+1=700,

699+1=700

,700/2=350,即

700/2=350

,即

叶结点数为350,叶结点层以上所有结点数为

350

,叶结点层以上所有结点数为350-1=349。

350-1=349

3

完全二叉树中,只存在度为

2

的结点和度为

0

的结点,而二叉树的性质中有一条是:

n0=n2+1

n0

指度为

0

的结点,即叶子结点,

n2

指度为

2

的结点,所以

2n2+1=699 n2=349

n0=350 

2.

在一棵二叉树上第

5

层的结点数最多是多少

一棵二叉树,如果每个结点都是是满的,那么会满足

2^(k-1)1

所以第

5

层至多有

2^(5-1)=16

个结点!

个结点!

3.

在深度为

5

的满二叉树中,叶子结点的个数为

答案是

16 ~ 

叶子结点就是没有后件的结点

~ 

说白了

~ 

就是二叉树的最后一层

~ 

深度为

K

的二叉树

~ 

最多有

2^k-1

个结点

~ 

最多有

2^(k-1)

个结点

~ 

所以此题

~ 

最多有

2^5-1=31

个结点

~ 

最多有

2^(5-1)=16

个叶子结点

~ 

4.

某二叉树中度为

2

的结点有

18

个,则该二叉树中有几个叶子结点?

结点的度是指树中每个结点具有的子树个数或者说是后继结点数。

题中的度为

2

是说具有的

2

个子树的结点;

个子树的结点;

二叉树有个性质:二叉树上叶子结点数等于度为

2

的结点数加

1

5.

在深度为

7

的满二叉树中,度为

2

的结点个数为多少,

就是第一层只有一个节点,他有两个子节点,第二层有两个节点,他们也都有两个子节点

就是第一层只有一个节点,他有两个子节点,第二层有两个节点,他们也都有两个子节点

以此类推,所以到第

6

层,就有

2

5

次方个节点,他们都有两个子节点

次方个节点,他们都有两个子节点

最后第

7

层都没有子节点了。因为是深度为

7

的。

的。

所以就是

1+2+4+8+16+32

2

深度为

1

的时候有

0

深度为

2

的时候有

1

深度为

3

的时候有

3

深度为

4

的时候有

7

.... 

深度为

n

的时候有(

2

n-1

次方减

1

)个

)个

6.

一棵二叉树中共有

70

个叶子结点与

80

个度为

1

的结点,则该二叉树中的总结点

数为?

假设

n

表示二叉树的所有结点数,

n0

表示度为

0

的结点

(

叶子结点

)

n1

表示度

1

的结点,

n2

表示度为

2

的结点,由二叉树的性质有:

的结点,由二叉树的性质有:

n0 = n2 + 1 

已知

n0 = 70

n2 = n0 -1 = 69 

n = n0 + n1 + n2 

= 70 + 80 + 69 

= 219

总结点数 n=70+80+70-1=219

总结点数

n=70+80+70-1=219

2解:对任一二叉树

解:对任一

二叉树,如果其叶子结点

,如果其

叶子结点为n0,度为

n0

,度为1的结点数为n1,度为

n1,

度为2的结

点数为n2,则

n2

,则n0=n2+1;

然后由

然后由n=n0+n1+n2①即可得出。(n

n=n0+n1+n2①即可得出。

(n为结点总数)

为结点总数

)

证明上一结论:由二叉树的特点可知,除了

证明上一结论:由二叉树的特点可知,除了根结点外,所有的结点都是由一

个分支引出来的,因此分支数为A=n-1,而二叉树中的分支都是由度为

A=n-1,

而二叉树中的分支都是由度为1和度为2

的结点发出的,因此有A=n1+2*n2,于是

A=n1+2*n2,

于是A=n-1=n1+2*n2,得到:n=n1+2*n2+1②

A=n-1=n1+2*n2,

得到:n=n1+2*n2+1②

得到:n=n1+2*n2+1②

由①与②可得:

由①与②可得:n0=n2+1

由①与②可得:

n0=n2+1

则该二叉树共有几个结点

7.

某二叉树有

5

个度为

2

的结点和

3

个度为

1

的结点,

二叉树性质:终端结点(叶子节点)个数

n0 

= 

度为

2

的节点(有

2

个孩子)

个数

n2 + 1 

n0 = n2 + 1

所以本题有:叶子节点个数 ,

所以本题有:叶子节点个数

= 5 + 1 = 6

度为

1

的结点个数 ,

的结点个数

= 3

度为

2

的结点个数 ,

的结点个数

= 5

所以总个数

所以总个数 = 6 + 3 + 5 = 14

所以总个数

= 6 + 3 + 5 = 14

2对任何一棵二叉树

T

,如果其终端结点数为

n0

,度为

2

的结点数为

n2

,则

n0 

= n2 + 1 

故叶子结点数(即度为

0

的结点)为

5+1=6 

二叉树的结点数为

n=n0+n1+n2 

所以该二叉树的结点为:

5+3+6=14 

|

2024年4月7日发(作者:考潍)

1.

设一棵完全二叉树共有

699

个结点,则在该二叉树中的叶子结点数?

1

根据

二叉树的第

i

层至多有

2^(i − 1)

个结点;深度为

k

的二叉树至多有

2^k − 1

个结点;

个结点(根结点的深度为

1

这个性质:

这个性质:

因为

2^9-1 < 699 < 2^10-1 ,

所以这个完全二叉树的深度是

10

,前

9

层是一个满

二叉树,

二叉树,

这样的话,前九层的结点就有

这样的话,

前九层的结点就有

2^9-1=511

个;而第九层的结点数是

个;

而第九层的结点数是

2^(9-1)=256 

所以第十层的叶子结点数是

699-511=188

个;

个;

现在来算第九层的叶子结点个数。

现在来算第九层的叶子结点个数。

由于第十层的叶子结点是从第九层延伸的,所以应该去掉第九层中还有子树的结

点。因为第十层有

188

个,所以应该去掉第九层中的

188/2=94

个;

个;

所以,第九层的叶子结点个数是256-94=162,加上第十层有

256-94=162

,加上第十层有188个,最后结果

是350个

2

完全二叉树:若二叉树中最多只有最下面两层的结点的度可以小于

2

,并且最

下面一层的结点(叶结点)

下面一层的结点

(叶结点)都依次排列在该层最左边的位置上,

(叶结点)

都依次排列在该层最左边的位置上,这样的二叉树为

都依次排列在该层最左边的位置上,

这样的二叉树为

完全二叉树。

完全二叉树。

比如图:

比如图:

完全二叉树除叶结点层外的所有结点数(叶结点层以上所有结点数)为奇数,

此题中,

699

是奇数,叶结点层以上的所有结点数为保证是奇数,则叶结点数必

是偶数,这样我们可以立即选出答案为

B

如果完全二叉树的叶结点都排满了,则是满二叉树,

如果完全二叉树的叶结点都排满了,

则是满二叉树,易得满二叉树的叶结点数是

其以上所有层结点数

+1

比如图:

比如图:

此题的其实是一棵满二叉树,我们根据以上性质,699+1=700,

699+1=700

,700/2=350,即

700/2=350

,即

叶结点数为350,叶结点层以上所有结点数为

350

,叶结点层以上所有结点数为350-1=349。

350-1=349

3

完全二叉树中,只存在度为

2

的结点和度为

0

的结点,而二叉树的性质中有一条是:

n0=n2+1

n0

指度为

0

的结点,即叶子结点,

n2

指度为

2

的结点,所以

2n2+1=699 n2=349

n0=350 

2.

在一棵二叉树上第

5

层的结点数最多是多少

一棵二叉树,如果每个结点都是是满的,那么会满足

2^(k-1)1

所以第

5

层至多有

2^(5-1)=16

个结点!

个结点!

3.

在深度为

5

的满二叉树中,叶子结点的个数为

答案是

16 ~ 

叶子结点就是没有后件的结点

~ 

说白了

~ 

就是二叉树的最后一层

~ 

深度为

K

的二叉树

~ 

最多有

2^k-1

个结点

~ 

最多有

2^(k-1)

个结点

~ 

所以此题

~ 

最多有

2^5-1=31

个结点

~ 

最多有

2^(5-1)=16

个叶子结点

~ 

4.

某二叉树中度为

2

的结点有

18

个,则该二叉树中有几个叶子结点?

结点的度是指树中每个结点具有的子树个数或者说是后继结点数。

题中的度为

2

是说具有的

2

个子树的结点;

个子树的结点;

二叉树有个性质:二叉树上叶子结点数等于度为

2

的结点数加

1

5.

在深度为

7

的满二叉树中,度为

2

的结点个数为多少,

就是第一层只有一个节点,他有两个子节点,第二层有两个节点,他们也都有两个子节点

就是第一层只有一个节点,他有两个子节点,第二层有两个节点,他们也都有两个子节点

以此类推,所以到第

6

层,就有

2

5

次方个节点,他们都有两个子节点

次方个节点,他们都有两个子节点

最后第

7

层都没有子节点了。因为是深度为

7

的。

的。

所以就是

1+2+4+8+16+32

2

深度为

1

的时候有

0

深度为

2

的时候有

1

深度为

3

的时候有

3

深度为

4

的时候有

7

.... 

深度为

n

的时候有(

2

n-1

次方减

1

)个

)个

6.

一棵二叉树中共有

70

个叶子结点与

80

个度为

1

的结点,则该二叉树中的总结点

数为?

假设

n

表示二叉树的所有结点数,

n0

表示度为

0

的结点

(

叶子结点

)

n1

表示度

1

的结点,

n2

表示度为

2

的结点,由二叉树的性质有:

的结点,由二叉树的性质有:

n0 = n2 + 1 

已知

n0 = 70

n2 = n0 -1 = 69 

n = n0 + n1 + n2 

= 70 + 80 + 69 

= 219

总结点数 n=70+80+70-1=219

总结点数

n=70+80+70-1=219

2解:对任一二叉树

解:对任一

二叉树,如果其叶子结点

,如果其

叶子结点为n0,度为

n0

,度为1的结点数为n1,度为

n1,

度为2的结

点数为n2,则

n2

,则n0=n2+1;

然后由

然后由n=n0+n1+n2①即可得出。(n

n=n0+n1+n2①即可得出。

(n为结点总数)

为结点总数

)

证明上一结论:由二叉树的特点可知,除了

证明上一结论:由二叉树的特点可知,除了根结点外,所有的结点都是由一

个分支引出来的,因此分支数为A=n-1,而二叉树中的分支都是由度为

A=n-1,

而二叉树中的分支都是由度为1和度为2

的结点发出的,因此有A=n1+2*n2,于是

A=n1+2*n2,

于是A=n-1=n1+2*n2,得到:n=n1+2*n2+1②

A=n-1=n1+2*n2,

得到:n=n1+2*n2+1②

得到:n=n1+2*n2+1②

由①与②可得:

由①与②可得:n0=n2+1

由①与②可得:

n0=n2+1

则该二叉树共有几个结点

7.

某二叉树有

5

个度为

2

的结点和

3

个度为

1

的结点,

二叉树性质:终端结点(叶子节点)个数

n0 

= 

度为

2

的节点(有

2

个孩子)

个数

n2 + 1 

n0 = n2 + 1

所以本题有:叶子节点个数 ,

所以本题有:叶子节点个数

= 5 + 1 = 6

度为

1

的结点个数 ,

的结点个数

= 3

度为

2

的结点个数 ,

的结点个数

= 5

所以总个数

所以总个数 = 6 + 3 + 5 = 14

所以总个数

= 6 + 3 + 5 = 14

2对任何一棵二叉树

T

,如果其终端结点数为

n0

,度为

2

的结点数为

n2

,则

n0 

= n2 + 1 

故叶子结点数(即度为

0

的结点)为

5+1=6 

二叉树的结点数为

n=n0+n1+n2 

所以该二叉树的结点为:

5+3+6=14 

|

发布评论

评论列表 (0)

  1. 暂无评论