1. 搜索

  1. public class BinarySearchTree {
  2.     private Node tree;
  3.     public Node find(int data) {
  4.         Node p = tree;
  5.         while (p != null) {
  6.             if (data < p.data) p = p.left;
  7.             else if (data > p.data) p = p.right;
  8.             else return p;
  9.         }
  10.         return null;
  11.     }
  12.     public static class Node {
  13.         private int data;
  14.         private Node left;
  15.         private Node right;
  16.         public Node(int data) {
  17.             this.data = data;
  18.         }
  19.     }
  20. }

2. 插入节点

  1. public void insert(int data) {
  2.     if (tree == null) {
  3.         tree = new Node(data);
  4.         return;
  5.     }
  6.     Node p = tree;
  7.     while (p != null) {
  8.         if (data > p.data) {
  9.             if (p.right == null) {
  10.                 p.right = new Node(data);
  11.                 return;
  12.             }
  13.             p = p.right;
  14.         } else { // data < p.data
  15.             if (p.left == null) {
  16.                 p.left = new Node(data);
  17.                 return;
  18.             }
  19.             p = p.left;
  20.         }
  21.     }
  22. }

3.删除节点

  1. public void delete(int data) {
  2.     Node p = tree; // p指向要删除的节点，初始化指向根节点
  3.     Node pp = null; // pp记录的是p的父节点
  4.     while (p != null && p.data != data) {
  5.         pp = p;
  6.         if (data > p.data) p = p.right;
  7.         else p = p.left;
  8.     }
  9.     if (p == null) return; // 没有找到
  10.     // 要删除的节点有两个子节点
  11.     if (p.left != null && p.right != null) { // 查找右子树中最小节点
  12.         Node minP = p.right;
  13.         Node minPP = p; // minPP表示minP的父节点
  14.         while (minP.left != null) {
  15.             minPP = minP;
  16.             minP = minP.left;
  17.         }
  18.         p.data = minP.data; // 将minP的数据替换到p中
  19.         p = minP; // 下面就变成了删除minP了
  20.         pp = minPP;
  21.     }
  22.     // 删除节点是叶子节点或者仅有一个子节点
  23.     Node child; // p的子节点
  24.     if (p.left != null) child = p.left;
  25.     else if (p.right != null) child = p.right;
  26.     else child = null;
  28.     if (pp == null) tree = child; // 删除的是根节点
  29.     else if (pp.left == p) pp.left = child;
  30.     else pp.right = child;
  31. }