408第一季 - 数据结构 - 树与二叉树

树

神秘公式

可以看见啊，每个节点都有一个向上的根的，只有顶点A没有，所以我们就有个公式

n = e + 1  n是节点个数，e的边的个数

度的概念

B度为2，D度为3，孩子个数成为节点的度

分支节点

分支节点 = 非叶子节点 = 非终端节点

度为0是孩子节点，中专结点

森林

把下面的图看成整体就是森林

性质

所有结点的度数之和（就是边的数量）加1 就是结点数

后面有一些性质不用记了，看见题目时现推一下就知道了

比如：

假设度是4

很容易就看出来了，bro

做题

1

80+30+2+10 +1 = 123个结点

就剩下度为0的没有了，度为0就是叶子节点

123-20-10-1-10= 82个叶子节点

b

2

第一个圈起来的树，结点比边多1个，第二个数也是，第三个树也是

可以看见这个森林，有n条边和n+3个节点，有3颗树

题目里是15条边，和 15加10个结点，所以啊，有10颗树

c

二叉树

完全二叉树

完全二叉树右边可以少

 也就是说

最大两层，就是倒数第二层的7，和最后一层的8，9，10，11，12

二叉树的性质

性质1

 叶子节点等于度为2的节点+1 ， 怎么推的？

这里就是度为0的节点 加 度为1的节点 加 度为2的节点 等于 度为1的边 加 度为2的边（边有2个所以乘2） + 1，这里n1和n2加起来其实就是边的个数

做题

1

叽里咕噜说什么呢，其实就是满二叉树

a

2

 运用公式，可以看见叶子节点和度为2的节点有奇数个，题目里的2n就在很明确的告诉我们，总数是偶数个，因此啊，度为1的必定是奇数个

以后就可以记住了，偶数个节点啊，一定会有奇数个度为1的节点

C选择这里有说有偶数个（2m）度为1的，所以错了

3

n2可以替换为n0-1，然后n1要么是1要么是0

然后0和1都试一下，第一个解不出来，所以第二个是正确的

这里如果我们知道上面的公式就是偶数个节点啊，一定会有奇数个度为1的节点，就会知道这里一定不会为0

性质2和3

推的话就是用等比啊，没什么东西，但用的频率极高

做题

1

完全二叉树吗，有意思，来吧

注意倒数第一和倒数第二层才会出现叶子节点，又问的最多，所以第六层的8个是倒数第二层的叶子节点

所以 1(第一层）+ 2(第二层）+4(第三层）+8(第四层）+16(第五层）+32(第六层）+（32-8）*2等于111个节点

c

2

 

注意倒数第一和倒数第二层才会出现叶子节点，又问的最少，所以第六层的8个是倒数第一层的叶子节点

所以 1(第一层）+ 2(第二层）+4(第三层）+8(第四层）+16(第五层）+8(第六层）等于39个节点

a

性质4

这里第一个公式有个向上取整的符号，比如3.1就是4

第二个公式是向下取整的符号

以后的折半查找判断树要用的

存储结构

首先要是完全二叉树，因为这样就可以防止还原不唯一

然后就是链式，你得看这左边的表还原成唯一的二叉树就行了，链式存储可以不连续

做题

1

 一般人可能会这样做

但老头这招太狠了

题目里有个任意，也就是说任何树都可以，所以应该这样做（也就是最大化31个节点）

这时候就有人说了，byd那至少是干什么的，至少的意思就是说，什么32个40个存储空间就没有必要了，所以31个刚刚好

记住看见老头的任意门，要考虑最坏的情况