数据结构——二叉树

发表于 更新于 本文字数： 1.9k 阅读时长 ≈ 7 分钟

树形结构的基本概念：

  • 根节点：
  • 度：结点拥有的直接子节点数称为结点的度
  • 叶子：度为0的结点称为叶子
  • 树的度：所有结点的度中的最大值
  • 孩子：一个结点的直接子结点称为它的孩子
  • 双亲：一个节点的父节点就是他的双亲节点
  • 深度：树中最大的结点层

二叉树

一个结点的直接子节点最多只能有两个，并且有左右之分，次序不能随意颠倒。

满二叉树

  1. 所有分支结点的度为２；
  2. 所有叶子结点只能分布在最下层上；
  3. 同样深度的二叉树中，满二叉树的结点数最多，叶子结点数最多；
  • 满二叉树的深度：log2(n+1)；

完全二叉树（只有最底下一层不满的满二叉树）

  1. 二叉树从根结点出发，按着层次从左到右遍历，第i个结点的位置与满二叉树中对应结点位置完全相同；
  2. 所有叶子结点只能出现在最下两层；
  3. 若结点度为1，则该结点只有左子树，不存在只有右子树的情况；
  4. 结点分配先左后右；

遍历二叉树

  1. 先序遍历：先访问根节点；先序遍历左子树；先序遍历右子树；
  2. 中序遍历：中序遍历左子树；访问根节点；中序遍历右子树；
  3. 后序遍历：后序遍历左子树；后序遍历右子树；访问根节点；

先序遍历——前缀表示——波兰式
后序遍历——后缀表示——逆波兰式

线索二叉树

增加节点的左右指针一个标志位：是否为叶子节点。当为叶子节点的时候，其左右指针指向其某种遍历的前驱、后驱；否则指向其左右子树。

  • 线索：指向节点前驱与后驱的指针叫做线索
  • 线索化：以某种次序遍历使其变为线索二叉树的过程

二叉排序树

二叉排序树又称二叉查找树，亦称二叉搜索树，它主要用于查找。 它或者是一棵空树；或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

中序遍历二叉排序树可得到其有序序列，讲一个无序序列变为二叉排序树是一个排序过程。

平衡二叉树

平衡二叉树又被称为AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，由它可以生成平衡二叉搜索树，查找效率会更高。构造与调整方法平衡二叉树的常用算法有红黑树、AVL、Treap等。最小二叉平衡树的节点的公式如下F(n)=F(n-1)+F(n-2)+1这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

  • 平衡因子：左子树的深度减去右子树的深度
    平衡二叉树的平衡因子只会是-1，0，1
  • 在结点的左子树的左子树插入元素,LL 插入；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 /**
 * 右旋（顺时针旋转）
 *
 * @param node 失衡结点
 * @return 旋转后根节点
 */
private TreeNode<T> rightRotate(TreeNode<T> node) {
    // 将失衡结点的左子树赋给一个临时结点，也就是将A的左子树B 赋给新的结点
    TreeNode<T> newRoot = node.leftChild;
    // 将B 被右子树BR 挂在A 的左子树上
    node.leftChild = newRoot.rightChild;
    // B 的右子树为失衡的结点即A
    newRoot.rightChild = node;
    // 结点A 的高度为左右子树高度最大值加1
    node.height = getMax(height(node.leftChild), height(node.rightChild)) + 1;
    // 结点B 的高度为左右子树高度最大值加1
    newRoot.height = getMax(height(newRoot.leftChild), newRoot.height) + 1;
    // 返回根节点
    return newRoot;
}
  • 在结点的左子树的右子树插入元素,LR 插入；
  • 在结点的右子树的左子树插入元素,RL 插入；
  • 在结点的右子树的右子树插入元素,RR 插入。
  1. 如上所述的第3步，当插入元素后导致左边高，右边低，并且为4和3的平衡因子符号相同，则右旋。
  2. 如上所诉的第5步，当插入节点9后，导致以4为根的树右边高，左边低，4和7的平衡因子符号相同，则左旋
  3. 如上所述的第7步，当插入节点10后，导致以9为根的树右边高，左边低，由于9和11的平衡因子符号不同（也就是根和他的右孩子的平衡因子符号不同）不能进行左旋，正确操作：需要先右旋在左旋，要让根和根的右孩子平衡因子符号相同。
  4. 第4种旋转和3相反，当左边高于右边的话，且根和他的左孩子，平衡因子符号不同，需要先左旋再右旋

哈夫曼树

哈夫曼树也称最优二叉树，它是带权路径长度最小的二叉树。

哈夫曼树的构造规则为：
(1) 将w1、w2、…、wn看成是有n 棵树的集合(每棵树仅有一个结点)；
(2) 在集合中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从集合中删除选取的两棵树，并将新树加入集合；
(4)重复(2)、(3)步，直到集合中只剩一棵树为止，该树即为所求得的哈夫曼树。

为了使得到的哈夫曼树的结构尽量唯一，通常规定生成的哈夫曼树中每个结点的左子树根结点的权小于等于右子树根结点的权。

哈夫曼编码

电文是以二进制的0、1序列传送的，每个字符对应一个二进制编码，为了缩短电文的总长度，采用不等长编码方式，构造哈夫曼树，
将每个字符的出现频率作为字符结点的权值赋予叶子结点，每个分支结点的左右分支分别用0和1编码，从树根结点到每个叶子结点的路径上

B 树、B+ 树

这里的B树，也就是英文中的B-Tree，一个 m 阶的B树满足以下条件：

  1. 每个结点至多拥有m棵子树；
  2. 根结点至少拥有两颗子树（存在子树的情况下）；
  3. 除了根结点以外，其余每个分支结点至少拥有 m/2 棵子树；
  4. 所有的叶结点都在同一层上；
  5. 有 k 棵子树的分支结点则存在 k-1 个关键码，关键码按照递增次序进行排列；
  6. 关键字数量需要满足ceil(m/2)-1 <= n <= m-1；

红黑树RBTree

  1. 每个节点要么是黑的，要么是红的
  2. 根节点是黑的
  3. 叶节点是黑的
  4. 如果一个节点是红的，他的两个儿子节点都是黑的
  5. 对于任一节点而言，其到叶节点树尾端NIL指针的每一条路径都包含相同数目的黑节点
  6. 新插入的节点总是设为红色的