Skip to content

二叉树

· 11 min

二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

编号 2 的二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做 满二叉树。

编号 3 的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做 完全二叉树。

如何表示（或者存储）一棵二叉树？#

一种是基于指针或者引用的二叉 链式存储法，一种是基于数组的 顺序存储法。

链式存储法。从图中你应该可以很清楚地看到，每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。

基于数组的顺序存储法。我们把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 * i = 2 的位置，右子节点存储在 2 * i + 1 = 3 的位置。以此类推，B 节点的左子节点存储在 2 * i = 2 * 2 = 4 的位置，右子节点存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。

刚刚举的例子是一棵完全二叉树，所以仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间。可以看举的下面这个例子

所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

二叉树的遍历#

经典的方法有三种，前序遍历、中序遍历和后序遍历：

// 先序
function preOrder(root) {
  if (root == null) return;
  console.log(root.value);
  preOrder(root.left);
  preOrder(root.right);
}


// 中序
function inOrder(root) {
  if (root == null) return;
  inOrder(root.left);
  console.log(root.value);
  inOrder(root.right);
}


// 后序
function postOrder(root) {
  if (root == null) return;
  postOrder(root.left);
  postOrder(root.right);
  console.log(root.value);
}

二叉查找树#

也叫二叉搜索树，二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。 二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

1. 二叉查找树的查找操作#

我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}
function searchBST(root, val) {
  while (root !== null && val !== root.val) {
    root = val < root.val ? root.left : root.right;
  }
  return root;
}

2. 二叉查找树的插入操作#

如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}
function insertBST(root, val) {
  if (root === null) {
    root = new TreeNode(val);
    return root;
  }
  while (root != null) {
    if (val > root.val) {
      if (root.right == null) {
        root.right = new TreeNode(val);
        return root;
      }
      root = root.right;
    } else {
      if (root.left == null) {
        root.left = new TreeNode(val);
        return root;
      }
      root = root.left;
    }
  }
}

3. 二叉查找树的删除操作#

针对要删除节点的子节点个数的不同，我们需要分三种情况来处理。

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}
function deleteNode(root, key) {
  if (!root) return null;
  if (root.val > key) {
    root.left = deleteNode(root.left, key);
    return root;
  }
  if (root.val < key) {
    root.right = deleteNode(root.right, key);
    return root;
  }
  if (root.val === key) {
    if (!root.left && !root.right) {
      return null;
    }
    if (!root.right) {
      return root.left;
    }
    if (!root.left) {
      return root.right;
    }
    let p = root.right;
    while (p.left) {
      p = p.left;
    }
    root.right = deleteNode(root.right, p.val);
    p.right = root.right;
    p.left = root.left;
    return p;
  }
};

平衡二叉查找树#

平衡二叉树：二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看，完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。

平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。最先被发明的平衡二叉查找树是AVL树，它严格符合平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过 1，是一种高度平衡的二叉查找树。 发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。 所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

红黑树#

红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树。红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：


> cd ..