二叉搜索树Java实现

1.二叉搜索树(Binary Search Tree):

(又:二叉查找树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
二叉搜索树Java实现_第1张图片

2.建二叉树

static class TreeNode {
     
        public int val;//值
        public TreeNode left;//左边
        public TreeNode right;//右边

        public TreeNode(int val) {
     //构造方法,用于赋值
            this.val = val;
        }
    }

二叉搜索树Java实现_第2张图片

3.搜索操作

//搜索操作
    public TreeNode search(int key) {
     //查找key
        TreeNode cur = root;
        while(cur != null) {
     
            if(cur.val == key) {
     
                return cur;
            } else if(cur.val < key) {
     
                cur = cur.right;
            }else  {
     
                cur = cur.left;
            }
        }
        return null;
    }

4.插入操作

//插入操作
    public void insertTree(int val) {
     
    //如果二叉搜索树为空,直接插入值
        if(root == null) {
     
            root = new TreeNode(val);
            return;
        }
        TreeNode cur = root;
        TreeNode parent = null;

        while(cur != null) {
     
             if(cur.val < val) {
     
                parent = cur;
                cur = cur.right;
            } else {
     
                parent = cur;
                cur = cur.left;
            }
        }
        TreeNode node = new TreeNode(val);
        if(parent.val < val) {
     
            parent.right = node;
        } else {
     
            parent.left = node;
        }
    }

5.删除操作

5.1:cur.lelf == null 左子树为空

cur 是root,则root = cur.right

二叉搜索树Java实现_第3张图片

cur不是root,cur是parent.left,则parent.left=cur.right

二叉搜索树Java实现_第4张图片

cur不是root,cur是parent.right,则parent.right=cur.right

二叉搜索树Java实现_第5张图片

5.2:cur.right == null 右子树为空

右子树为空与左子树为空大致相同,可以自行推理。

5.3:cur.lelf != null&&cur.right != null 左右子树都不为空

思路:

  • 左树找最大数据
  • 右树找最小数据

这里演示右树找最小数据

top1:找的树在左边
二叉搜索树Java实现_第6张图片
**top2:**找的树在右边
二叉搜索树Java实现_第7张图片

//删除操作
    public void remove(int key) {
     
        TreeNode cur = root;
        TreeNode parent = null;//查找相应结点然后删除
        while(cur != null) {
     
            if(cur.val == key) {
     
                removeNode(parent,cur);//删除函数
                return ;
            } else if(cur.val < key) {
     
                parent = cur;
                cur = cur.right;
            } else {
     
                parent = cur;
                cur = cur.left;
            }
        }
    }
    //通过removeNode函数进行删除
    public void removeNode(TreeNode parent,TreeNode cur) {
     
        if(cur.left == null) {
     //左子树为空
            if(cur == root) {
     
                root = cur.right;
            } else if(cur == parent.left) {
     
                parent.left = cur.right;
            } else {
     
                parent.right = cur.right;
            }
        } else if(cur.right == null) {
     
            if(cur == root) {
     //右子树为空
                root = cur.left;
            } else if(cur == parent.left) {
     
                parent.left = cur.left;
            } else {
     
                parent.right = parent.left;
            }
        } else {
     //替罪羊的删除*//左边找最大,右边找最小
            TreeNode targetparent = cur;
            TreeNode target = cur.right;
            while(target.left != null) {
     
                targetparent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(targetparent.left == target) {
     
                targetparent.left = target.right;
            } else {
     
                targetparent.right = target.right;
            }
        }
    }

二叉搜索树测试及完整代码:
https://gitee.com/btyyt/growing-xbt/commit/d2976f8036a9ef757cb9f00e3f42ac460096d90a

你可能感兴趣的