⼆叉树选择题
本篇文章是初阶二叉树的收尾，旨在进一步加深对于二叉树性质的理解，祝你有一个愉快的学习之旅！
💡 ⼆叉树性质
1）对任何⼀棵⼆叉树, 如果度为 0 其叶结点个数为 n0 , 度为 2 的分⽀结点个数为 n2 ,则有 n0 = n2 + 1
证明上述性质：
假设⼀个⼆叉树有 a 个度为2的节点， b 个度为1的节点， c 个叶节点，则这个⼆叉树的边数是 2a+b
另⼀⽅⾯，由于共有 a+b+c 个节点，所以边数等于 a+b+c-1 结合上⾯两个公式：
2a+b = a+b+c-1 ，即： a = c-1
根据⼆叉树的性质，完成以下选择题：
-
某⼆叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该⼆叉树中的叶⼦结点数为（ ）
A 不存在这样的⼆叉树 B 200 C 198 D 199
根据公式：叶子节点数=度为2的节点个数+1 ，所以为200个，选择B
2.在具有 2n 个结点的完全⼆叉树中，叶⼦结点个数为（ ）
A n B n+1 C n-1 D n/2
节点的个数为度为2的节点个数+度为1的节点个数+叶子节点个数，又因为度为2的节点个数=叶子节点个数-1，综合起来看，需要做出讨论的是度为1的节点个数，因为总结点的个数为2n，是一个偶数，所以不能为奇数，所以为n,选A
3.⼀棵完全⼆叉树的结点数位为531个，那么这棵树的⾼度为（ ）
A 11 B 10 C 8 D 12
💡 ⼆叉树性质
根据满⼆叉树的特点可知：
1）若规定根结点的层数为 1 ，则⼀棵⾮空⼆叉树的第i层上最多有 2i−1 个结点
2）若规定根结点的层数为 1 ，则深度为 h 的⼆叉树的最⼤结点数是 2h-1
3）若规定根结点的层数为 1 ，具有 n 个结点的满⼆叉树的深度 ( log 以2为底， n+1 为对数)
根据以上性质 列出公式 2h-1=531,再来根据对数函数公式，求得h=10
4.⼀个具有767个结点的完全⼆叉树，其叶⼦结点个数为（）
A 383 B 384 C 385 D 386
以第二题为基准，2*叶子节点个数+度为1节点个数-1=767，根据奇偶性来看，度为1的节点个数为0，所以选B
链式⼆叉树遍历选择题
1.某完全⼆叉树按层次输出（同⼀层从左到右）的序列为 ABCDEFGH 。该完全⼆叉树的前序序列为（ ）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
答案：A
2.⼆叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则⼆叉树根结点为 （）
A E
B F
C G
D H
答案：A
3.设⼀课⼆叉树的中序遍历序列：badce，后序遍历序列：bdeca，则⼆叉树前序遍历序列为。
A adbce
B decab
C debac
D abcde
第三题根据后序遍历确定根节点为a,再来看中序遍历，确定左右子树，确定b为左子树，发现ce位置不同，所以再来看后序遍历，确定c为右子树的根节点，所以选D
4.某⼆叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同⼀层从左到右） 的序列 为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF
跟上面题目一样的思路后序遍历确定根节点，中序遍历确定左右子树
所以选择A
列 为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF
跟上面题目一样的思路后序遍历确定根节点，中序遍历确定左右子树
所以选择A
本篇文章虽然有一些短，但是相信看到这里也会是收获满满的
