Java之二叉搜索树(BST)

这篇具有很好参考价值的文章主要介绍了Java之二叉搜索树(BST)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一.二叉搜索树(BST)

1.什么是二叉搜索树

2.判断一颗二叉搜索树

二.二叉搜索树CRUD操作

1.二叉搜索树的数据结构

2.添加操作

3.查找操作

1.查找最大值

2.查找最小值

3.查找任意值

4.删除操作

1.删除最大值

2.删除最小值

3.删除任意值

5.其他操作

1.打印操作(toString的实现)

6.代码总体实现

三.二叉搜索树的相关题目

1.二叉搜索树和双向链表

1.题目描述

描述

输入描述:

返回值描述:

2.问题分析

3.代码实现

2.将升序数组转化为平衡二叉搜索树

1.题目描述

2.问题分析

3.代码实现


一.二叉搜索树(BST)

1.什么是二叉搜索树

二叉搜索树(Binary Search Tree,简称BST)是一种常见的二叉树数据结构,它满足以下性质:

  1. 对于任意一个节点,它的左子树中的所有节点都小于它的值,它的右子树中的所有节点都大于它的值;
  2. 对于任意一个节点,它的左子树和右子树都是二叉搜索树。

因为二叉搜索树具有上述的性质,所以可以快速地进行查找、插入、删除等操作。在二叉搜索树中,查找一个元素的时间复杂度为O(log n),其中n是树中节点的个数。同时,在二叉搜索树中,可以按照某种顺序(如中序遍历)输出树中的所有节点,因此也可以作为一种排序数据的方法。

2.判断一颗二叉搜索树

如何判断一棵树是否为二叉搜索树呢?我们不能仅仅通过当前结点大于左孩子结点和小于右孩子来判断是二叉搜索树,这样是一些对二叉搜索树概念认识不清楚的人的误区,真正的定义应该当前结点大于它左子树上的任一结点并且小于右子树上的任一结点.其实利用非递归的思想就是利用中序遍历来判断,因为二叉搜索树的中序遍历一定是有序的,所以我们可以写出代码

    //二叉搜索树的中序遍历为有序序列
    public boolean isValidBST(TreeNode root) {
        travel(root);
        for (int i = 0; i < list.size() - 1; ++i) {
            if (list.get(i) >= list.get(i + 1))
                return false;
        }
        return true;


    }

    ArrayList<Integer> list = new ArrayList<>();

    public void travel(TreeNode root) {
        if (root == null)
            return;
        travel(root.left);
        list.add(root.val);
        travel(root.right);

    }

递归的思想也很好判断,当我们进入左子树的时候,之前根结点的值就是最大值,当我们进入右子树的时候,之前根结点的值就是最小值,我们只需要左子树的值都小于之前根结点的值,右子树的值都大于根结点的值,就可以判断出来了.

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }

二.二叉搜索树CRUD操作

1.二叉搜索树的数据结构

首先和普通的二叉树有一样的数据结构,要有一个私有的内部类TreeNode(对于内部类不了解的可以看这篇文章:https://blog.csdn.net/qq_64580912/article/details/129310721),作为二叉树节点,保存结点的值和左右孩子结点的指向,然后BST类的内部也应该用root结点属性,代表这颗二叉搜索树的根结点,然后就是size属性,代表二叉搜索树的结点个数

public class BST {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }

    private TreeNode root;
    private int size;


}

2.添加操作

因为二叉搜索树的性质:当前结点的值比左子树的任一结点都大,比右子树的任一结点都小,在添加的时候,我们不能破坏了二叉搜索树的这一性质,并且插入的时候我们总是在将新添加的结点成为叶子结点,因此当添加结点的值小于当前根结点的时候,向左子树递归插入,当添加的结点的值大于当前根结点的时候,向右子树递归插入,当根结点为空的时候,我们进行结点的添加,返回添加的结点,然后递归返回进行结点的连接操作.

    public void add(int val) {
        this.root = add(root, val);
    }

    //插入的结点都是和根结点进行比较,如果大于根结点,右子树的插入,如果小于根结点就是左子树的插入
    public TreeNode add(TreeNode root, int val) {
        //寻找到了插入的位置
        if (root == null) {
            TreeNode node = new TreeNode(val);
            size++;
            return node;
        } else if (root.val > val) {//此时左子树插入
            root.left = add(root.left, val);
            return root;

        }
        //此时左子树插入
        root.right = add(root.right, val);
        return root;
    }

