数据结构之二叉树

本文是数据结构和算法之美学习笔记

树

树这种数据结构跟现实中的树很像，里面的每个元素叫做结点，用连线把相邻的结点连接起来，相邻结点之间的关系叫父子关系。

比如下图中，A结点是B的父节点，B是A的子结点，B,C,D是兄弟结点，E没有父节点称为根节点，没有子节点的结点是叶子结点，G,H,I,H,K,L都是叶子结点。

树一般用三个概念可以描述，高度，深度，层

高度：结点到叶子结点的最长路径（边数）

深度：根结点到这个结点所经历的边的个数

层数：结点的深度加1

树的高度：根结点的高度

高度是从下往上度量，就像数楼层。深度从上往下度量，就像往水下看，层数是跟深度类似，不过是以1为起点。

二叉树

顾名思义，就是每个结点最多有两个叉，也就是两个叶子结点，左子节点和右子节点，左右子节点只要存在一个就行。

如果除了叶子结点外的每个结点都有左右两个子节点，这种二叉树叫“满二叉树”

如果叶子结点都在最底下两层，最后一层的叶子结点都靠左排列，并且除了最后一层，其他的结点个数都要达到最大，这种二叉树叫做“完全二叉树”

如何存储一个二叉树？

可以使用基于指针的或者引用的二叉链式存储法，或者基于数组的顺序存储法。

链式存储法：

每个结点有三个字段，其中一个缓存数据，剩下的两个分别是指向左右子节点的指针。我们只要找到根节点就能通过左右指针找到所有数据。

顺序存储法：

把根节点存储在下标为i=1的位置，左子节点存储在下标为2 i=2的位置，右子节点存储在2 i+1=3的位置，以此类推。

对于顺序存储法来说，完全二叉树更能节省内存。

二叉树的遍历

经典的方法有三种：前序遍历，中序遍历，后序遍历。前中后表示的是结点本身打印的顺序。

• 前序遍历是对于树种的任意结点来说，先打印这个结点，然后在打印它的左子树，最后打印它的右子树
• 中序遍历是对于树种任意结点来说，先打印它的左子树，在打印它本身，最后打印它的右子树
• 后序遍历是先对于树种任意结点来说，先打印左子树，在打印右子树，最后打印结点本身。

其实二叉树的前中后遍历就是一个递归的过程。比如前序遍历，就是先打印跟结点，然后递归打印左子树，在递归打印右子树。

遍历方法：

void preOrder(Node* root) {
  if (root == null) return;
  System.out.print(root.data);
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  System.out.print(root.data);
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  System.out.print(root.data);
}

还有一种按层遍历，这个需要用到队列

public void levelOrder(BinaryTree tree) {
    // 利用队列先入先出的特点来实现按层遍历
    LinkedList<BinaryTree> linkedList = new LinkedList<>();
    // 记录当前遍历到哪个结点
    BinaryTree currentNode = tree;
    // 根节点入队
    linkedList.add(currentNode);
    // 从队列中弹出各结点数据，直到队列为空，遍历完毕
    while (linkedList.size()>0){
    // 弹出队首元素(当前结点)，打印其数据，并依次将其左右子节点入队
      currentNode = linkedList.poll();
      System.out.print(currentNode.data+" -> ");
      if (currentNode.left!=null) {
        linkedList.add(currentNode.left);
      }
      if (currentNode.right!=null) {
        linkedList.add(currentNode.right);
      }
    }
  }

二叉树最大的特点就是支持动态数据集合的快速插入、删除、查找操作。

二叉查找树（Binary Search Tree）

二叉查找树也叫二叉搜索树，是为了实现快速查找而生的，不过它不仅支持快速查找还支持快速插入删除。

二叉查找树规定：在树中的任意一个节点，其左子树的每个值都小于这个节点的值，右子树的每个值都大于这个节点的值。

1.二叉查找树的查找

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

代码：

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;
    }
  }
}

2.二叉查找树的插入

新插入的数据一般都是在叶子节点，我们需要从根节点开始依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就把数据插到右子节点的位置，如果不为空就在递归遍历右子树，直到找到插入的位置。如果要插入的数据比节点数值小并且节点的左子树为空，就插入，不为空，递归遍历左子树直到找到插入位置。

代码：

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.二叉查找树的删除

删除操作比插入和查找操作麻烦一点

（1）如果要删除的节点是叶子节点，我们只需更新父节点指向删除节点的指针为null

（2）如果要删除的节点只有一个子节点，我们只需要更新其父节点中指向要删除节点的指针，让它指向要删除的节点的子节点就好了

（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;
}

中序遍历二叉树可以输出有序的数据序列，并且非常高效。因此二叉查找树也叫做二叉排序树。

如果数据中有重复的数据怎么办？

（1）二叉查找树中不仅会存储一个数据，我们可以通过链表和支持动态扩容的数组，把相同的值存储在同一个节点上。

（2）插入数据的时候，如果碰到一个节点的值与要插入的数据的值相同，就将这个要插入的数据放到这个节点的右子树，也就是把它当成大于这个节点的值来处理。

当要查找数据的时候，遇到值相同的节点，不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点停止。

删除数据的时候，先找到每个要删除的节点，然后按照前面的删除方法依次删除。