文章目录

二叉搜索树代码实现

二叉搜索树

性质:

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也分别为二叉查找树；没有键值相等的节点。

代码实现

import java.util.ArrayList; import java.util.List; /** * @author jssd * @create 2019-05-25 11:08 */ public class BST<E extends Comparable<E>> { //BST 内部节点 private class Node { E data; Node left, right; public Node(E data) { this.data = data; left = null; right = null; } } //BST树的大小 private int size; //根元素 private Node root; public BST() { root = null; size = 0; } // 取得大小 public int getSize() { return size; } //判断是否为空 public boolean isEmpty() { return size == 0; } // 添加元素 public void add(E data) { root = add(root, data); } private Node add(Node root, E data) { if (root == null) { size++; return new Node(data); } if (data.compareTo(root.data) < 0) root.left = add(root.left, data); else root.right = add(root.right, data); return root; } // 取得最小元素 public E getMin() { if (isEmpty()) throw new IllegalArgumentException("BST is empty"); else return getMin(root).data; } private Node getMin(Node node) { if (node.left == null) return node; return getMin(node.left); } // 取得最大元素 public E getMax() { if (isEmpty()) throw new IllegalArgumentException("BST is empty"); else return getMax(root).data; } private Node getMax(Node node) { if (node.right == null) { return node; } return getMax(node.right); } // 删除最小元素, 并将删除的元素返回 public E removeMin() { E miniData = getMin(); root = removeMin(root); return miniData; } private Node removeMin(Node node) { if (node.left == null) { Node nodeRight = node.right; node.right = null; size--; return nodeRight; } return removeMin(node.left); } //删除最大元素, 并将删除元素返回 public E removeMax() { E data = getMax(); root = removeMax(root); return data; } private Node removeMax(Node node) { if (node.right == null) { Node nodeLeft = node.left; node.left = null; size--; return nodeLeft; } return removeMax(node.right); } //删除元素E public void remove(E data) { if (isEmpty()) throw new IllegalArgumentException("thi BST is empty"); root = remove(root, data); } private Node remove(Node node, E data) { if (data.compareTo(node.data) < 0) { node.left = remove(node.left, data); } else if (data.compareTo(node.data) > 0) { node.right = remove(node.right, data); } else { //如果左子树为空 if (node.left == null) { size--; return node.right; } //如果右子树为空 if (node.right == null) { size--; return node.left; } // 都不为空 Node minNode = getMin(node.right); minNode.right = removeMin(node.right); minNode.left = node.left; node = minNode; } return node; } // 是否包含某个元素 public boolean contains(E e) { if (isEmpty()) throw new IllegalArgumentException("the BST is Empty"); return contains(root, e); } private boolean contains(Node node, E e) { if (node == null) { return false; } if (e.compareTo(node.data) < 0) { return contains(node.left, e); } else if (e.compareTo(node.data) > 0) { return contains(node.right, e); } else { return true; } } //先序遍历 public void preOrder() { preOrder(root); } private void preOrder(Node node) { if (node == null) return; System.out.println(node.data); preOrder(node.left); preOrder(node.right); } //中序遍历 public void inOrder() { inOrder(root); } private void inOrder(Node node) { if (node == null) { return; } inOrder(node.left); System.out.println(node.data); inOrder(node.right); } //后序遍历 public void postOrder() { postOrder(root); } private void postOrder(Node node) { if (node == null) { return; } postOrder(node.left); postOrder(node.right); System.out.println(node.data); } //层次遍历 public void levelOrder() { List<Node> list = new ArrayList<>(); list.add(root); while (!list.isEmpty()) { Node temp = list.remove(0); System.out.println(temp.data); if (temp.left != null) list.add(temp.left); if (temp.right != null) list.add(temp.right); } } }