【数据结构】——二叉树的种类及性质

二叉树：每个结点的子节点最多有2个，二叉树的子节点分为左节点和右节点

满二叉树

一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树

除了叶子结点外每一个结点都有左右子叶，且叶子结点都处在最底层

完全二叉树

在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。

设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布

平衡二叉树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树

• 如下图右面所示，以1为根结点，它的左子树为3层，右子树为1层，它们的高度差的绝对值等于2，已经超过了1，所以右面的不是平衡二叉树

二叉搜索树

• 它是一颗空树，或者
• 若它的左子树不为空，左子树上所有结点的值均小于根结点
• 若它的右子树不为空，右子树上所有结点的值均大于根结点
• 每个子树均为二叉搜索树

红黑树

• 根结点为黑色
• 叶子结点为黑色
• 每个结点要么是红色，要么是黑色
• 每个红色结点的两个子节点一定是黑色
• 任意一个结点到每个叶子结点的路径，都包含相同数量的黑色结点

霍夫曼树

霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树

所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度

如上图， 带权路径长度为（100*0 + 40*1 + 19*2 + 21*2 + 60*1 + 28*2 + 32*2 + 11*3 + 17*3）

二叉树的性质

• 二叉树的第 i 层至多有 2^(i －1)个结点
• 深度为 k 的二叉树至多有 (2^k) - 1个结点(k >=1)
• 对任何一棵二叉树, 如果其叶子结点数为n0，度为2的结点数为 n2，则n0＝n2＋1
•  具有n个结点的完全二叉树的深度为，（[]表示向下取整）

• 对于具有n个节点的完全二叉树，如果用顺序方式存储，对二叉树中的所有节点从0开始到n-1进行编号，则对于任意的下标为i的节点，有：

        （1）若 i=0，则它是根节点，若 i>0，则它的父节点的下标为 i / 2

        （2）若 2i <= n，则下标为 i 的节点的左节点的下标为 2i，否则下标为 i 的节点没有左节点

        （3）若 2i+1 <= n ，则下标为 i 的节点的右节点的下标为 2i+1，否则下标为 i 的节点没有右节点