Java创建二叉搜索树,实现搜索,插入,删除操作

简介: Java实现的二叉搜索树,并实现对该树的搜索,插入,删除操作(合并删除,复制删除) 首先我们要有一个编码的思路,大致如下: 1、查找:根据二叉搜索树的数据特点,我们可以根据节点的值得比较来实现查找,查找值大于当前节点时向右走,反之向左走!2、插入:我们应该知道,插入的全部都是叶子节点,所以我们就需要找到要进行插入的叶子节点的位置,插入的思路与查找的思路一致。

Java实现的二叉搜索树,并实现对该树的搜索,插入,删除操作(合并删除,复制删除)
首先我们要有一个编码的思路,大致如下:
1、查找:根据二叉搜索树的数据特点,我们可以根据节点的值得比较来实现查找,查找值大于当前节点时向右走,反之向左走!

2、插入:我们应该知道,插入的全部都是叶子节点,所以我们就需要找到要进行插入的叶子节点的位置,插入的思路与查找的思路一致。

3、删除:
1)合并删除:一般来说会遇到以下几种情况,被删节点有左子树没右子树,此时要让当前节点的父节点指向当前节点的左子树;当被删节点有右子树没有左子树,此时要让当前节点的父节点指向该右子树;当被删节点即有左子树又有右子树时,我们可以找到被删节点的左子树的最右端的节点,然后让这个节点的右或者左“指针”指向被删节点的右子树
2)复制删除:复制删除相对而言是比较简单的删除操作,也是最为常用的删除操作。大致也有以下三种情况:当前节点无左子树有右子树时,让当前右子树的根节点替换被删节点;当前节点无右子树有左子树时,让当前左子树的根节点替换被删除节点;当前被删节点既有左子树又有右子树时,我们就要找到被删节点的替身,可以在被删节点的左子树中找到其最右端的节点,并让这个节点的值赋给被删节点,然后别忘了让此替身节点的父节点指向替身的“指针”为空,(其实在Java中无关紧要了,有垃圾处理机制自动进行处理)。你也可以在当前被删节点的右子树的最左端的节点作为替身节点来实现这一过程。


接下来就上代码吧。
首先是## 二叉搜索树节点类 ##

package SearchBinaryTree;

public class SearchBinaryTreeNode<T> {
    T data;
    public SearchBinaryTreeNode<T> leftChild;
    public SearchBinaryTreeNode<T> rightChild;

    public SearchBinaryTreeNode(){
        this.data=null;
        this.leftChild=this.rightChild=null;
    }

    public SearchBinaryTreeNode(T da){
        this.data=da;
        this.leftChild=this.rightChild=null;
    }

    public SearchBinaryTreeNode(T da,SearchBinaryTreeNode<T> left,SearchBinaryTreeNode<T>right){
        this.data=da;
        this.leftChild=left;
        this.rightChild=right;
    }

    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public SearchBinaryTreeNode<T> getLeftChild() {
        return leftChild;
    }
    public void setLeftChild(SearchBinaryTreeNode<T> leftChild) {
        this.leftChild = leftChild;
    }
    public SearchBinaryTreeNode<T> getRightChild() {
        return rightChild;
    }
    public void setRightChild(SearchBinaryTreeNode<T> rightChild) {
        this.rightChild = rightChild;
    }

    public boolean isLeaf(){
        if(this.leftChild==null&&this.rightChild==null){
            return true;
        }
        return false;
    }


}

实现二叉搜索树

package SearchBinaryTree;


public class SearchBinaryTree<T> {
    SearchBinaryTreeNode<T> root;

    public boolean isEmpty(){
        if(root==null){
            return true;
        }
        return false;
    }

    public void Visit(SearchBinaryTreeNode<T> root){
        if(root==null){
            System.out.println("this tree is empty!");
        }
        System.out.println(root.getData());
    }

    public SearchBinaryTreeNode<T> getRoot(){
        if(root==null){
            root=new SearchBinaryTreeNode<T>();
        }
        return root;
    }

    public SearchBinaryTree(){
        this.root=null;
    }

    /*
     * 创造一颗二叉树
     */
    public void CreateTree(SearchBinaryTreeNode<T> node, T data) {
        if (root == null) {
            root = new SearchBinaryTreeNode<T>();
        } else {
            if (Math.random() > 0.5) {                   //采用随机方式创建二叉树
                if (node.leftChild == null) {
                    node.leftChild = new SearchBinaryTreeNode<T>(data);
                } else {
                    CreateTree(node.leftChild, data);
                }
            } else {
                if (node.rightChild == null) {
                    node.rightChild = new SearchBinaryTreeNode<T>(data);
                } else {
                    CreateTree(node.rightChild, data);
                }
            }
        }
    }

    /*
     * 在二查搜索树中进行搜索
     */
    public SearchBinaryTreeNode<T> search(SearchBinaryTreeNode<T> root,T value){
        SearchBinaryTreeNode<T> current=root;
        while((root!=null)&&(current.getData()!=value)){
            //需要注意的是java中泛型无法比较大小,在实际的使用时我们可以使用常见的数据类型来替代这个泛型,这样就不会出错了
            current=(value<current.getData()?search(current.leftChild,value):search(current.rightChild,value));
        }
        return current;
    }

