二叉树：

image-20211027183453896.png

  • 二叉树结构

image-20211027183848791.png

1.二分搜索树的应用：（二分搜索类似二分查找，需要已排序）

文件目录，数据有序存储等。
image.png

2.二分树的特性：

image.png
虽然二分树通常情况下不包含重复元素，但是在进行add和remove时，只要改变判断条件，就可以包括重复元素。要注意和 堆进行区分，堆实际上借鉴了二分树的思想。不同的是，二分树的排序特性为从左叶子节点向右递增。而堆是从 root 向下递减（分为最大堆和最小堆）

3.具体实现

  1. // 父节点的值，大于左子节点，大于右子节点
  2. public class BTS <E extends Comparable<E>>{
  3.     // 使用链表实现
  4.     private class Node{
  5.         public E value;
  6.         public Node left;
  7.         public Node right;
  9.           public Node(E e){
  10.             value = e;
  11.             left = null;
  12.             right = null;
  13.         }
  14.     }
  15.     private Node root;
  16.     private int size;
  18.     public BTS(){
  19.         root = null;
  20.         size = 0;
  21.     }
  23.     // 加入元素，放到适合的位置
  24.     public Node add(Node node, E e){
  25.         // 如果为空二叉树，则为头节点
  26.         if(Node == null){
  27.                size++;
  28.             return new Node(e);
  29.         }
  30.         // 否则进行遍历
  31.         if(e.compareTo(node.e) < 0){
  32.             node.left = add(node.left, e);
  33.         }else{
  34.             node.right = add(node.right, e);
  35.         }
  36.         return node;
  37.     }
  39.     // 使用非递归方法
  40.     private Node add2(Node node, E e) {
  41.         while (node != null) {
  42.             if (e.compareTo(node.e) < 0) {
  43.                 node = node.left;
  44.             } else if (e.compareTo(node.e) > 0) {
  45.                 node = node.right;
  46.             }
  47.         }
  48.         node = new Node(e);
  49.         return node;
  50.     }
  51. }

image.png
（1）假设根节点为 null ，满足

（2） 看递归过程 :

  1. // 在 node == null 时
  2. 看上去是 node  被赋值为 new Node(e), 实际上 return 时 ，node会消失，不存在于 node.left中。
  3. 因为 node = new Node(e) 仅在if( node == null) 时生效， node.left 并不会改变
  4. 就好比 你传入 （2,3）
  5. 然后 3 递减， 当 小于1时，2 == 1，但是局部赋值不能改变传递进来的参数.
  6. 因此只有返回值才能保证变化。

1.删除节点：

假如为叶子节点：直接删除
假如有左子节点或者右子节点，直接上移
假如左子节点和右子节点同时存在，看以下情况：
前缀：寻找当前节点的左子树中最大的那个节点
后缀：寻找当前节点的右子树中最小的那个节点
image.png

  1. // 删除某节点下，value = e 的节点，左子树中最大的那个提上来作为新的父节点
  2. private Node remove(Node node, E e){
  3.     // 遍历到叶子节点后
  4.     if(node == null) return null;
  5.     // 遍历直到 node.e == value
  6.     // 假如
  7.     if(e.compareTo(node.e) < 0){
  8.         node.left = remove(node.left, e);
  9.         return node;
  10.     }else if(e.compareTo(node.e) > 0) {
  11.         node.right = remove(node.right, e);
  12.         return node;
  13.     }else{
  14.         // 假如当前节点左子树为空,即为叶子节点
  15.         if (node.left == null) {
  16.                 Node accessor = node.right;
  17.                 node.right = null;
  18.                 size--;
  19.                 return accessor;
  20.             // 假如当前右子树为空，为叶子节点
  21.             } else if (node.right == null) {
  22.                 Node accessor = node.left;
  23.                 node.left = null;
  24.                 size--;
  25.                 return accessor;
  26.             }
  27.         // 假如当前节点节点为满
  28.             Node accessor = Maximum(node.right);
  29.             accessor.left = node.left;
  30.             accessor.right = removeMin(node.right);
  31.             node.left = null;
  32.             node.right = null;
  33.             return accessor;
  34.     }
  35. }
  38. // 删除某节点后，右子树中最小的那个提上来作为新的父节点
  39.  private Node remove2(Node node, E e) {
  40.         if (node == null) {
  41.             return null;
  42.         }
  43.         if (e.compareTo(node.e) < 0) {
  44.             node.left = remove2(node.left, e);
  45.             return node;
  46.         } else if (e.compareTo(node.e) > 0) {
  47.             node.right = remove2(node.right, e);
  48.             return node;
  49.         } else {
  50.             if (node.left == null) {
  51.                 Node accessor = node.right;
  52.                 node.right = null;
  53.                 size--;
  54.                 return accessor;
  55.             } else if (node.right == null) {
  56.                 Node accessor = node.left;
  57.                 node.left = null;
  58.                 size--;
  59.                 return accessor;
  60.             }
  61.             Node accessor = Maximum(node.left);
  62.             accessor.right = node.right;
  63.             accessor.left = removeMax(node.left);
  64.             node.left = null;
  65.             node.right = null;
  66.             return accessor;
  67.         }
  68.     }
  • 获取Node 节点下最小值与最大值 ```java // 获取 Node 节点下最大值 public Node Maximum(Node node){ if(node.right == null)
    1.   return node;
    return Maximum(node.right); }

// 获取 Node 节点下最大值 public Node Minimum(Node node){ if(node.left == null) return node; return Minimum(node.left); }


- 删除 Node 节点下最小值与最大值
```java
public Node removeMax(Node node){
    // 由于左子节点小于node
    if(node.right == null){
        Node nodeleft = node.left;
        node.left = null;
        size--;
        return nodeleft;
    }
    node.right = removeMax(node.right);
    return node;
}

public Node removeMin(Node node){
    // 由于左子节点小于node
    if(node.left == null){
        Node nodeleft = node.right;
        node.right = null;
        size--;
        return noderight;
    }
    node.right = removeMax(node.right);
    return node;
}

2.遍历方式：

  • 前序遍历（preOrder）

    // 前序遍历
public void preOrder(Node node){
  // 当 node == null，则直接返回
  if(node == null){
      return;
  }
  System.out.println(node.e);
  preOrder(node.left);
  preOrder(node.right);
}

  • 中序遍历（inOrder）

    // 中序遍历
public voud inOrder(Node node){
  if(node == null){
      return;
  }
  inOrder(node.left);
  System.out.println(node.e);
  inOrder(node.right);
}

  • 后序遍历 (postOrder)

    // 后序遍历
public void postOrder(Node node){
  if(node == null){
      return;
  }
  postOrder(node.left);
  postOrder(node.right);
  System.out.println(node.e);
}

  • 层序遍历 (levelOrder)

    // 层序遍历
public void levelOrder(){
  Queue<Integer> queue = new Queue<>();
  // 使用队列,每次都把 Node 加入，然后进行遍历
  queue.add(root);
  while(!queue.isEnpty()){
      Node cur = queue.remove();
      System.out.println(cur);
      if(cur.left != null){
          queue.add(cur.left);
      }else if(cur.right != null){
          queue.add(cur.right);
      }
  }
}