【数据结构】你真的学会了二叉树了吗，来做一做二叉树的算法题及选择题

1. 二叉树算法题

1.1 单值二叉树

https://leetcode.cn/problems/univalued-binary-tree/description/

1.2 相同的树

https://leetcode.cn/problems/same-tree/description/

基于上一道OJ题，拓展学习

对称二叉树：https://leetcode.cn/problems/symmetric-tree/description/

1.3 另一棵树的子树

https://leetcode.cn/problems/subtree-of-another-tree/description/

1.4 二叉树的遍历

前序遍历：

https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

中序遍历：

https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

后序遍历：

https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

1.5 二叉树的构建及遍历

https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef

2. 二叉树选择题

💡 二叉树性质

对任何一棵二叉树, 如果度为$0$其叶结点个数为$n_0$, 度为$2$的分支结点个数为 $n_2$ ,则有$n_0=n_2+1$

证明上述性质：

假设一个二叉树有a个度为2的节点，b个度为1的节点，c个叶节点，则这个二叉树的边数是2a+b

另一方面，由于共有a+b+c个节点，所以边数等于a+b+c-1

结合上面两个公式：

2a+b = a+b+c-1 ，即：a = c-1

根据二叉树的性质，完成以下选择题：

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199
2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2
3.一棵完全二叉树的结点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 124.一个具有767个结点的完全二叉树，其叶子结点个数为（）
A 383
B 384
C 385
D 386

答案：
1.B
2.A
3.B
4.B

链式二叉树遍历选择题

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为（）
A E
B F
C G
D H
3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde
4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF

答案：

1.A
2.A
3.D
4.A

3. 结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。

也可以点点关注，避免以后找不到我哦！

Crossoads主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的动力！