二叉查找树 Java 代码

2016-08-01 11:23:31 暂无评论阳光倾城算法与数据结构 699

二叉查找树 java 代码

public class BSTNode {
      private int value;
      private BSTNode left;
      private BSTNode right;
      public BSTNode(int value) {
            this.value = value;
            left = null;
            right = null;
      }
public boolean add(int value) {
            if (value == this.value)
                  return false;

                  if (left == null) {
                        left = new BSTNode(value);
                        return true;
                  } else
                        return left.add(value);
            } else if (value > this.value) {
                  if (right == null) {
                        right = new BSTNode(value);
                        return true;
                  } else
                        return right.add(value);
            }
            return false;
      }
public boolean search(int value) {
            if (value == this.value)
                  return true;

                  if (left == null)
                        return false;
                  else
                        return left.search(value);
            } else if (value > this.value) {
                  if (right == null)
                        return false;
                  else
                        return right.search(value);
            }
            return false;
      }
public boolean remove(int value, BSTNode parent) {

                  if (left != null)
                        return left.remove(value, this);
                  else
                        return false;
            } else if (value > this.value) {
                  if (right != null)
                        return right.remove(value, this);
                  else
                        return false;
            } else {
                  if (left != null && right != null) {
                        this.value = right.minValue();
                        right.remove(this.value, this);
                  } else if (parent.left == this) {
                        parent.left = (left != null) ? left : right;
                  } else if (parent.right == this) {
                        parent.right = (left != null) ? left : right;
                  }
                  return true;
            }
      }
      public int minValue() {
            if (left == null)
                  return value;
            else
                  return left.minValue();
      }
}
public class BinarySearchTree {
      private BSTNode root;
      public BinarySearchTree() {
            root = null;
      }
public boolean add(int value) {
            if (root == null) {
                  root = new BSTNode(value);
                  return true;
            } else
                  return root.add(value);
      }
public boolean search(int value) {
            if (root == null)
                  return false;
            else
                  return root.search(value);
      }
public boolean remove(int value) {
            if (root == null)
                  return false;
            else {
                  if (root.getValue() == value) {
                        BSTNode auxRoot = new BSTNode(0);
                        auxRoot.setLeftChild(root);
                        boolean result = root.remove(value, auxRoot);
                        root = auxRoot.getLeft();
                        return result;
                  } else {
                        return root.remove(value, null);
                  }
            }
      }
}