本文最后更新于：2022年12月13日晚上

二叉排序树(BST)

二叉排序树(BST)

背景引入

需求分析

给你一个数列 (7,3,10,12,5,1,9)，要求能够高效的完成对数据的查询和添加

解决方案分析

使用数组

数组未排序
- 优点：直接在数组尾添加，速度快。
- 缺点：查找速度慢。
数组排序
- 优点：可以使用二分查找，查找速度快。
- 缺点：为了保证数组有序，在添加新数据时找到插入位置后，后面的数据需整体移动，速度慢。

使用链式存储（链表）

不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动。

使用二叉排序树

二叉排序树基本介绍

二叉排序树 BST (Binary Sort(Search) Tree)对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点

二叉排序树的创建与排序

直接上代码

public class BinarySortTree {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int j : arr) {
            binarySortTree.add(new Node(j));
        }
        binarySortTree.infixOrder();
        // 1 3 5 7 9 10 12
    }

    Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void infixOrder() {
        if (root == null) {
            System.out.println("树为空");
            return;
        }
        root.infixOrder();
    }

}

class Node {
    int val;
    Node left;
    Node right;

    public Node(int val) {
        this.val = val;
    }

    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (node.val < this.val) {
            if (this.left == null)
                this.left = node;
            else
                this.left.add(node);
        } else {
            if (this.right == null)
                this.right = node;
            else
                this.right.add(node);
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.print(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        return " " + this.val;
    }
}

二叉排序树的删除

二叉排序树的删除情况比较复杂，有下面三种情况需要考虑

删除叶子节点
删除只有一颗子树的节点
删除有两颗子树的节点

思路分析

第一种情况

删除叶子节点思路

（1）先找到要删除的结点targetNode
（2）找到targetNode的父结点parent
（3）确定targetNode是parent的左子结点还是右子结点
（4）根据前面的情况来对应删除

左子结点parent.left = null
右子结点parent.right = null

第二种情况

删除只有一颗子树的节点思路

（1）先找到要删除的结点targetNode
（2）找到targetNode的父结点parent
（3）确定targetNode的子结点是左子结点还是右子结点
（4）targetNode是parent的左子结点还是右子结点
（5）如果targetNode有左子结点

如果targetNode是parent的左子结点parent.left = targetNode.left
如果targetNode是parent的右子结点parent.right = targetNode.left

（6）如果targetNode有右子结点

如果targetNode是parent的左子结点parent.left = targetNode.right
如果targetNode是parent的右子结点parent.right = targetNode.right

第三种情况

删除有两颗子树的节点思路

（1）先找到要删除的结点targetNode
（2）从targetNode的右子树找到最小的结点，或者从左子树找最大的结点
（3）用一个临时变量，将最小结点的值保存temp = min
（4）删除该最小结点
（5）targetNode.value = temp

代码实现

在Node中添加search和searchParent方法

// 查找结点
public Node search(int val) {
    if (this.val == val) {
        return this;
    } else if (this.val > val) {
        if (this.left == null)
            return null;
        return this.left.search(val);
    } else {
        if (this.right == null)
            return null;
        return this.right.search(val);
    }
}
// 查找父结点
public Node searchParent(int val) {
    if ((this.left != null && this.left.val == val) || this.right != null && this.right.val == val) {
        return this;
    } else if (this.val > val && this.left != null) {
        return this.left.searchParent(val);
    } else if (this.val <= val && this.right != null) {
        return this.right.searchParent(val);
    } else {
        return null;
    }
}

在BinarySortTree类中添加search、searchParent和delNode方法

public void delNode(int val) {
    if (root == null) {
        return;
    }
    Node targetNode = this.search(val);
    if (targetNode == null) {
        return;
    }
    // 判断树是不是只有一个只根节点
    if (root.left == null && root.right == null) {
        root = null;
        return;
    }
    Node parent = this.searchParent(val);
    if (targetNode.left == null && targetNode.right == null) {
        // 如果targetNode是叶子结点
        if (parent.left != null && parent.left == targetNode)
            parent.left = null;
        if (parent.right != null && parent.right == targetNode)
            parent.right = null;
    } else if (targetNode.left != null && targetNode.right == null) {
        // 如果targetNode只有一颗左子树
        if (parent.left != null && parent.left == targetNode)
            // 如果targetNode是parent的的左子结点
            parent.left = targetNode.left;
        if (parent.right != null && parent.right == targetNode)
            // 如果targetNode是parent的的右子结点
            parent.right = targetNode.left;
    } else if (targetNode.left == null) {
        // 如果targetNode只有一颗右子树
        if (parent.left != null && parent.left == targetNode)
            // 如果targetNode是parent的的左子结点
            parent.left = targetNode.right;
        if (parent.right != null && parent.right == targetNode)
            // 如果targetNode是parent的的右子结点
            parent.right = targetNode.right;
    } else {
        // 如果targetNode有两颗子树
        Node temp = targetNode.right;
        // 找右子树的最小值
        while (temp.left != null) {
            temp = temp.left;
        }
        delNode(temp.val);
        targetNode.val = temp.val;
    }
}
// 查找父结点
public Node searchParent(int val) {
    if (root == null) {
        return null;
    }
    return root.searchParent(val);
}
// 查找结点
public Node search(int val) {
    if (root == null) {
        return null;
    }
    return root.search(val);
}

拓展练习

将第三种情况的（2）改为从左子树找最大的结点

将第三种情况的代码改为

// 如果targetNode有两颗子树
Node temp = targetNode.left;
// 找左子树的最大值
while (temp.right != null) {
    temp = temp.right;
}
delNode(temp.val);
targetNode.val = temp.val;

存在BUG

当第二种情况的目标结点为根结点是，目标结点的父结点为空，会出现空指针问题。

修改第二种情况的代码为：

if (targetNode.left != null && targetNode.right == null) {
    if (parent == null) {
        root = targetNode.left;
        return;
    }
    // 如果targetNode只有一颗左子树
    if (parent.left != null && parent.left == targetNode)
        // 如果targetNode是parent的的左子结点
        parent.left = targetNode.left;
    if (parent.right != null && parent.right == targetNode)
        // 如果targetNode是parent的的右子结点
        parent.right = targetNode.left;
} else if (targetNode.left == null) {
    if (parent == null) {
        root = targetNode.right;
        return;
    }
    // 如果targetNode只有一颗右子树
    if (parent.left != null && parent.left == targetNode)
        // 如果targetNode是parent的的左子结点
        parent.left = targetNode.right;
    if (parent.right != null && parent.right == targetNode)
        // 如果targetNode是parent的的右子结点
        parent.right = targetNode.right;
}

DataStructure

#Java #树 #Tree #Sort #Srarch

二叉排序树

https://yorick-ryu.github.io/数据结构/数据结构_二叉排序树/

作者

Yorick

发布于

2022年8月1日

许可协议

平衡二叉树上一篇

计算机基础下一篇