二叉树知识点

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.