二进制排序树（Binary Sort Tree）搜索，插入，删除Java实现

可以通过在表的末尾插入和删除元素并与最后一个元素交换来维持顺序存储的插入和删除，以维持高效率，但是查找的效率很低.

如果搜索的数据表是有序的线性表并顺序存储，则可以通过诸如减半，插值和斐波那契等搜索算法来实现搜索二叉排序树删除，但是由于插入和删除操作的顺序二叉排序树删除，这将花费很多时间.

二叉树可以提高插入和删除效率，并且可以更有效地进行搜索.

二进制排序树，也称为二进制排序树. 它可以是具有以下属性的空树或二叉树

1. 如果其左子树不为空，则左子树上所有节点的值小于其根节点的值;

2. 如果其右子树不为空，则右子树上所有节点的值均小于其根节点的值;

3. 它的左和右子树也是二进制排序树.

搜索二进制排序树有两种方法: 递归和非递归.

public class BinarySortTree {
    
    /**
     * 根结点
     */
    private TreeNode rootNode;
    
    /**
     * 获取rootNode
     * @return
     */
    public TreeNode getRootNode() {
        return this.rootNode;
    }
    
    /**
     * 创建二叉排序树 的第一种方法（通过insertBST创建）
     * @param array
     * @return
     */
    public void createBinarySortTree1(int[] array) {
        
        for (int i = 0; i <array.length; i++) {
            if (!insertBST(array[i])) {
                System.out.println("已存在" + array[i] + "，不再插入二叉排序树");
            }
        }
        
    }
    
    /**
     * 创建二叉排序树 的第二种方法
     * @param array
     * @return
     */
    public void createBinarySortTree2(int[] array) {
        
        for (int i = 0; i < array.length; i++) {
            if (i == 0) {
                rootNode = new TreeNode(array[i]);
                continue;
            }
            
            TreeNode node = rootNode;
            while (true) {
                if (array[i] < node.getData()) {
                    
                    if (node.getLchild() == null) {
                        node.setLchild(new TreeNode(array[i]));
                        break;
                    } else {
                        node = node.getLchild();
                    }
                    
                } else if (array[i] == node.getData()) {
                    System.out.println("已存在" + array[i] + "，不再插入二叉排序树");
                    break;
                } else {
                    
                    if (node.getRchild() == null) {
                        node.setRchild(new TreeNode(array[i]));
                        break;
                    } else {
                        node = node.getRchild();
                    }
                    
                }
            }
        }
        
    }
    
    /**
     * 中序遍历
     * @param node
     */
    public void inOrderTraverse(TreeNode node) {
        if (node != null) {
            inOrderTraverse(node.getLchild());
            System.out.print(node.getData() + " ");
            inOrderTraverse(node.getRchild());
        }
    }
    
    /**
     * 二叉排序树的查找 （递归实现）
     * 
     * 查找可以有两种实现方法，一种是递归，一种是while 循环。
     * 在插入和删除操作中也首先需要查询操作，这时使用while 循环比较好，可以知道要查询结点的双亲结点
     * @param node
     * @param key
     * @return 返回
     */
    public boolean searchBST(TreeNode node, int key) {
        if (node == null) {
            return false;
        } else if (key == node.getData()) {
            return true;
        } else if (key < node.getData()) {
            return searchBST(node.getLchild(), key);
        } else {
            return searchBST(node.getRchild(), key);
        }
    }
    