3.查找操作

1.查找最大值

迭代实现

迭代查找最大值是很容易的,因为二叉树的性质:当前结点的值比左子树的任一结点都大,比右子树的任一结点都小,因此很容易知道最大的结点是这棵树的最右端的结点,

    //查找最大值 ---迭代实现
    public int findMax() {
        if (root == null) {
            throw new NoSuchElementException("root is null");
        }
        TreeNode temp = root;
        while (temp.right != null) {
            temp = temp.right;
        }
        return temp.val;

    }

递归实现

递归其实也是比较容易实现的,我们只需要不断的向右子树进行递归,当当前根结点的右孩子结点为空的时候进行返回当前根结点即可.

    //查找最大值 ---递归实现
    public TreeNode findMax2() {
        if (root == null) {
            throw new NoSuchElementException("root is null");
        }
        return findMax2(root);

    }

    public TreeNode findMax2(TreeNode root) {
        if (root.right == null) {
            return root;
        }
        return findMax2(root.right);

    }

2.查找最小值

迭代实现

迭代查找最小值是很容易的,因为二叉树的性质:当前结点的值比左子树的任一结点都大,比右子树的任一结点都小,因此很容易知道最小的结点是这棵树的最左端的结点,

    //查找最小值 ---迭代实现
    public int findMin() {
        if (root == null) {
            throw new NoSuchElementException("root is null");
        }
        TreeNode temp = root;
        while (temp.left != null) {
            temp = temp.left;
        }
        return temp.val;

    }

递归实现

递归其实也是比较容易实现的,我们只需要不断的向左子树进行递归,当当前根结点的左孩子结点为空的时候进行返回当前根结点即可.

    //查找最小值 ---迭代实现
    public TreeNode findMin2() {
        if (root == null) {
            throw new NoSuchElementException("root is null");
        }
        return findMin2(root);

    }

    public TreeNode findMin2(TreeNode root) {
        if (root.left == null) {
            return root;
        }
        return findMin2(root.left);

    }

3.查找任意值

普通二叉树查找任意值的时候,需要将整个二叉树进行遍历,查看是否存在,而二叉搜索树只需要遍历一半的结点,因为还是二叉树的性质:当前结点的值比左子树的任一结点都大,比右子树的任一结点都小,当需要查找的值的结点比当前根结点小的时候向左子树进行递归遍历,当需要查找的值的结点比当前根结点大的时候向右子树进行递归遍历,和需要查找的值的结点相等的时候,直接返回true;或者根结点为null的时候,直接返回false.

    //是否包含值为val的结点
    public boolean contains(int val) {
        return contains(root, val);
    }

    private boolean contains(TreeNode root, int val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        } else if (root.val > val) {
            return contains(root.left, val);
        }
        return contains(root.right, val);

    }

4.删除操作

1.删除最大值

如下图所示的一颗二叉搜索树,我们要删除最大值(也就是7结点),我们首先需要找到最大节点的位置,和查找最大值的方法上面一样,直接递归到最大值的位置,此时最大值的左子树可能还存在结点,我们需要做的就是把最大值结点(也就是当前根结点)的左节点返回出去,然后和递归返回的时候和上一层根结点的右子树进行连接.

Java之二叉搜索树(BST)Java之二叉搜索树(BST)

    public int removeMax() {
        int max = findMax();
        root = removeMax(root);
        size--;
        return max;
    }

    //删除为root的结点
    private TreeNode removeMax(TreeNode root) {
        if (root.right == null) {
            //当前结点为最大值结点
            TreeNode left = root.left;
            root.left = root = null;
            size--;
            return left;
        }
        root.right = removeMax(root.right);
        return root;


    }

2.删除最小值

和删除最大值的方法一样,无非就是一直向左子树进行遍历,遍历到最小的结点之后,返回最小节点的右子树,然后一次进行连接.

    public int removeMin() {
        int min = findMin();
        root = removeMin(root);
        size--;
        return min;
    }

    //删除为root的结点
    private TreeNode removeMin(TreeNode root) {
        if (root.left == null) {
            //当前结点为最大值结点
            TreeNode right = root.right;
            root.right = root = null;
            size--;
            return right;
        }
        root.left = removeMin(root.left);
        return root;


    }

