二叉树

二叉树的前序遍历、中序遍历、后序遍历。

img

代码实现：

void preOrder(Node* root) {
  if (root == null) return;
  print root // 此处为伪代码，表示打印 root 节点
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root // 此处为伪代码，表示打印 root 节点
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root // 此处为伪代码，表示打印 root 节点
}

二叉查找树（BST)

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

img

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

1. 取根节点，如果是，返回；
2. 若比根节点小，就在左子树中递归查找；
3. 若比根节点大，就在右子树中递归查找；

img

代码实现：

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

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

从根节点开始，依次比较要插入的数据和节点的大小关系

分为几种情况：

1. <u>插入数据比当前节点大</u>（前提1），且节点右子树为空，则新数据直接当前节点的右子节点；
2. 若不为空，就再递归遍历右子树，直到遇到情况1；
3. <u>插入数据比当前节点小</u>（前提2），且节点左子树为空，则新数据直接当前节点的左子节点；
4. 若不为空，就再递归遍历左子树，直到遇到情况3；

img

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) {           //情况1
       p->right = new Node(data);
        return;
      }
      p = p->right;                     //情况2
    } else {                            // data < p.data
      if (p->left == null) {            //情况3
        p->left = new Node(data);
        return;
      }
      p = p->left;                      //情况4
    }
  }
}

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

三种情况（都是要父节点）：

1. 该节点没有子节点，只需将父节点指向该节点的指针<u>置NULL</u>；
2. 该节点只有一个子节点，只需将父节点指向该节点的指针<u>指向该节点的子节点</u>；
3. 该节点有两个子节点：1.找到<u>该节点右子树中的最小节点</u> 2.<u>替换</u>到该待删除的节点 3.再<u>删除掉这个最小节点</u>（有右节点也不怕，用情况2）。

img

代码实现：

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; // 没有找到
    
    //p永远都是要待删除的节点//
    //////////////////////////////
    //情况3：要删除的节点有两个子节点//
    //////////////////////////////
  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 了，留给下面的情况2或者情况1*//
    pp = minPP;
  }

    ////////////////////////////
    //情况2：删除节点仅有一个子节点//
    ////////////////////////////
  Node* child; // p 的子节点
  if (p->left != null) child = p->left;
  else if (p->right != null) child = p->right;
  else child = null;    
    
    //////////////////////////////
    //情况1：删除节点是叶子节点//
    //////////////////////////////
  if (pp == null) tree = child; // 删除的是根节点
  else if (pp->left == p) pp->left = child;
  else pp->right = child;
}

4.二叉查找树的其他操作

中序遍历二叉查找树，就可以输出有序的数据序列，时间复杂度是O(n)。因此，二叉查找树也叫作二叉排序树。

5.支持重复数据的二叉查找树

插入：

在找插入位置时，如果碰到一个节点的值，与待插入数据的值相同，那就把这个待插入的值当做大于这个节点的值来处理。即：

if (data >= p->data)

img

查找：

遇到相同的节点，并不停止查找，而是继续在右子树中查找，直到遇到叶子节点才停止。把所有值相同的节点都找出来。

img

删除：

先查找，再用前面的方法依次删除。

img

6.二叉查找树的时间复杂度

不稳定。

最坏变成链表，查找变为O(n)；

最好是完全二叉树，查找、删除、插入都为O(height)；

3.红黑树

红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树再说数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似log n，所以他是近似平衡的，插入、删除、查找操作的时间复杂度都是O(log n)。

因为红黑树是一种性能非常稳定的二叉查找树，所以在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到它。但如果没有现成的代码可以支持，那么我们更倾向用跳表来实现。