数据结构专题——二叉查找树的基本操作

Myth丶恋晨 2023-02-20 12:09 102阅读 0赞

### 什么是二叉查找树 ###

二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树，又称二叉搜索树，二叉排列树  
他的递归定义是

1.  要么二叉查找树是一颗空树
2.  要么二叉查找树是由根结点、左子树、右子树构成，其中左子树和右子树都是二叉查找树，且左子树上所有结点的数据均小于或等于根结点，右子树上的所有结点的数据均大于根结点 ，如下图所示![在这里插入图片描述][20200626172601427.jpg_pic_center]

### 二叉查找树的基本操作 ###

二叉查找树的操作算法是由一般查找树改造而来的。  
查找操作

/** * 查找 * @param root * @param x */
        public void search(BinaryNode root,int x){ 
            if(root==null){ 
                System.out.println("查找失败");
            }
            if(root.data==x){ 
                System.out.println("查找成功"+root.hashCode());
            }else if(root.data>x){ 
                search(root.rchild,x);
            }else{ 
                search(root.lchild,x);
            }
        }

插入操作

/** * 插入 * @param root * @param x */
        public  void insert(BinaryNode root ,int x){ 
            if(root.data>x&&root.lchild!=null){ 
                insert(root.lchild,x);
            }else if(root.data<=x&&root.rchild!=null){ 
                insert(root.rchild,x);
            }else if(root.data>x){ 
                root.lchild=new BinaryNode(x);
            }else{ 
                root.rchild=new BinaryNode(x);
            }
        }

删除操作，为了保证删除后还是一个二叉查找树，我们采取的方法是找到要删除的结点后，用比该结点小的最大结点或者用比该结点大的最小结点来替换该结点，这种方式不会破环二叉查找树的结构

public void delete(BinaryNode root, int x){ 
            if(root==null){ 
                return;
            }
            if(root.data==x){ 
                BinaryNode node=root;
                if(root.lchild!=null&&root.rchild!=null){ 
                    node=node.lchild;
                    while (node.rchild!= null) { 
                        node=node.rchild;
                    }
                    root.data=node.data;
                    node.pNode.rchild=null;
                }else if(root.lchild==null&&root.rchild==null){ 
                    if(node.pNode.lchild==root){ 
                        node.pNode.lchild=null; 
                    }else{ 
                        node.pNode.rchild=null;
                    }
                }else if(root.lchild==null&&root.rchild!=null){ 
                    if(node.pNode.lchild==root){ 
                        node.pNode.lchild=node.rchild;
                    }else{ 
                        node.pNode.rchild=node.rchild;
                    }
                }else{ 
                    if(node.pNode.lchild==root){ 
                        node.pNode.lchild=node.lchild;
                    }else{ 
                        node.pNode.rchild=node.lchild;
                    }
                }
            }else if(root.data>x){ 
                delete(root.lchild,x);
            }else{ 
                delete(root.rchild,x);
            }
        }

[20200626172601427.jpg_pic_center]: https://img-blog.csdnimg.cn/20200626172601427.jpg#pic_center