Java实现二叉查找树的增删查详解

2022-11-13 11:11:29 查找 增删 详解

定义

二叉查找树（ADT）是一个具有对于树种的某个节点X,它的左节点都比X小，它的右节点都比X大的二叉树。如下就是一个符合

要求的二叉查找树：

增加节点

1.定义节点类:

class node{
    int val;
    Node left;
    Node right;
    public Node(int val){
        this.val=val;
    }
}

2.插入元素

我们采用递归的方法：

1.判断与根节点是否相同，相同无需操作

2.比根元素小往左边查找，左节点不存在的话则作为左节点插入即可

3.比根元素大往右边查找，右节点不存在的话则作为右节点插入即可

代码实现如下：

Node root;
 
    
    public void add(int val){
        if(root==null){
            root=new Node(val);
            return;
        }
        addNode(val,root);
    }
    private void addNode(int val,Node root){
        if(root==null || root.val==val){
            return;
        }
        if(root.val>val){
            if(root.left==null){
                root.left=new Node(val);
            }else {
                addNode(val,root.left);
            }
        }else {
            if(root.right==null){
                root.right=new Node(val);
            }else {
                addNode(val,root.right);
            }
        }
    }

查询节点

我们采用递归的方法：

1.判断与根节点是否相同，相同则返回true

2.比根元素小往左边查找，左节点为null则返回false表示不存在

3.比根元素大往右边查找，右节点为null则返回false表示不存在

代码实现如下:


    public boolean findVale(int val){
        return isExit(root,val);
    }
 
    private boolean isExit(Node node,int val){
        if(node==null){
            return false;
        }
        if(node.val==val){
            return true;
        }else if(node.val>val){
            return isExit(node.left,val);
        }else {
            return isExit(node.right,val);
        }
    }

删除节点

删除元素时要判断元素的情况：

1.删除的元素没有叶子节点，直接删除，如删除值为1的节点，虽然平衡性不是太好，但是还是符合二叉查找树的特性

2.删除的元素只有一个节点，删除元素并将指针指向其子节点 ，如删除值为4的节点:

3.删除的元素有左右两个节点，从右节点中找出大于该节点的最小节点，作为新的节点A,如删除节点值为2的节点:

代码实现如下:


    public void deleteElement(int val){
        deleteElement(null,root,val,true);
    }
 
    
    private void deleteElement(Node prev,Node root,int val,boolean isright){
        if(root.val==val){
            //删除的元素没有叶子节点，直接删除
            if(root.left==null &&  root.right==null){
                changeValue(prev,null,isright);
            }else if(root.left!=null &&  root.right!=null){
                //3.删除的元素有两个节点，从右节点中找出大于该元素的最小值，作为新的节点
                changeValue(prev,new Node(findMinGt(root,root.right,true)),isright);
                if(prev==null){
                    //对于头结点的删除特殊处理
                    prev=this.root;
                    prev.left=root.left;
                    prev.right=root.right;
                    return;
                }
                if(isright){
                    prev.right.right=root.right;
                    prev.right.left=root.left;
                }else {
                    prev.left.right=root.right;
                    prev.left.left=root.left;
                }
            }//删除的元素只有一个节点，删除元素并将指针指向其子节点
            else if(root.left!=null){
                changeValue(prev,root.left,isright);
            }else {
                changeValue(prev,root.right,isright);
            }
            return;
        }
        if(root.val>val){
            deleteElement(root,root.left,val,false);
        }else{
            deleteElement(root,root.right,val,true);
        }
    }
    //改变元素值
    private void changeValue(Node prev,Node value,boolean isright){
        if(prev==null){
            root=value;
            return;
        }
        if(isright){
            prev.right=value;
        }else {
            prev.left=value;
        }
    }
    //寻找大于根节点的最小值
    private int findMinGt(Node prev,Node root,boolean isRight){
        if(root.left==null && root.right==null){
            changeValue(prev,null,isRight);
            return root.val;
        }
        if(root.left==null){
            changeValue(prev,null,isRight);
            return root.val;
        }
        return findMinGt(root,root.left,false);
    }

到此这篇关于Java实现二叉查找树的增删查详解的文章就介绍到这了,更多相关Java二叉查找树增删查内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

相关文章