3.删除任意值

删除任意值的操作就十分复杂了.当然也有和之前查找任意值套路一样的地方,就是当删除值小于当前根结点的时候,向左子树进行遍历,当删除值大于当前根结点的时候,向右子树进行遍历,当然可能存在遍历到为空节点的情况(此时删除值的结点不存在二叉搜索树中,返回null就可以,相当于对这颗二叉搜索树没有进行任何操作).

接下来我们需要考虑的就是找到要删除的结点时候的操作,主要分为以下的几种情况:

  • 情况一:当前结点(也就是要删除的结点)左右子树都为空
  • 情况二:当前结点左子树为空,右子树不为空
  • 情况三:当前结点右子树为空,左子树不为空
  • 情况四:当前结点左子树和右子树均不为空

对于情况一可以很好的解决,只需要直接返回null就可以了,对于情况二,左子树为空,我们只需要把右子树进行返回即可,和删除最小节点一个思路,对于情况三,右子树为空,我们只需要把左子树进行返回即可,和删除最大节点一个思路.其实我们可以把情况一归结到情况二或者情况三里面,因为情况二和情况三返回右子树或者左子树,如果对于情况一,直接返回null了,也就是情况二或者情况三的类型.

对于情况四,就比较复杂了.其实我们可以变换一下思路,我们不删除这个结点,我们找一个结点来替换要删除结点的位置(successor),这要只要返回这个替换节点(successor)即可,那么该寻找哪一个结点来替换这个要删除的结点,并且一定不能破坏二叉搜索树的结构,这个结点要大于左子树的任何一值并且小于右子树的任意值,其实就是找到左子树的最大值或者右子树的最小值来进行替换,(以用左子树的最大值替换举例)我们使用我们写好的方法就可以找到要删除结点的左子树最大值(findMax(root)),然后我们把successor的右孩子指向(左子树的最大值进行删除的树removeMax(root))与进行连接,并且将successor的左孩子结点指向根节点的左子树,

注意:这两步不能颠倒,因此如果先successor的左孩子指向root.left的话,然后调用removeMax(root)可能会删除错误结点的数据连接了.

并且这个时候不要size--了,因为removeMax(root)里面已经包含了size--;

    //在bst树中删除任意节点

    /**
     * @param val
     * @return 删除成功返回true, 失败返回false
     */
    public void remove(int val) {
        root = remove(root, val);
    }

    /**
     * 删除当前树中值为val的结点,没有返回null
     *
     * @param root
     * @param val
     * @return
     */
    private TreeNode remove(TreeNode root, int val) {
        //此时可能树中并不存在val=val的结点
        if (root == null) {
            return null;
        }
        //在左子树中进行删除
        if (root.val > val) {
            root.left = remove(root.left, val);
            return root;
        } else if (root.val < val) {//在右子树中进行删除
            root.right = remove(root.right, val);
            return root;
        } else {//当前结点就是要删除的结点
            if (root.left == null) {
                size--;
                TreeNode right = root.right;
                root.right = root = null;
                return right;
            }
            if (root.right == null) {
                size--;
                TreeNode left = root.left;
                root.left = root = null;
                return left;
            }
/*            //此时都不为空
            //寻找左子树的最大值或者右子树的最小值(采用这一种)来替代
            TreeNode successor = findMin2(root.right);
            //这一步的操作为把successor删除,并且将successor.right与root.right相连接,这两步的顺序不能改变
            successor.right = removeMin(root.right);
            //不需要size--,因为removeMin中已经进行了这个操作
            successor.left = root.left;
            root.left = root.right = root = null;
            return successor;*/

            //左子树的最大值替代
            TreeNode successor = findMax2(root.left);
            successor.right = removeMax(root.left);
            successor.left = root.left;
            return successor;


        }

    }

5.其他操作

1.打印操作(toString的实现)

直接进行打印,并且打印层次.

    @Override
    //前序toString打印
    public String toString() {
        StringBuilder sb = new StringBuilder();
        gengerateBSTString(root, 0, sb);
        return sb.toString();

    }

    /**
     * 在当前以root为结点的树中,将当前结点的层次和值,拼接到sb对象中
     *
     * @param root
     * @param depth
     * @param sb
     */
    private void gengerateBSTString(TreeNode root, int depth, StringBuilder sb) {
        if (root == null) {
            sb.append(generateDepthString(depth) + "null\n");
            return;
        }
        sb.append(generateDepthString(depth).append(root.val + "\n"));
        gengerateBSTString(root.left, depth + 1, sb);
        gengerateBSTString(root.right, depth + 1, sb);
    }

    private StringBuilder generateDepthString(int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; ++i) {
            sb.append("--");
        }
        return sb;
    }

