笔试选择题-树
做过笔试的同学应该知道，数据结构比较常考的除了栈，还有一个数据结构就是树。所以本篇文章就是用来理清树的一些简单的知识点。
树
- 树的层次：从根结点开始算，根结点是第一层，以此类推。
- 结点的度：子树的数量，说白了就是有几个分叉，例如叶子结点度为0
- 树的度：所有结点中最大的度作为树的度
- n个结点的树，边数一定是n-1
- 结点的深度是指根结点到该结点的深度，根结点代表1；结点的高度是指从最底层结点到该结点的深度
- 树的高度和深度是一样的就是根结点到最底层结点的高度和深度。
二叉树
- 满二叉树：每一层的结点数量都达到当前层的最大值。深度为k的话，则总结点数为2的k次方减1
2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(k-1) = 2^k - 1 - 完全二叉树：除了最后一层，每一层的结点数量都达到当前层的最大值。且最后一层要求结点连续。
- 二叉树第i层（i>0）的最大结点数为
2^(i-1)，即 - 二叉树深度为k，有最大结点数为
2^k - 1，也就是满二叉树的时候。
例题：10个叶子结点的二叉树，度为2的结点数？
假如n0表示度为0的结点个数，n1表示度为1的结点个数，n2表示度为2的结点个数，则二叉树的总结点数n = n0 + n1 + n2，其中n0就是叶子结点数。存在公式n0 = n2 + 1，所以度为2的结点数为9。公式证明如下：
根据结点边的贡献进行推导
一共有n个结点，则边数为n-1 = n0 + n1 + n2 - 1
n0贡献的边数为0 * n0
n1贡献的边数为1 * n1
n2贡献的边数为2 * n2
则n0 + n1 + n2 - 1 = 0 + n1 + 2 * n2
得证n0 = n2 + 1
例题：深度为k的二叉树，只有度为0和度为2的结点，则该二叉树的结点数至少为2k -1(除了第一层，每层都有两个结点，这样的结点数最少)
例题：已知一棵有 2011 个结点的树，其叶结点个数为 116 ，该树对应的二叉树中无右孩子的结点个数是1896
解析：度为2的结点：n2 = 116 - 1 = 115
结果：度为1的结点(2011 - 115 - 116) + 叶子结点(116)，即2011 - 115 = 1896
💡注意度为1的结点是没有右孩子的，具体看树是如何转二叉树的这篇文章
例题：设一棵完全二叉树中有65个结点，则该完全二叉树的深度为7
根据满二叉树性质，6层的话，顶多63个，说明为7层。同理如果是64个结点的完全二叉树的深度也为7。因为完全二叉树并没有什么公式，所以我们需要借助有公式的树，其实满二叉树也是完全二叉树
- 平衡二叉树：是一颗二叉搜索树，且任意结点的左右子树的高度差不超过
例题：高度为h的平衡二叉树的最少结点数和最大结点数。
情况一：最少结点数满足nh = nh-1 +nh-2 + 1，详见文章
情况二：最大结点数，把树看成满二叉树，这样结点数会达到最大，所以结点数为2h-1
例题：求含有20个结点的平衡二叉树的最大深度为6，求最大深度，说明要每层用的结点越少，深度越高，所以是情况一。如果求最小深度，只需把树看成满二叉树，其中4层的话顶多15个结点，说明最小为5层。