数据结构05-二进制排序树

二进制排序树是空树或具有以下属性的树:

如果左侧子树不为空，则左侧子树上方所有节点的键值均小于根节点的键值；如果右边的子树不为空，那么右边的子树Keyword值以上的所有节点都大于根节点;左和右子树是二叉树.

二叉排序树的搜索效率高于普通二叉树，但是添加和删除的效率较低.

public void put(E data) {
    Node<E> now = new Node<E>(data);
    if (root == null) {
        root = now;
        return;
    }
    Node<E> parent = root;
    while (parent != null) {
        //小于当前节点，就与左子树比较
        if (data.compareTo(parent.data) < 0) {
            //如果左子节点为空，那就放到左子节点
            if (parent.left == null) {
                parent.left = now;
                now.parent = parent;
                return;
                //如果左子节点不为空，那就继续比较
            } else {
                parent = parent.left;
            }
            //大于当前节点，就放与右子树比较
        } else if (data.compareTo(parent.data) > 0) {
            //如果右子节点为空，那就放到右子节点
            if (parent.right == null) {
                parent.right = now;
                now.parent = parent;
                return;
                //如果右子节点不为空，那就继续比较
            } else {
                parent = parent.right;
            }
        } else {
            return;
        }
    }
}

搜索是二进制搜索的概念.

public Node<E> get(E data) {
    if (root == null) {
        return null;
    }
    Node<E> now = root;
    while (now != null) {
        //小于当前节点，就与左子树比较
        if (data.compareTo(now.data) < 0) {
            now = now.left;
            //大于当前节点，就放与右子树比较
        } else if (data.compareTo(now.data) > 0) {
            now = now.right;
            //等于当前节点，就直接返回当前节点
        } else {
            return now;
        }
    }
    return null;
}

删除元素:

1. 如果p具有右子树，则找到其右子树的最左子节点r，然后使用r替换p;

2. 如果p具有左子树而没有右子树，则找到其左子树的最右子节点l，然后使用l替换p;

3. 如果p是叶节点二叉排序树 数据结构，则直接将其删除

public Node<E> remove(E data) {
    Node<E> p = get(data);
    if (p == null) {
        throw new NoSuchElementException();
    }
    //p的右子树的最左子节点r
    Node<E> r = nodeLeft(p.right);
    //p的左子树的最右子节点l
    Node<E> l = nodeRight(p.left);
    if (r != null) {
        p.data = r.data;
        //如果p的右子结点有左节点
        if (r != p.right) {
            r.parent.left = r.right;
        } else {
            p.right = p.right.right;
        }
        r.left = r.right = r.parent = null;
    } else if (l != null) {
        p.data = l.data;
        //如果p的左子结点有右节点
        if (l != p.left) {
            l.parent.right = l.left;
        } else {
            p.left = p.left.left;
        }
        l.left = l.right = l.parent = null;
        //如果p是叶子节点
    } else {
        if (p.parent == null) {
            root = null;
        } else if (p.parent.left == p) {
            p.parent.left = null;
        } else {
            p.parent.right = null;
        }
        p.parent = null;
    }
    return p;
}

代码地址:

关于数据结构和算法的专题:

喜欢，请喜欢二叉排序树 数据结构，谢谢！

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-245964-1.html