6.代码总体实现

public class BST {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }

    private TreeNode root;
    private int size;

    @Override
    //前序toString打印
    public String toString() {
        StringBuilder sb = new StringBuilder();
        gengerateBSTString(root, 0, sb);
        return sb.toString();

    }

    /**
     * 在当前以root为结点的树中,将当前结点的层次和值,拼接到sb对象中
     *
     * @param root
     * @param depth
     * @param sb
     */
    private void gengerateBSTString(TreeNode root, int depth, StringBuilder sb) {
        if (root == null) {
            sb.append(generateDepthString(depth) + "null\n");
            return;
        }
        sb.append(generateDepthString(depth).append(root.val + "\n"));
        gengerateBSTString(root.left, depth + 1, sb);
        gengerateBSTString(root.right, depth + 1, sb);
    }

    private StringBuilder generateDepthString(int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; ++i) {
            sb.append("--");
        }
        return sb;
    }

    public int removeMax() {
        int max = findMax();
        root = removeMax(root);
        size--;
        return max;
    }

    //删除为root的结点
    private TreeNode removeMax(TreeNode root) {
        if (root.right == null) {
            //当前结点为最大值结点
            TreeNode left = root.left;
            root.left = root = null;
            size--;
            return left;
        }
        root.right = removeMax(root.right);
        return root;


    }

    public int removeMin() {
        int min = findMin();
        root = removeMin(root);
        size--;
        return min;
    }

    //删除为root的结点
    private TreeNode removeMin(TreeNode root) {
        if (root.left == null) {
            //当前结点为最大值结点
            TreeNode right = root.right;
            root.right = root = null;
            size--;
            return right;
        }
        root.left = removeMin(root.left);
        return root;


    }
    //在bst树中删除任意节点

    /**
     * @param val
     * @return 删除成功返回true, 失败返回false
     */
    public void remove(int val) {
        root = remove(root, val);
    }

    /**
     * 删除当前树中值为val的结点,没有返回null
     *
     * @param root
     * @param val
     * @return
     */
    private TreeNode remove(TreeNode root, int val) {
        //此时可能树中并不存在val=val的结点
        if (root == null) {
            return null;
        }
        //在左子树中进行删除
        if (root.val > val) {
            root.left = remove(root.left, val);
            return root;
        } else if (root.val < val) {//在右子树中进行删除
            root.right = remove(root.right, val);
            return root;
        } else {//当前结点就是要删除的结点
            if (root.left == null) {
                size--;
                TreeNode right = root.right;
                root.right = root = null;
                return right;
            }
            if (root.right == null) {
                size--;
                TreeNode left = root.left;
                root.left = root = null;
                return left;
            }
/*            //此时都不为空
            //寻找左子树的最大值或者右子树的最小值(采用这一种)来替代
            TreeNode successor = findMin2(root.right);
            //这一步的操作为把successor删除,并且将successor.right与root.right相连接,这两步的顺序不能改变
            successor.right = removeMin(root.right);
            //不需要size--,因为removeMin中已经进行了这个操作
            successor.left = root.left;
            root.left = root.right = root = null;
            return successor;*/

            //左子树的最大值替代
            TreeNode successor = findMax2(root.left);
            successor.right = removeMax(root.left);
            successor.left = root.left;
            return successor;


        }

    }

    public int getSize() {
        return size;
    }

    public void add(int val) {
        this.root = add(root, val);
    }

    //插入的结点都是和根结点进行比较,如果大于根结点,右子树的插入,如果小于根结点就是左子树的插入
    public TreeNode add(TreeNode root, int val) {
        //寻找到了插入的位置
        if (root == null) {
            TreeNode node = new TreeNode(val);
            size++;
            return node;
        } else if (root.val > val) {//此时左子树插入
            root.left = add(root.left, val);
            return root;

        }
        //此时左子树插入
        root.right = add(root.right, val);
        return root;
    }

    //查找最大值 ---迭代实现
    public int findMax() {
        if (root == null) {
            throw new NoSuchElementException("root is null");
        }
        TreeNode temp = root;
        while (temp.right != null) {
            temp = temp.right;
        }
        return temp.val;

    }

    //查找最大值 ---递归实现
    public TreeNode findMax2() {
        if (root == null) {
            throw new NoSuchElementException("root is null");
        }
        return findMax2(root);

    }

    public TreeNode findMax2(TreeNode root) {
        if (root.right == null) {
            return root;
        }
        return findMax2(root.right);

    }

    //查找最小值 ---迭代实现
    public int findMin() {
        if (root == null) {
            throw new NoSuchElementException("root is null");
        }
        TreeNode temp = root;
        while (temp.left != null) {
            temp = temp.left;
        }
        return temp.val;

    }

    //查找最小值 ---迭代实现
    public TreeNode findMin2() {
        if (root == null) {
            throw new NoSuchElementException("root is null");
        }
        return findMin2(root);

    }

    public TreeNode findMin2(TreeNode root) {
        if (root.left == null) {
            return root;
        }
        return findMin2(root.left);

    }

    //是否包含值为val的结点
    public boolean contains(int val) {
        return contains(root, val);
    }

    private boolean contains(TreeNode root, int val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        } else if (root.val > val) {
            return contains(root.left, val);
        }
        return contains(root.right, val);

    }

}

