数据结构之二叉树

由于二叉树的内容比较多，故分开来记录。

二叉树(Binary Tree)

二叉树是一个有序的树，且每一个结点最多只能拥有两个子结点。二叉树结点的子树有左、右子树区分，不能随意颠倒。即使只有一个子树的情况，也要说明是左、右子树。二叉树具有递归性质。

满二叉树

满二叉树(Full Binary Tree)是一棵高度为 h 的，且有 2^k+1 - 1 个结点的二叉树。即是每一层的结点都是满的。满二叉树是一棵特殊的完全二叉树。

完全二叉树

完全二叉树(Complete Binary Tree)除了最一层，每一层都是满的，最后一层可以有 1 至 2^h个结点，并且最后一层所有结点都靠近左边。

最优二叉树

最优二叉树也称为哈夫曼树，它是一类带权路径长度最短的树。路径是从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。

平衡二叉树

任意结点的左右子树深度相差不超过1，每结点的平衡度只能为 -1，0 或 1。

二叉树的性质

二叉树的第 i 层上最多有 2^i-1个结点(i≥1)。
深度为 k 的二叉树最多有 2^k - 1 个结点(k≥1)。
对任意非空二叉树，其叶结点为 n₀，度为 2 的结点为 n₂，n₀ = n₂ + 1。
具有 n 个结点的完全二叉树，其深度为 ⌊log₂n⌋ + 1。
对一颗 n 个结点的完全二叉树，其结点依次自上而下，自左至右编号，则对于任一结点 i (1 <= i <= n)，则有：
- 若 i 的双亲为 ⌊i/2⌋（i > 1）
- 若 2i > n，则结点 i 为叶子结点；否则，其左子结点为 2i
- 若 2i + 1 > n，则结点 i 无右子结点；否则，其右子结点为 2i + 1

二叉树的遍历

设二叉树的链表存储结构的结点类型定义如下:

typeof struct BiTnode {
  int data;
  struct BiTnode *lchild, *rchild;
}BiTnode, *BiTree;

二叉树的先序遍历(根->左->右)

void PreOrder(BiTree root) {
  if (root != NULL) {
    printf("%d", root->data);   /* 根结点 */
    PreOrder(root->lchild);     /* 先序遍历根结点的左子树 */
    PreOrder(root->rchild);     /* 先序遍历根结点的右子树 */
  }
}

二叉树的中序遍历(左->根->右)

void InOrder(BiTree root) {
  if (root != NULL) {
    InOrder(root->lchild);      /* 中序遍历根结点的左子树 */
    printf("%d", root->data);   /* 根结点 */
    InOrder(root->rchild);      /* 中序遍历根结点的右子树 */
  }
}

二叉树的后序遍历(左->右->根)

void PostOrder(BiTree root) {
  if (root != NULL) {
    PostOrder(root->lchild);    /* 后序遍历根结点的左子树 */
    PostOrder(root->rchild);    /* 后序遍历根结点的右子树 */
    printf("%d", root->data);   /* 根结点 */
  }
}

二叉查找树(Binary Search Tree)

二叉查找树(BST)又叫二叉排序树(sorted binary tree)。他们允许快速查找，添加和删除数据项。他们的数据项按照顺序排列，在二叉树中若左，右子树非空，则有：

左子树上所有的结点的值均小于根结点的值。
右子树上所有的结点的值均大于根结点的值。
左右子树也是二叉查找树。

二叉查找树的查找

struct node *search(struct node* root, int key) {
  if (root == NULL || root->key == key) {
    return root;
  }
  if (root->key < key) {
    return search(root->right, key);
  } else {
    return search(root->left, key);
  }
}

二叉查找树的插入

struct node *newNode(int item) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

struct node *insert(struct node* node, int key) {
  if (node == NULL) return newNode(key);
  if (key < node->key) {
    node->left = insert(node->left, key);
  } else if (key > node->key) {
    node->right = insert(node->right, key);
  }
  return node;
}

二叉查找树的删除

二叉查找树的删除有三种情况：

删除的结点没有子结点(叶结点)
删除的结点有一个子结点
删除的结点有两个子结点

// 返回一个非空二叉查找树的最小结点
struct node *minValueNode(struct node* node) {
  struct node* current = node;
  while(current->left != NULL) {
    current = current->left;
  }
  return left;
}

struct node* deleteNode(struct node* root, int key) {
  if (root == NULL) return root;
  if (key < root->key) {
    root->left = deleteNode(root->left, key);
  } else if (key > root->key) {
    root->right = deleteNode(root->right, key);
  } else {
    /* 结点没有子结点或者只有一个子结点 */
    if (root->left == NULL) {
      struct node *temp = root->right;
      free(root);
      return temp;
    } else if (root->right == NULL) {
      struct node *temp = root->left;
      free(root);
      return temp;
    }
    /* 结点有两个子结点 */
    struct node* temp = minValueNode(root->right);
    root->key = temp->key;
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

平衡二叉树(Self-balancing Tree)

自平衡二叉搜索树，又叫高度平衡二叉搜索树。AVL 树是第一个被发现的平衡二叉树，所以是最具有代表性的平衡二叉树。在 AVL 树中，左，右子树的高度差最多为 1，且左右子树也均为平衡二叉树。在任何时候，如果他们的高度差超过 1，则会重新进行操作以恢复平衡。在 AVL 树中，每一个维护平衡的结点都叫平衡因子(balance factor/BF)。

Balance factor = heightOfLeftSubtree - heightOfRightSubtree

平衡二叉树的旋转

在 AVL 树，每一步的操作例如插入，删除我们都需要检测 AVL 树中每个结点的平衡因子。如果每个平衡因子都是平衡的，我们结束操作，否则我们使其平衡。我们使用旋转操作来移动左，右子树使树平衡。旋转操作有四种情况：

                            / Left Rotation  (LL Rotation)
            Single Rotation
          /                 \ Right Rotation (RR Rotation)
Rotations
          \                 / Left Right Rotation (LR Rotation)
            Double Rotation
                            \ Right Left Rotation (RL Rotation)