【java数据结构】二叉搜索树

博客最后附有整篇博客的全部代码！！！

一、二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树

从上述概念以及图中可以看出，二叉搜索树具有以下特性：

• 二叉搜索树中最左侧的节点是树中最小的节点，最右侧节点一定是树中最大的节点
• 采用中序遍历遍历二叉搜索树，可以得到一个有序的序列

二、二叉搜索树的操作

2.1 插入

思路：

1. 先判断这个树是否为null，为null则插入的值直接为根节点。
2. 定义一个parent节点，这个节点是来标记cur的父节点，以便cur节点走完，找到要插入的位置（这时就用parent节点的值和val对比，大于则插入parent节点的右节点，反之小于则是左节点）

代码：

  public void insertTreeNode(int val) {
        if(root == null) root = new TreeNode(val);
        else {
            TreeNode node = new TreeNode(val);
            TreeNode parent = root;
            TreeNode cur =root;
            while(cur!=null) {
                if(node.val < cur.val) {
                    parent=cur;
                    cur=cur.left;
                } else if(node.val > cur.val){
                    parent=cur;
                    cur=cur.right;
                }else{
                    return;
                }
            }
            if(parent.val> node.val){
                parent.left=node;
            }else{
                parent.right=node;
            }
        }
    }

2.2 查找

思路：

1. 先判断树是不是为空或为树的根节点
2. 定义cur节点，遍历树，遇到cur.val小于val,则cur=cur.right;反之大于则cur=cur.left；最后值相等，返回该节点。

    public TreeNode searchTreeNode(int val) {
        if(root == null) return null;
        if(val == root.val) return root;
        TreeNode cur=root;
        while(cur!=null) {
            if(cur.val>val){
                cur = cur.left;
            }else if(cur.val<val){
                cur = cur.right;
            }else{
                return cur;
            }
        }
        return null;
    }

2.3 删除（重点以及难点）

2.3.1 删除节点的左边为null

• 第一种情况，删除节点是根节点，root=cur.right；
  
• 第二种情况，删除的节点不是根节点，这是就需要借助parent节点来标记删除节点的父亲节点，parent.left=cur.right；
  
• 第三种情况，删除的节点不是根节点，parent.right=cur.right;
  

2.3.2 删除节点的右边为null

• 第一种情况，删除节点是根节点，root=cur.left；
  
• 第二种情况，删除节点不是根节点，cur=parent.left;则parent.left=cur.left;
• 第三种情况，删除节点不是根节点，cur=parent.right;则parent.right=cur.left;
  

2.3.3 删除的左右节点都不为空

思路：

替换法：找到删除节点左子树的最大值（或右子树的最小值）我们代码是以删除节点右数的最小值演示。
代码思路：让cur走找到删除节点，让parent来标记删除节点，此时让cur继续往右子树走，在右子树中找到最小值，定义节点t用来标记右子树最小值的父亲节点。

    public void removeTreeNode(int val) {
        if (root == null) return;
        TreeNode cur = root;
        TreeNode parent = root;
        //cur.left==null
        while (cur != null) {
            if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else {
                remove(cur, parent);
            }
        }

    }

    private void remove(TreeNode cur, TreeNode parent) {
        if (cur.left == null) {
            if (cur.val == root.val) {
                root = cur.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur.val == root.val) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            }else{
                parent.right = cur.left;
            }
        }else{
            TreeNode tp=cur;
            TreeNode t=cur.right;
            while(t.left!=null) {
                tp=t;
                t=t.left;
            }
            cur.val=t.val;
            if(tp.left==t){
                tp.left=t.right;
            }else{
                tp.right=t.right;
            }
        }
    }

三、二叉搜索树的性能分析

3.1 最优情况

二叉搜索树是完全二叉树时，时间复杂度：O(log n)

3.2 最差情况

二叉搜索树退化为单支数时，时间复杂度为：O(N)

此篇博客的全部代码！！！

原文地址：https://blog.csdn.net/2303_77535762/article/details/145309998

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！