三.二叉搜索树的相关题目

1.二叉搜索树和双向链表

1.题目描述

描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。如下图所示

Java之二叉搜索树(BST)
要求:空间复杂度O(1)(即在原树上操作),时间复杂度 O(n)

注意:

1.要求不能创建任何新的结点,只能调整树中结点指针的指向。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode,有左右指针,其实可以看成一个双向链表的数据结构                             4.你不用输出双向链表,程序会根据你的返回值自动打印输出

输入描述:

二叉树的根节点

返回值描述:

双向链表的其中一个头节点。

牛客:二叉搜索树与双向链表_牛客题霸_牛客网

2.问题分析

像这类二叉树的问题,一般我们都采用递归的方式.

从一般到特殊,对于这样的一颗二叉搜索树树,我们该如何变为双向链表呢,此时将root.left=left,left.right=root,root.right=right,right.left=root;这样就可以转化为一颗二叉搜索树

Java之二叉搜索树(BST)

其实我们再来分析这个递归函数的信息,对于返回值:返回的这个双向链表的头结点,参数 pRootOfTree是当前子树的根结点,此时我们只需要将这个根结点与左半链表连接,与右半链表进行连接,就可以处理这个问题了,但是我们要小心空指针的问题,可能会左半链表或者右半链表为空的情况,并且左半链表返回的是头结点,我们要找到它的尾结点与根结点进行连接,右半链表直接用头结点与根结点进行连接,最终的返回值返回的头结点,但是当头结点为空的时候,要返回当前的根结点(此时左半链表为null).

3.代码实现

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        TreeNode head = Convert(pRootOfTree.left);
        TreeNode tail = head;
        while (tail != null) {
            if (tail.right == null) {
                break;
            }
            tail = tail.right;
        }
        // 此时tail节点走到了左半链表的尾部
        // 2.将左半链表和根节点拼接
        if (tail != null) {
            // 左子树存在
            tail.right = pRootOfTree;
            pRootOfTree.left = tail;
        }
        // 3.转换右子树和根节点拼接
        TreeNode right = Convert(pRootOfTree.right);
        // 拼接根节点和右半链表
        if (right != null) {
            right.left = pRootOfTree;
            pRootOfTree.right = right;
        }
        //如果head==null,说明此时左边链表为空,直接返回pRootOfTree
        return head == null ? pRootOfTree : head;

    }
}

2.将升序数组转化为平衡二叉搜索树

1.题目描述

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

例如当输入的升序数组为[-1,0,1,2]时,转化后的平衡二叉搜索树(BST)可以为{1,0,2,-1},如下图所示:

Java之二叉搜索树(BST)