    public SearchBinaryTreeNode<T> insertNode( T value){
        SearchBinaryTreeNode<T> p=root,pre=null;
        while(p!=null){
            pre=p;
            //需要注意的是java中泛型无法比较大小,在实际的使用时我们可以使用常见的数据类型来替代这个泛型,这样就不会出错了
            if(p.getData()<value){
                p=p.rightChild;
            }else{
                p=p.leftChild;
            }
        }
        if(root==null){
            root=new SearchBinaryTreeNode<T>(value);
        }else if(pre.getData()<value){
            pre.rightChild=new SearchBinaryTreeNode<T>(value);
        }else{
            pre.leftChild=new SearchBinaryTreeNode<T>(value);
        }
    }

    /*
     * 合并删除
     */
    public void deleteByMerging(SearchBinaryTreeNode<T> node){
        SearchBinaryTreeNode<T> temp=node;
        if(node!=null){
            //若被删除节点没有右子树,用其左子树的根节点来代替被删除节点
            if(node.rightChild!=null){
                node=node.leftChild;
            }else if(node.leftChild==null){
                //若被删节点没有左子树,用其有字数的最左端的节点代替被删除的节点
                node=node.rightChild;
            }else{
                //如果被删节点左右子树均存在
                temp=node.leftChild;
                while(temp.rightChild!=null){
                    temp=temp.rightChild;     //一直查找到左子树的右节点
                }

                //将查找到的节点的右指针赋值为被删除节点的右子树的根
                temp.rightChild=node.rightChild;
                temp=node;
                node=node.leftChild;
            }
            temp=null;
        }
    }

    /*
     * 复制删除
     */
    public void deleteByCoping(SearchBinaryTreeNode<T> node){
        SearchBinaryTreeNode<T> pre=null;
        SearchBinaryTreeNode<T> temp=node;
        //如果被删节点没有右子树,用其左子树的根节点来代替被删除节点
        if(node.rightChild==null){
            node=node.leftChild;
        }else if(node.leftChild==null){
            node=node.rightChild;
        }else{
            //如果被删节点的左右子树都存在
            temp=node.leftChild;
            pre=node;
            while(temp.rightChild!=null){
                pre=temp;
                temp=temp.rightChild;      //遍历查找到左子树的最右端的节点
            }
            node.data=temp.data;           //进行赋值操作
            if(pre==node){
                pre.leftChild=node.leftChild;
            }else{
                pre.rightChild=node.rightChild;
            }
        }
        temp=null;
    }

}

测试类

package SearchBinaryTree;

public class SearchBinaryTreeTest {

    public static void main(String []args){
        SearchBinaryTree<Integer> tree=new SearchBinaryTree<Integer>();
        for(int i=1;i<10;i++){
            tree.CreateTree(new SearchBinaryTreeNode<Integer>(), i);
        }

        //搜索
        tree.search(tree.root, 7);

        //合并删除
        tree.deleteByMerging(new SearchBinaryTreeNode<Integer>(8));

        //复制删除
        tree.deleteByCoping(new SearchBinaryTreeNode<Integer>(6));
    }

}

好了,就是这样!

目录
相关文章
|
5月前
|
存储 算法 Java
Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点,而BFS利用队列按层次访问。以下是简化的代码片段:[Java代码略]
45 4
|
2月前
|
Java
Java搜索与替换
Java搜索与替换
24 4
Java搜索与替换
|
5月前
|
Java
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
48 2
|
5月前
|
存储 算法 Java
Java查找算法概览:二分查找适用于有序数组,通过比较中间元素缩小搜索范围;哈希查找利用哈希函数快速定位,示例中使用HashMap存储键值对,支持多值关联。
【6月更文挑战第21天】Java查找算法概览:二分查找适用于有序数组,通过比较中间元素缩小搜索范围;哈希查找利用哈希函数快速定位,示例中使用HashMap存储键值对,支持多值关联。简单哈希表实现未涵盖冲突解决和删除操作。
55 1
|
6月前
|
存储 Java 数据库连接
从 0 实现一个文件搜索工具 (Java 项目)
从 0 实现一个文件搜索工具 (Java 项目)
75 17
|
4月前
|
存储 搜索推荐 算法
Java中的文本搜索与全文检索引擎
Java中的文本搜索与全文检索引擎
|
5月前
|
存储 前端开发 算法
2016届蓝桥杯大赛软件类国赛Java大学B组 反幻方 暴力搜索
2016届蓝桥杯大赛软件类国赛Java大学B组 反幻方 暴力搜索
30 0
|
5月前
|
Java
二叉树搜索 - Java版
二叉树搜索 - Java版
16 0
|
5月前
|
算法 Java Go
【经典算法】LeetCode 35. 搜索插入位置(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 35. 搜索插入位置(Java/C/Python3/Golang实现含注释说明,Easy)
34 0
|
6月前
|
Java
java如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。
这段内容介绍了Java中使用AVL树实现高效二叉搜索树的方法。AVL树是一种自平衡树,节点子树高度差不超过1,确保操作时间复杂度为O(log n)。代码包括了`Node`类和`AVLTree`类,实现了节点、插入、删除、查找和平衡旋转等方法。通过旋转操作,维持树的平衡,保证了搜索效率。
43 6