笔试选择题-树

做过笔试的同学应该知道，数据结构比较常考的除了栈，还有一个数据结构就是树。所以本篇文章就是用来理清树的一些简单的知识点。

树

#度

• 树的层次：从根结点开始算，根结点是第一层，以此类推。
• 结点的度：子树的数量，说白了就是有几个分叉，例如叶子结点度为0
• 树的度：所有结点中最大的度作为树的度
• n个结点的树，所有结点的度之和为n-1
• n个结点的树，边数一定是n-1，度和边可以理解为是一样的。
• 结点的深度是指根结点到该结点的深度，根结点代表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
1
2
3
4
5
6
7

例题：深度为k的二叉树，只有度为0和度为2的结点，则该二叉树的结点数至少为2k -1(除了第一层，每层都有两个结点，这样的结点数最少)

#二叉树

• 满二叉树：每一层的结点数量都达到当前层的最大值。深度为k的话，则总结点数为2的k次方减1

  2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(k-1) = 2^k - 1
  1

• 完全二叉树：除了最后一层，每一层的结点数量都达到当前层的最大值。且最后一层要求结点连续。
• 二叉树第i层（i>0）的最大结点数为2^(i-1)，即
• 二叉树深度为k，有最大结点数为2^k - 1，也就是满二叉树的时候。

例题：设一棵完全二叉树中有65个结点，则该完全二叉树的深度为7
根据满二叉树性质，6层的话，顶多63个，说明为7层。同理如果是64个结点的完全二叉树的深度也为7。因为完全二叉树并没有什么公式，所以我们需要借助有公式的树，其实满二叉树也是完全二叉树

#二叉树遍历

例题：任意一棵二叉树的叶子结点在先序、中序、后序遍历序列中的相对次序都是相同的，因为左边的总是比右边的先遍历，变化的只是根。
原题

例题：某二叉树，其度为1的节点数为n1，度为2的节点数为n2，且先序遍历和后序遍历序
列正好相反，则此二叉树的深度为n1+1
解析：由于先序后序相同，说明该树只存在左子树或者右子树，即不存在度为2的结点。固边数=n1+n0 = n1 + 1
原题

#二叉排序树

当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。

下面内容为扩展，有时间再学

---

#哈夫曼树

要点： WPL最小的数称为哈夫曼树，或者叫最优二叉树。树不一定唯一，但最小WPL唯一

哈夫曼树思想：反复选择两个最小的元素，合并并放回原来的集合，继续选两个最小的，直到只剩下一个元素。

例题：合并果子

import java.util.PriorityQueue;
import java.util.Scanner;
public class HaFuMan {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int num = input.nextInt();
        PriorityQueue<Integer> queue = new PriorityQueue<>(num);
        for (int i = 0; i < num; i++) {
            int tmp = input.nextInt();
            queue.add(tmp);
        }
        int sum = 0;//消耗
        while(queue.size() > 1) {
            Integer a = queue.poll();
            Integer b = queue.poll();
            int tmp = a + b;
            queue.add(tmp);
            sum+=tmp;
        }
        System.out.println(sum);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

哈夫曼编码

前缀编码意义：不会产生混淆，能正常解码

例题：用二进制来编码字符串 “abcdabaa”，需要能够根据编码，解码回原来的字符串，最少需要14长的二进制字符串
各字符出现的次数：a=4, b=2, c=1,d=1，先合并cd，需要2，合并2和b，需要4，合并4和a，需要8，所以总和14。
原题

例题： 由10个数构造出的Huffman树一共有19个节点 。
两两合并，需要9次，即产生9个节点，所以总共19。

#待整理

森林转二叉树 https://www.nowcoder.com/questionTerminal/9d6c5ea438fa4ed2b0df1b0e6c29b102
二叉树转森林 https://www.nowcoder.com/test/question/done?tid=61713819&qid=372730#summary
https://www.nowcoder.com/test/question/done?tid=61212132&qid=112831#summary
b树

例题：已知一棵有 2011 个结点的树，其叶结点个数为 116 ，该树对应的二叉树中无右孩子的结点个数是1896
解析：度为2的结点：n2 = 116 - 1 = 115
结果：度为1的结点(2011 - 115 - 116) + 叶子结点(116)，即2011 - 115 = 1896
💡注意度为1的结点是没有右孩子的，具体看树是如何转二叉树的这篇文章