或为{0,-1,1,#,#,#,2},如下图所示: 

Java之二叉搜索树(BST)

2.问题分析

需要转化为一颗平衡的二叉搜索树,也就是左右子树的高度差不超过1.也就是我们每次要选取数组中间的元素作为根结点,那么一定会保证高度差不超过1.此时我们要新建一个方法,方法的参数要包含数组,左指针left,右指针right,每一次求得mid,将他作为根结点,然后左子树递归,右子树递归,直到left>right的时候返回null.文章来源地址https://www.toymoban.com/news/detail-424686.html

3.代码实现

public class Solution {
    /**
     *
     * @param num int整型一维数组
     * @return TreeNode类
     */
    public TreeNode sortedArrayToBST (int[] num) {
        // write code here
        return convert(num, 0, num.length - 1);

    }
    public TreeNode convert(int[] num, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = left + ((right - left) >> 1);
        TreeNode node = new TreeNode(num[mid]);
        node.left = convert(num, left, mid - 1);
        node.right = convert(num, mid + 1, right);
        return node;


    }
}

到了这里,关于Java之二叉搜索树(BST)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++练级之路】【Lv.14】二叉搜索树(进化的二叉树——BST)

    快乐的流畅:个人主页 个人专栏:《C语言》《数据结构世界》《进击的C++》 远方有一堆篝火,在为久候之人燃烧! 二叉树在之前的数据结构章节讲解过,当时使用C来实现。而如今学习的二叉搜索树,便是二叉树的进阶,也更适合使用C++来实现。 二叉搜索树(BST,Binary Se

    2024年03月23日
    浏览(33)
  • 【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST)

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,

    2024年03月28日
    浏览(63)
  • C++ 二叉搜索树(BST)的实现(非递归版本与递归版本)与应用

    二叉搜索树既可以实现为升序版本,也可以实现为降序版本 本文实现为升序版本 二叉搜索树是一种特殊的二叉树 它的特点是: 1.左子树的所有节点均比根节点的值小 2.右子树的所有节点均比根节点的值大 3.左右子树都是二叉搜索树 4.中序遍历序列是有序的 5.一般二叉搜索树不

    2024年02月04日
    浏览(43)
  • ( “树” 之 BST) 109. 有序链表转换二叉搜索树 ——【Leetcode每日一题】

    二叉查找树(BST):根节点大于等于左子树所有节点,小于等于右子树所有节点。 二叉查找树中序遍历有序。 给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子

    2023年04月23日
    浏览(39)
  • 【C++】二叉树进阶之二叉搜索树

    作者简介:დ旧言~,目前大二,现在学习Java,c,c++,Python等 座右铭:松树千年终是朽,槿花一日自为荣。 目标:熟练掌握二叉搜索树,能自己模拟实现二叉搜索树 毒鸡汤:不断的努力,不断的去接近梦想,越挫越勇,吃尽酸甜苦辣,能够抵御寒冬,也能够拥抱春天,这样

    2024年03月16日
    浏览(82)
  • 数据结构之二叉搜索树

    满足条件: 1.对于根节点:左子树中所有节点的值小于右子树中所有节点的值 2.任意节点的左右子树也是二叉搜索树,同样满足条件1 我们将二叉搜索树封装为一个类 BinarySearchTree ,并声明一个成员变量 root ,指向树的根节点 查找节点 给定目标值 target ,我们可以根据二叉搜索

    2024年01月20日
    浏览(35)
  • 数据结构与算法之二叉树: Leetcode 98. 验证二叉搜索树 (Typescript版)

    验证二叉搜索树 https://leetcode.cn/problems/validate-binary-search-tree/ 描述 给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身

    2024年02月16日
    浏览(36)
  • 数据结构之二叉树(Java)

    在这里先说明一下,结点和节点其实一样的,无须关注这个。 1. 概念:树是一种非线性的数据结构,它是由n个有限节点组成一个具有层次关系的集合。 如上图所示,把此种数据结构称作树是因为它看起来像一个倒挂的树。  2. 特点 有一个特殊的节点,称为根节点,它是唯一

    2024年02月07日
    浏览(36)
  • 【开卷数据结构 】二叉排序树(BST)

    目录 二叉排序树(BST) 二叉排序树的定义 二叉排序树的操作 二叉排序树的查找 代码演示 二叉排序树的插入 代码演示 二叉排序树的构造 代码演示 二叉排序树的删除 Q:什么是二叉排序树 A: 二叉排序树或者是一棵空树,或者是具有如下性质的二叉树 1) 若它的左子树不空

    2024年02月11日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包