二叉排序树BST

概念

• BTS: 对于任何一个非叶子节点，左子节点都比当前节点小，右子节点都比当前节点大
• 平衡二叉树和满二叉树，完全二叉树是没关系的，极端情况就是一个链表

删除

1. 删叶子节点
   1. parent.left = null
   2. parent.right = null
2. 删只有一颗子树的节点
   1. parent.left = targetNode.left
   2. parent.left = targetNode.right
   3. parent.right = targetNode.left
   4. parent.right = targetNode.right
3. 删有两颗子树的节点
   1. 找到targetNode右子树的最小节点 或者左子树最大
   2. 赋值给targetNode,删除

public class BinarySortTree {

  public static void main(String[] args) {
    int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
    Tree tree = new Tree();
    for (int i : arr) {
      tree.add(new Node(i));
    }
    tree.delNode(2);
    tree.delNode(5);
    tree.delNode(9);
    tree.delNode(12);
    tree.delNode(7);
    tree.delNode(3);
    tree.delNode(10);
    tree.delNode(1);


    tree.infixOrder();
  }
}

class Tree {

  Node root;
  // 查找
  Node search(int value) {
    if (root == null) {
      return null;
    } else {
      return this.root.search(value);
    }
  }
  // 删除右子树最左节点
  int deleteRightMin(Node node) {
    Node temp = node;
    while (temp.left != null) {
      temp = node.left;
    }
    delNode(temp.value);
    return temp.value;
  }
  // 删除节点方法
  void delNode(int value) {
    if (root.left == null && root.right == null && value == root.value) {
      root = null;
      return;
    }
    if (root == null) {
      return;
    } else {
      Node targetNode = search(value);
      if (targetNode == null) {
        return;
      }
      // 是叶子节点
      if (targetNode.left == null && targetNode.right == null) {
        // 是左子树
        if (targetNode.parent.left != null && targetNode.parent.left == targetNode) {
          targetNode.parent.left = null;
        }
        // 是右子树
        if (targetNode.parent.right != null && targetNode.parent.right == targetNode) {
          targetNode.parent.right = null;
        }
      } else if (targetNode.left != null && targetNode.right != null) { // 要删的节点有两个子树
        int minVal = deleteRightMin(targetNode.right);
        targetNode.value = minVal;
      } else { // 要删的节点有一个子树
        if (targetNode.left != null) { // 子树是左子树
          if (targetNode.parent != null) {
            if (targetNode.parent.left == targetNode) {
              targetNode.parent.left = targetNode.left;
            }
          } else {
            root = targetNode.left;
          }
        } else { // 子树是右子树
          if (targetNode.parent != null) {

            if (targetNode.parent.left == targetNode) {
              targetNode.parent.left = targetNode.right;
            } else {
              targetNode.parent.right = targetNode.right;
            }
          } else {
            root = targetNode.right;
          }
        }
      }
    }
  }

  void add(Node node) {
    if (root == null) {
      root = node;
    } else {
      root.add(node);
    }
  }

  public void infixOrder() {
    if (root != null) {
      root.infixOrder();
    }
  }
}

class Node {

  int value;
  Node left;
  Node right;
  Node parent;

  public Node(int value) {
    this.value = value;
  }
  // 查找
  Node search(int value) {
    if (value == this.value) {
      return this;
    } else {
      if (value < this.value) {
        if (this.left == null) {
          return null;
        }
        return this.left.search(value);
      } else {
        if (this.right == null) {
          return null;
        }
        return this.right.search(value);
      }
    }
  }

  // 添加节点
  void add(Node node) {
    if (node == null) {
      return;
    }
    if (node.value < this.value) {
      if (this.left == null) {
        this.left = node;
        this.left.parent = this;
      } else {
        this.left.add(node);
      }
    } else {
      if (this.right == null) {
        this.right = node;
        this.right.parent = this;
      } else {
        this.right.add(node);
      }
    }
  }
  // 中序遍历
  void infixOrder() {
    if (this.left != null) {
      this.left.infixOrder();
    }
    System.out.println(this.value);
    if (this.right != null) {
      this.right.infixOrder();
    }
  }

}