    /**
     * 二叉排序树的插入
     * @param node
     * @param key
     */
    public boolean insertBST(int key) {
        
        //相当于 search 用非递归实现 -----begin 
        TreeNode node = rootNode;
        //查找 最后访问的 node
        TreeNode searchLastNode = null;
        
        while (node != null) {
            searchLastNode = node;
            if (key < node.getData()) {
                node = node.getLchild();
            } else if (key > node.getData()) {
                node = node.getRchild();
            } else {
                return false;
            }
        }
        // search ----end
        
        TreeNode newNode = new TreeNode(key);
        
        if (rootNode == null) {
            rootNode = newNode;
        } else if (key < searchLastNode.getData()) {
            searchLastNode.setLchild(newNode);
        } else {
            searchLastNode.setRchild(newNode);
        }
        
        return true;
    }
    
    
    public boolean deleteBST(int key) {
        //相当于 search 用非递归实现 -----begin 
        TreeNode node = rootNode;
        //存储 其双亲结点，如果是根节点，则双亲结点为null
        TreeNode parentNode = null;
        
        while (node != null) {
            if (key < node.getData()) {
                parentNode = node;
                node = node.getLchild();
            } else if (key > node.getData()) {
                parentNode = node;
                node = node.getRchild();
            } else {
                //相等时已找到
                break ;
            }
        }
        
        // search ----end
        
        //没有找到要删除的node
        if (node == null) {
            return false;
        }
        
        // 右子树为空 ，重接左子树
        if (node.getRchild() == null) {
            if (parentNode != null) {
                if (parentNode.getLchild() == node)
                    parentNode.setLchild(node.getLchild());
                else
                    parentNode.setRchild(node.getLchild());
            } else {
                rootNode = node.getLchild();
            }
        // 左子树为空，重接右子树
        } else if (node.getLchild() == null) {
            if (parentNode != null) {
                if (parentNode.getLchild() == node)
                    parentNode.setLchild(node.getRchild());
                else
                    parentNode.setRchild(node.getRchild());
            } else {
                rootNode = node.getRchild();
            }
        // 左右子树都不为空 ，可以将 要删除结点 按中序遍历的前驱或后继 替代 要删除结点的位置，此处取前驱
        } else {
            
            //取前驱结点 ，先转左，然后一直到最右
            TreeNode replaceNode = node.getLchild();
            TreeNode replaceParentNode = node;
            
            while (replaceNode.getRchild() != null) {
                replaceParentNode = replaceNode;
                replaceNode = replaceNode.getRchild();
            }
            //获取到前驱结点极其双亲结点
            
            //如果前驱结点的双亲结点是 要删除的结点
            if (replaceParentNode == node)
                replaceParentNode.setLchild(replaceNode.getLchild());
            else 
                replaceParentNode.setRchild(replaceNode.getLchild());
            
            node.setData(replaceNode.getData());
        }
        
        
        return true;
    }
    
    public static void main(String[] args) {
//        int[] array = new int[15];
//        System.out.print("随机数：");
//        for (int i = 0; i < 15; i++) {
//            array[i] = (int) (Math.random() * 100);
//            System.out.print(array[i] + " ");
//        }
        
        int[] array = {4, 10, 1, 13, 3, 15, 9, 11, 8, 5, 14, 2, 6, 7, 12};
        
        BinarySortTree binarySortTree = new BinarySortTree();
        //创建二叉排序树
        binarySortTree.createBinarySortTree1(array);
        
        //中序遍历 即是 从小到大的排序
        System.out.print("\n中序遍历结果：");
        binarySortTree.inOrderTraverse(binarySortTree.getRootNode());
        
        //二叉排序树的查找
        boolean searchResult = binarySortTree.searchBST(binarySortTree.getRootNode(), 2);
        if (searchResult) 
            System.out.println("\n查到");
        else
            System.out.println("\n查不到");
        
        //二叉排序树的删除 
        binarySortTree.deleteBST(2);
        binarySortTree.deleteBST(1);
        binarySortTree.deleteBST(3);
        binarySortTree.deleteBST(4);
        binarySortTree.deleteBST(10);
        binarySortTree.inOrderTraverse(binarySortTree.getRootNode());
        
    }
}
/**
 * 二叉树结点
 * 
 *
 */
class TreeNode {
    private int data;
    private TreeNode lchild;
    private TreeNode rchild;
    
    public TreeNode(int data) {
        this.data = data;
    }
    
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public TreeNode getLchild() {
        return lchild;
    }
    public void setLchild(TreeNode lchild) {
        this.lchild = lchild;
    }
    public TreeNode getRchild() {
        return rchild;
    }
    public void setRchild(TreeNode rchild) {
        this.rchild = rchild;
    }
    
    @Override
    public String toString() {
        return "TreeNode [data=" + data + ", lchild=" + lchild + ", rchild=" + rchild + "]";
    }
}

代码中显示的二叉树

运行结果:

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