二叉树知识点

1.霍夫曼编码-最优生成树

这位作者写的很清楚，生成的带权路径长度最小

哈夫曼编码详解——图解真能看了秒懂_已知字符集abcdef,若各字符出现的次数_Young_IT的博客-CSDN博客

2.满二叉树与完全二叉树

满二叉树是指每层数量是pow(2,n-1)个节点，总节点数是pow(2,n)-1;

而完全二叉树是指最后一层不一定满，但是节点数要全部靠左边。

3.平衡搜索树

平衡搜索树任意节点的左右子树高度差小于等于1，nullptr的节点高度为0，

当插入不平衡时，需要左旋和右旋，所谓旋转就是重新设根节点，如果左子树多，就把根节点的左节点当成新的根节点，即右旋，反之，右子树太高，就把右节点当成新的根节点，即左旋。

上述情况适用于根节点两个节点一直往左或者往右，但还有一种情况，即先左后右或者先右后左，这时需要两次旋转才行，因为根节点即中间值是最下面的那个。

 

 

如上图所示，如果树是这样的形式，先将最下面两个进行左旋得到中间形态，再右旋得到平衡树。 

这篇文章介绍的很详细

平衡二叉树 —— 如何优雅的进行旋转 - 知乎 (zhihu.com)

 4.节点的度

一颗二叉树节点的度为0，1，2，度即左右边的个数

牛客题：

评论区说度为0的节点比度为2的节点多1，

也可以用二叉树画出来：

牛客题2：

答案写的很明确了，节点个数比分支多1. 

5.b树，b+树，b-树

 b树删除问题

b-树，非终端节点，关键字

6.线索二叉树

 线索二叉树的线索数就是空指针域的个数

如图所示，它的线索数就是4，即节点个数为n时，有n-1个边，每个节点都是满的话应该有2*n条边，空指针域就是2*n-(n-1)=n+1，即线索数为n+1。 

7.森林转二叉树