Binary Search Tree

Binary Search Tree

• 必须有可比较性
• 左孩子比根节点小，右孩子比根节点大
• 如果想包含重复的元素的话，只需要定义：左子树小于等于节点；或者右子树大于等于节点

实现

public class BST<E> extends Comparable<E> {
	private class Node {
		public E e;
		public Node left, right;
	}

	public Node(E e) {
		this.e = e;
		this.left = null;
		this.right = null;
	}

	private Node root;
	private int size;

	public BST() {
		this.root = null;
		this.size = 0;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}
	// 添加元素
	public void add(E e) {
		// if(root == null) {
		// 	root = new Node(e);
		// 	size ++;
		// } else {
		// 	add(root,e);
		// }
		
		// 修改之后
		root = add(root,e);
	}

	// 向以node为根的二分搜索树种插入元素E
	private Node add(Node node, E e) {
		// if(root.e.equals(e)) {
		// 	return;
		// } else if(e.compareTo(node.e) < 0 && node.left == null) {
		// 	node.left = new Node(e);
		// 	size ++;
		// 	return;
		// } else if(e.compareTo(node.e) > 0 && node.right == null) {
		// 	node.right = new Node(e);
		// 	size ++;
		// 	return;
		// }
		// if (e.compareTo(node.e) < 0) {
		// 	add(node.left,e);
		// } else {
		// 	add(node.right,e);
		// }

		// 当我们递归到null的时候就一定要创建一个节点
		if(node == null) {
			size ++;
			return new Node(e);
		}
		if (e.compareTo(node.e) < 0) {
			node.left = add(node.left,e);
		} else {
			node.right = add(node.right,e);
		}
		return node;
	}

	public boolean contains(E e) {
		return contains(root, e);
	}

	private boolean contains(Node node, e) {
		if(node == null) {
			return false;
		}

		if(e.compareTo(node.e)){
			return true;
		}

		if (e.compareTo(node.e) < 0) {
			return contains(node.left,e);
		} else {
			return contains(node.right,e);
		}
	}

	// 二叉树的前序遍历
	public void preOrder() {
		preOrder(root);
	}

	private void preOrder(Node node) {
		if(node == null) {
			return;
		}
		System.out.println(node.e);
		preOreder(node.left);
		preOreder(node.right);
	}

	// 顺序的排列的
	public void inOrder() {
		inOrder(root);
	}

	public void inOrder(Node node) {
		if(node == null) {
			return;
		}
		preOreder(node.left);
		System.out.println(node.e);
		preOreder(node.right);
	}

	// 后序遍历
	// 为二分搜索释放内存
	public void postOrder() {
		postOrder(root);
	}

	private void postOrder(Node node) {
		if(node == null) {
			return;
		}
		preOreder(node.left);
		preOreder(node.right);
		System.out.println(node.e);
	}
    // 最小值
    public E minimum() {
        if(size == 0){
            throw new IllegalArgumentException("BST is empty");
        }
        return minimum(root).e;
    }
    // 返回已node为根的二分搜索树的最小值所在的节点
    private Node minimum(Node node) {
        if(node.left == null) {
            return node;
        }
        return minimum(node.left);
    }
    
    // 最大值	
    public E maximum() {
        if(size == 0){
            throw new IllegalArgumentException("BST is empty");
        }
        return maximum(root).e;
    }
    // 返回已node为根的二分搜索树的最小值所在的节点
    private Node maximum(Node node) {
        if(node.right == null) {
            return node;
        }
        return minimum(node.right);
    }
    // 从树中删除最小值
    public E removeMin() {
        E ret = minimum();
        // 返回删除后新的根节点
        root = removeMin(root);
        return ret;
    }
    // 返回删除节点后新的二分搜索树
    private Node removeMin(Node node) {
        
        if(node.left == null) {
            Node rightNode = node.rigth;
            node.right = null;
            size --;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }
    
     // 从树中删除最小值
    public E removeMax() {
        E ret = maximum();
        // 返回删除后新的根节点
        root = removeMax(root);
        return ret;
    }
    // 返回删除节点后新的二分搜索树
    private Node removeMax(Node node) {
        
        if(node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size --;
            return leftNode;
        }
        node.right = removeMin(node.right);
        return node;
    }
    
    // 删除某一结点
    public void remove(E e) {
        root = remove(root);
    }
    private Node remove(Node node, E e) {
        if(node == null) {
            return null;
        }
        if(e.compareTo(node.e) < 0) {
            node.left = remove(node.left,e);
            return node;
        } else if(e.compareTo(node.e) > 0) {
            node.right = remove(node.right,e);
            return node;
        } else {
            // 3种情况
            if(node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }
            if(node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }
            // 当左右子树都不为空的时候
            Node successor = minimum(node.right);
            // 这里我们进行了删除size进行了减操作
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right = null;
            return successor;
        }
    }
}

前序遍历非递归实现

// 首先将节点压入栈中，如果栈不为空这弹出栈顶元素，并将左右孩子压入栈中，首先压入左孩子然后压入右孩子
public void preOrder() {
  Stack<Node> stack = new Stack<>();
  stack.push(root);
  if(!stack.isEmpty()){
    Node node = stack.pop();
    System.out.println(node.e);
    if(node.left != null){
      stack.push(node.left);
    }
    if(node.right != null){
      stack.push(node.right);
    }
  }
}

层序遍历实现

// 利用队列
public void levelOrder() {
  Queue<Node> q = new LinkedList<>();
  q.add(root);
  while(!q.isEmpty()) {
    Node cur = q.remove();
    System.out.println(cur.e);
    if(cur.left != null) {
      q.add(cur.left);
    }
    if(cur.right != null) {
      q.add(cur.right);
    }
  }
}