二叉树学习总结

1 什么是二叉树？

在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。

2 树的几个相识概念“深度”、“高度”、“层”。

3 什么是满二叉树和完全二叉树？

满二叉树：如果一棵二叉树只有度为 0 的结点和度为 2 的结点，并且度为 0 的结点在同一层上，则这棵二叉树为满二叉树。除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做满二叉树。如下图。

 完全二叉树：深度为 k，有 n 个结点的二叉树当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 到 n 的结点一一对应时，称为完全二叉树。也就是说叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。

4 二叉树的应用。

二叉树通常作为数据结构应用，典型用法是对节点定义一个标记函数，将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树和二叉堆，并应用于高效率的搜索和排序。

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

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

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

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

如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。

6 什么是二叉查找树？

二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。

二叉查找树的特殊结构：二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

7 如何实现二叉查找树的查找、插入、删除操作？

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

代码：

public class BinarySearchTree {  private Node tree;
  public Node find(int data) {    Node p = tree;    while (p != null) {      if (data < p.data) p = p.left;      else if (data > p.data) p = p.right;      else return p;    }    return null;  }
  public static class Node {    private int data;    private Node left;    private Node right;
    public Node(int data) {      this.data = data;    }  }}

插入：从根节点开始，依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

代码：

public void insert(int data) {  if (tree == null) {    tree = new Node(data);    return;  }
  Node p = tree;  while (p != null) {    if (data > p.data) {      if (p.right == null) {        p.right = new Node(data);        return;      }      p = p.right;    } else { // data < p.data      if (p.left == null) {        p.left = new Node(data);        return;      }      p = p.left;    }  }}

删除：分 3 种情况

l 1 如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。

l 2 如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。

l 3 如果要删除的节点有两个子节点，我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。

public void delete(int data) {  Node p = tree; // p指向要删除的节点，初始化指向根节点  Node pp = null; // pp记录的是p的父节点  while (p != null && p.data != data) {    pp = p;    if (data > p.data) p = p.right;    else p = p.left;  }  if (p == null) return; // 没有找到
  // 要删除的节点有两个子节点  if (p.left != null && p.right != null) { // 查找右子树中最小节点    Node minP = p.right;    Node minPP = p; // minPP表示minP的父节点    while (minP.left != null) {      minPP = minP;      minP = minP.left;    }    p.data = minP.data; // 将minP的数据替换到p中    p = minP; // 下面就变成了删除minP了    pp = minPP;  }
  // 删除节点是叶子节点或者仅有一个子节点  Node child; // p的子节点  if (p.left != null) child = p.left;  else if (p.right != null) child = p.right;  else child = null;
  if (pp == null) tree = child; // 删除的是根节点  else if (pp.left == p) pp.left = child;  else pp.right = child;}

8 什么是“平衡二叉查找树”？

二叉树中任意一个节点的左右子树的高度相差不能大于 1。平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

9 如何定义一棵“红黑树”？

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

n 根节点是黑色的；每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；

n 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；

n 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。

10 什么是红黑树？

漫画版讲解红黑树完整版https://zhuanlan.zhihu.com/p/143396578