Java怎么实现二叉查找树的增删查

本篇内容介绍了“Java怎么实现二叉查找树的增删查”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

定义

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

要求的二叉查找树：

增加节点

定义节点类:

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

插入元素

我们采用递归的方法：

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

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

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

代码实现如下：

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);            }        }    }

查询节点

我们采用递归的方法：

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

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

比根元素大往右边查找，右节点为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的节点，虽然平衡性不是太好，但是还是符合二叉查找树的特性

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

删除的元素有左右两个节点，从右节点中找出大于该节点的最小节点，作为新的节点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怎么实现二叉查找树的增删查”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站，小编将为大家输出更多高质量的实用文章！