二叉排序(搜索)树

二叉排序(搜索)树

Scroll Down

二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。

定义

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

  1. 若左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 左、右子树也分别为二叉排序树;
  4. 没有键值相等的节点。

代码如下:

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BST<T extends Comparable<? super T>> {
    private Node<T> root;

    public BST() {
    }

    public void put(T item) {
        root = this.put(root, item);
    }

    /**
     * 创建二叉排序树
     *
     * @param x
     * @param item
     * @return
     */
    private Node<T> put(Node<T> x, T item) {
        if (x == null) {
            x = new Node<T>(item, null, null);
            return x;
        }
        if (item.compareTo(x.item) < 0) {
            x.left = put(x.left, item);
        } else {
            x.right = put(x.right, item);
        }
        return x;
    }

    public Node<T> search(T s) {
        return search(this.root, s);
    }

    /**
     * 递归查找要查找的值
     *
     * @param x
     * @param s
     * @return
     */
    private Node<T> search(Node<T> x, T s) {
        if (x == null) {
            return null;
        }
        if (s.compareTo(x.item) < 0) {
            return search(x.left, s);
        } else if (s.compareTo(x.item) > 0) {
            return search(x.right, s);
        }
        return x;
    }

    public Node<T> min() {
        return min(root);
    }

    /**
     * 查找二叉排序树中值最小的结点
     *
     * @param x
     * @return
     */
    private Node<T> min(Node<T> x) {
        if (x.left == null) {
            return x;
        }
        return min(x.left);
    }

    public Node<T> max() {
        return max(root);
    }

    /**
     * 查找二叉排序树中值最大的结点
     *
     * @param x
     * @return
     */
    private Node<T> max(Node<T> x) {
        if (x.right == null) {
            return x;
        }
        return max(x.right);
    }

    public void deleteMin() {
        root = deleteMin(root);
    }

    /**
     * 删除二叉排序树中的最小结点
     *
     * @param x
     * @return
     */
    private Node<T> deleteMin(Node<T> x) {
        if (x.left == null) {
            return x.right;
        }
        x.left = deleteMin(x.left);
        return x;
    }

    public void delete(T s) {
        root = delete(root, s);
    }

    /**
     * 删除结点,要分三种情况考虑
     * 1、如果要删除的结点是叶子结点,那么直接将它删去
     * 2、如果要删除的结点有左或右孩子,那么将此节点删去,用它的左或右孩子取代它
     * 3、如果要删除的结点有左右孩子,那么先查找此节点的右子树的最小结点,将此结点赋给要删除的那个节点,之后将此节点删除,然后将原来要删除结点的左右孩子分别赋给此节点;
     *
     * @param x
     * @param s
     * @return
     */
    private Node<T> delete(Node<T> x, T s) {
        if (x == null) {
            return null;
        }
        if (s.compareTo(x.item) < 0) {
            x.left = delete(x.left, s);
        } else if (s.compareTo(x.item) > 0) {
            x.right = delete(x.right, s);
        } else {
            if (x.left == null) {
                return x.right;
            }
            if (x.right == null) {
                return x.left;
            }
            Node<T> temp = x;
            x = min(temp.right);
            x.right = deleteMin(temp.right);
            x.left = temp.left;
        }
        return x;
    }

    public void preOrderTraverse() {
        this.preOrderTraverse(root);
    }

    /**
     * 前序遍历树
     *
     * @param x
     */
    private void preOrderTraverse(Node<T> x) {
        if (x != null) {
            System.out.print(x.item + " ");
            preOrderTraverse(x.left);
            preOrderTraverse(x.right);
        }
    }

    public void inOrderTraverse() {
        this.inOrderTraverse(root);
    }

    /**
     * 中序遍历树
     *
     * @param x
     */
    private void inOrderTraverse(Node<T> x) {
        if (x != null) {
            inOrderTraverse(x.left);
            System.out.print(x.item + " ");
            inOrderTraverse(x.right);
        }
    }

    public void postOrderTraverse() {
        this.postOrderTraverse(root);
    }

    /**
     * 后序遍历树
     *
     * @param x
     */
    private void postOrderTraverse(Node<T> x) {
        if (x != null) {
            postOrderTraverse(x.left);
            postOrderTraverse(x.right);
            System.out.print(x.item + " ");
        }
    }

    /**
     * 层次遍历树
     */
    public void leverTraverse() {
        Queue<Node<T>> queue = new LinkedList<Node<T>>();
        Node<T> pnode = null;
        queue.offer(root);
        while (!queue.isEmpty()) {
            pnode = queue.poll();
            System.out.print(pnode.item + " ");
            if (pnode.left != null) {
                queue.offer(pnode.left);
            }
            if (pnode.right != null) {
                queue.offer(pnode.right);
            }
        }
        System.out.println();
    }

    /**
     * 二叉排序树的树节点
     */
    private class Node<T> {
        T item;
        Node<T> left;
        Node<T> right;

        public Node(T item, Node<T> left, Node<T> right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "数据为:" + this.item + " " + "左孩子为:" + (this.left == null ? "null" : this.left.item) + " " +
                    "右孩子为:" + (this.right == null ? "null" : this.right.item);
        }
    }
}



总结

优点:插入,删除操作的时间复杂度都是O(log(n))级的,即经过O(log(n))时间搜索到了需插入和删除的节点的位置,后经过O(1)级的时间就可以直接插入和删除,比有序顺序表的插入和删除O(n)(查找O(log(n)),移动节点O(n))快,而和无序顺序表插入O(1),删除O(n)比,因为是有序的,所以查找的速度要快很多。
缺点:二叉排序树的构造不止和最终节点的顺序有关,还和节点插入和删除的顺序有关,在某些特殊的情况下,树的高度可以等于节点的数量,于是查找的时间复杂度就退化成了O(n)了,相当也无序顺序表的查找

支付宝 微信