数据结构——用Java实现二分搜索树

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

目录

一、树

二、二分搜索树

1.二叉树

2.二分搜索树

三、代码实现

1.树的构建

2.获取树中结点的个数

3.添加元素

4.查找元素

(1)查找元素是否存在

(2)查找最小元素

(3)查找最大元素

5.二分搜索树的遍历

(1)前序遍历:

(2)中序遍历:

(3)后序遍历:

(4)层序遍历:

6.删除操作

(1)删除最小元素

(2)删除最大元素

(3)删除任意元素

(4)删除根节点


一、树

        树结构本身是一种天然的组织结构

        是一个高效的查询内容的结构

二、二分搜索树

1.二叉树

特点:1.只有唯一的一个根节点

           2.每个结点最多有两个孩子

           3.每个结点最多有一个父亲

           4.二叉树具有天然的递归结构(左右子树也是二叉树)

           5.叶子结点出现在二叉树的最底层,除叶子结点之外的其它结点都有两个孩子结点。

2.二分搜索树

是特殊的二叉树

每个节点都大于左子树的所有结点,都小于右子树的所有结点

注意:存储的元素必须具有可比性

因为二分搜索树也是二叉树,也具有天然的递归结构,所以许多方法都可以使用递归的思想去实现

三、代码实现

1.树的构建

需要的元素有:根节点,结点,频率(如果添加的元素有重复元素),结点的值,索引,结点个数

//树的结点
    private static class Node<T> {
        private final T ele;//结点的值
        private int frequence;//频率
        private Node<T> left, right;//分别指向左右孩子的索引

        public Node(T ele) {
            this.ele = ele;
            this.left = this.right = null;
        }

    }

    //树对应的属性
    private Node<T> root;//树的根节点
    private int size;//结点的个数

    //构建树
    public BinearySeachTree() {
        this.root = null;
        this.size = 0;
    }

在给元素添加泛型后,就不能直接比较,所以在开始就继承Comparable来实现元素的比较

public class BinearySeachTree<T extends Comparable<T>>{

}

2.获取树中结点的个数

//获取树中结点的个数
    public int getSize() {
        return this.size;
    }

3.添加元素

将元素添加到二分搜索树的过程中,要注意将大的元素放在结点的右边,小的元素放在左边

数据结构——用Java实现二分搜索树,数据结构

再添加元素时,需要找到对应的位置,则可以使用递归的思想。

如果添加的值小于结点的值,则查找结点左孩子,如果还是小于结点,则继续查找

//向树中添加结点
    public void add(T ele) {
        //更新根结点
        this.root = addDG(this.root, ele);
    }

    //语义:向以root为根的二分搜索树中添加元素ele
    private Node<T> addDG(Node<T> root, T ele) {
        //递归终止条件
        if (root == null) {
            this.size++;
            return new Node<T>(ele);
        }
        //递归操作
        if (root.ele.compareTo(ele) > 0) {
            root.left = addDG(root.left, ele);
        } else if (root.ele.compareTo(ele) < 0) {
            root.right = addDG(root.right, ele);
        } else {
            //更新频率
            root.frequence++;
        }
        return root;
    }

4.查找元素

(1)查找元素是否存在

        查找元素是否在二叉树中,查找每一个结点,如果查找元素比当前节点小,就在左子树里重新查找,如果查找元素比当前节点大,就在右子树里重新查找

 //查询的方法
    public boolean search(T ele) {
        return searchDG(this.root, ele);
    }

    //语义:从以root为根的二分搜索树中查找元素ele
    private boolean searchDG(Node<T> root, T ele) {
        //递归终止的条件
        if (root == null) {
            return false;
        }
        //递归操作
        if (root.ele.compareTo(ele) == 0) {
            return true;
        } else if (root.ele.compareTo(ele) > 0) {
            return searchDG(root.left, ele);
        } else {
            return searchDG(root.right, ele);
        }
    }

(2)查找最小元素

        二分搜索树中最左边的元素

 //找树中的最小元素
    public T getMinValue() {
        if (this.isEmpty()) {
            return null;
        }
        Optional<Node<T>> optional = getMinNode();
        return optional.get().ele;
    }

//直接查找
private Optional<Node<T>> getMinNode() {
        if (this.root == null) {
            return Optional.empty();
        }
        //一直向左查找
        Node<T> node = this.root;
        while (node.left != null) {
            node = node.left;
        }
        return Optional.of(node);
    }

//利用递归方法查找
    //语义:在以Node为根结点的树中查找最小结点
    private Optional<Node<T>> getMinNode(Node<T> node) {
        if (node.left == null) {
            return Optional.of(node);
        }
        return getMinNode(node.left);
    }

(3)查找最大元素

        二分搜索树中最右边的元素

//找树中的最大元素
    public T getMaxValue() {
        if (this.isEmpty()) {
            return null;
        }
        Optional<Node<T>> optional = getMaxNode(this.root);
        return optional.get().ele;

    }

 //语义:在以Node为根结点的树中查找最大结点
    private Optional<Node<T>> getMaxNode(Node<T> node) {
        if (node.right == null) {
            return Optional.of(node);
        }
        return getMaxNode(node.right);
    }

5.二分搜索树的遍历

树的遍历有四种:前序遍历;中序遍历;后序遍历;层序遍历

数据结构——用Java实现二分搜索树,数据结构

(1)前序遍历:

首先打印根节点,然后遍历左子树,最后是右子树

【28,16,13,22,30,29,42】

//前序遍历
    public void preTravel() {
        List<AbstractMap.SimpleEntry<T, Integer>> list = new ArrayList<>();
        preTravelDG(this.root, list);
        String str = list.stream().map(item -> "[" + item.getKey() + ":" + item.getValue() + "]").collect(Collectors.joining("-"));
        System.out.println(str);
    }

 //前序遍历以root为根的树,讲解稿保存在list中
    private void preTravelDG(Node<T> root, List<AbstractMap.SimpleEntry<T, Integer>> list) {
        //递归终止条件
        if (root == null) {
            return;
        }
        //递归操作
        list.add(new AbstractMap.SimpleEntry<>(root.ele, root.frequence));
        //遍历左子树
        preTravelDG(root.left, list);
        //遍历右子树
        preTravelDG(root.right, list);
    }

(2)中序遍历:

先遍历左子树,在打印中间结点,最后遍历右子树

【13,16,22,28,29,30,42】

//中序遍历
    public void midTravel() {
        List<AbstractMap.SimpleEntry<T, Integer>> list = new ArrayList<>();
        midTravelDG(this.root, list);
        String str = list.stream().map(item -> item.toString()).collect(Collectors.joining("-"));
        System.out.println(str);
    }

//中序遍历以root为根的树,讲解稿保存在list中
    private void midTravelDG(Node<T> root, List<AbstractMap.SimpleEntry<T, Integer>> list) {
        //递归终止条件
        if (root == null) {
            return;
        }
        //递归操作
        //遍历左子树
        preTravelDG(root.left, list);
        list.add(new AbstractMap.SimpleEntry<>(root.ele, root.frequence));
        //遍历右子树
        preTravelDG(root.right, list);
    }

(3)后序遍历:

先遍历左子树,在遍历右子树,最后在打印中间结点

【13,22,16,29,42,30,28】

 //后序遍历
    public void sufTravel() {
        List<AbstractMap.SimpleEntry<T, Integer>> list = new ArrayList<>();
        sufTravelDG(this.root, list);
        String str = list.stream().map(item -> item.toString()).collect(Collectors.joining("-"));
        System.out.println(str);
    }

 //后序遍历以root为根的树,讲解稿保存在list中
    private void sufTravelDG(Node<T> root, List<AbstractMap.SimpleEntry<T, Integer>> list) {
        //递归终止条件
        if (root == null) {
            return;
        }
        //递归操作
        //遍历左子树
        preTravelDG(root.left, list);
        //遍历右子树
        preTravelDG(root.right, list);
        list.add(new AbstractMap.SimpleEntry<>(root.ele, root.frequence));
    }

可以看到,先中后序遍历的代码区别只是在递归最后将元素添加到list的位置不同而已

(4)层序遍历:

一层一层的打印

【28,16,30,13,22,29,42】

//层序遍历
    public void levelTravel() {
        //判断树是否为空
        if (this.isEmpty()) {
            return;
        }
        Queue<AbstractMap.SimpleEntry<Node<T>, Integer>> queue = new LinkedList<>();
        //1.先将根结点入队
        queue.add(new AbstractMap.SimpleEntry<>(this.root, 1));
        //2.遍历队列
        while (!queue.isEmpty()) {
            //2-1.出队
            AbstractMap.SimpleEntry<Node<T>, Integer> pair = queue.poll();
            //结点
            Node<T> node = pair.getKey();
            //层
            int level = pair.getValue();
            ;
            System.out.println("[val:" + node.ele + ",level:" + level + "]");
            //2-2.判断左右子树是否为空
            if (node.left != null) {
                queue.add(new AbstractMap.SimpleEntry<>(node.left, level + 1));
            }
            if (node.right != null) {
                queue.add(new AbstractMap.SimpleEntry<>(node.right, level + 1));
            }
        }
    }

6.删除操作

删除的操作中,需要注意删除后二分搜索树也会因此改变,所以要分情况讨论

(1)删除最小元素

删除最小元素并不需要改变树,只需要失去关联关系即可

 //从树中删除最小的结点
    public T removeMinNode() {
        T result = getMinValue();
        if (result == null) {
            return null;
        }
        //更新根结点
        this.root = removeMinNode(this.root);
        return result;
    }

    //语义:从以Node为根的二分搜索树中删除元素最小的结点
    private Node<T> removeMinNode(Node<T> node) {
        //递归终止条件
        if (node.left == null) {
            //删除操作
            //1.记录右子树
            Node<T> rightTree = node.right;
            //失去关联关系
            node.right = null;
            //3.跟新size
            this.size--;
            return rightTree;
        }
        //递归操作
        node.left = removeMinNode(node.left);
        return node;
    }

(2)删除最大元素

跟删除最小元素一样,只需要失去关联关系即可

//从树中删除最大的结点
    public T removeMaxNode() {
        T result = getMaxValue();
        if (result == null) {
            return null;
        }
        //更新根结点
        this.root = removeMaxNode(this.root);
        return result;
    }

    //语义:从以Node为根的二分搜索树中删除元素最大的结点
    private Node<T> removeMaxNode(Node<T> node) {
        //递归终止条件
        if (node.right == null) {
            //删除操作
            //1.记录左子树
            Node<T> leftTree = node.left;
            //失去关联关系
            node.left = null;
            //3.跟新size
            this.size--;
            return leftTree;
        }
        //递归操作
        node.right = removeMaxNode(node.right);
        return node;
    }

(3)删除任意元素

在删除任意元素中,需要考虑删除结点有没有左右子树

//语义:从以Node为根的二分搜索树中删除值为ele的结点
    private Node<T> remove(Node<T> node, T ele) {
        //递归终止的条件
        //没有找到
        if (node == null) {
            return null;
        }
        //找到了
        if (node.ele.compareTo(ele) == 0) {
            this.size--;
            //Node就是要删除的结点
            if (node.left == null) {
                Node<T>rightNode=node.right;
                node.right=null;
                return rightNode;
            } else if (node.right == null) {
                Node<T>leftNode=node.left;
                node.left=null;
                return leftNode;
            } else {
                Node<T> suffixNode = getMinNode(node.right).get();
                suffixNode.right=removeMinNode(node.right);
                suffixNode.left=node.left;
                this.size++;
                //失去关联关系
                node.left=node.right=null;
                return suffixNode;
            }
        }
        //递归操作
        if (node.ele.compareTo(ele) > 0) {
            node.left = remove(node.left, ele);
        } else {
            node.right = remove(node.right, ele);
        }
        return node;
    }

(4)删除根节点

直接删除关联关系即可

 //删除根节点
    public void removeRoot(){
        if(this.root==null){
            return;
        }
        remove(this.root.ele);
    }

四、完整代码

package com.algo.lesson.lesson04;

import java.util.*;
import java.util.stream.Collectors;

//二分搜索树
/*
保存到结点中的元素值必须具有可比性
 */
public class BinearySeachTree<T extends Comparable<T>> {
    //树的结点
    private static class Node<T> {
        private final T ele;//结点的值
        private int frequence;//频率
        private Node<T> left, right;//分别指向左右孩子的索引

        public Node(T ele) {
            this.ele = ele;
            this.left = this.right = null;
        }

    }

    //树对应的属性
    private Node<T> root;//树的根节点
    private int size;//结点的个数

    //构建树
    public BinearySeachTree() {
        this.root = null;
        this.size = 0;
    }

    //获取树中结点的个数
    public int getSize() {
        return this.size;
    }

    //向树中添加结点
    public void add(T ele) {
        //更新根结点
        this.root = addDG(this.root, ele);
    }

    //语义:向以root为根的二分搜索树中添加元素ele
    private Node<T> addDG(Node<T> root, T ele) {
        //递归终止条件
        if (root == null) {
            this.size++;
            return new Node<T>(ele);
        }
        //递归操作
        if (root.ele.compareTo(ele) > 0) {
            root.left = addDG(root.left, ele);
        } else if (root.ele.compareTo(ele) < 0) {
            root.right = addDG(root.right, ele);
        } else {
            //更新频率
            root.frequence++;
        }
        return root;
    }

    //查询的方法
    public boolean search(T ele) {
        return searchDG(this.root, ele);
    }

    //语义:从以root为根的二分搜索树中查找元素ele
    private boolean searchDG(Node<T> root, T ele) {
        //递归终止的条件
        if (root == null) {
            return false;
        }
        //递归操作
        if (root.ele.compareTo(ele) == 0) {
            return true;
        } else if (root.ele.compareTo(ele) > 0) {
            return searchDG(root.left, ele);
        } else {
            return searchDG(root.right, ele);
        }
    }

    //二分搜索树的遍历

    //前序遍历
    public void preTravel() {
        List<AbstractMap.SimpleEntry<T, Integer>> list = new ArrayList<>();
        preTravelDG(this.root, list);
        String str = list.stream().map(item -> "[" + item.getKey() + ":" + item.getValue() + "]").collect(Collectors.joining("-"));
        System.out.println(str);
    }

    //中序遍历
    public void midTravel() {
        List<AbstractMap.SimpleEntry<T, Integer>> list = new ArrayList<>();
        midTravelDG(this.root, list);
        String str = list.stream().map(item -> item.toString()).collect(Collectors.joining("-"));
        System.out.println(str);
    }

    //后序遍历
    public void sufTravel() {
        List<AbstractMap.SimpleEntry<T, Integer>> list = new ArrayList<>();
        sufTravelDG(this.root, list);
        String str = list.stream().map(item -> item.toString()).collect(Collectors.joining("-"));
        System.out.println(str);
    }

    //前序遍历以root为根的树,讲解稿保存在list中
    private void preTravelDG(Node<T> root, List<AbstractMap.SimpleEntry<T, Integer>> list) {
        //递归终止条件
        if (root == null) {
            return;
        }
        //递归操作
        list.add(new AbstractMap.SimpleEntry<>(root.ele, root.frequence));
        //遍历左子树
        preTravelDG(root.left, list);
        //遍历右子树
        preTravelDG(root.right, list);
    }

    //中序遍历以root为根的树,讲解稿保存在list中
    private void midTravelDG(Node<T> root, List<AbstractMap.SimpleEntry<T, Integer>> list) {
        //递归终止条件
        if (root == null) {
            return;
        }
        //递归操作
        //遍历左子树
        preTravelDG(root.left, list);
        list.add(new AbstractMap.SimpleEntry<>(root.ele, root.frequence));
        //遍历右子树
        preTravelDG(root.right, list);
    }

    //后序遍历以root为根的树,讲解稿保存在list中
    private void sufTravelDG(Node<T> root, List<AbstractMap.SimpleEntry<T, Integer>> list) {
        //递归终止条件
        if (root == null) {
            return;
        }
        //递归操作
        //遍历左子树
        preTravelDG(root.left, list);
        //遍历右子树
        preTravelDG(root.right, list);
        list.add(new AbstractMap.SimpleEntry<>(root.ele, root.frequence));
    }

    //判断树是否为空
    public boolean isEmpty() {
        return this.size == 0;
    }

    //层序遍历
    public void levelTravel() {
        //判断树是否为空
        if (this.isEmpty()) {
            return;
        }
        Queue<AbstractMap.SimpleEntry<Node<T>, Integer>> queue = new LinkedList<>();
        //1.先将根结点入队
        queue.add(new AbstractMap.SimpleEntry<>(this.root, 1));
        //2.遍历队列
        while (!queue.isEmpty()) {
            //2-1.出队
            AbstractMap.SimpleEntry<Node<T>, Integer> pair = queue.poll();
            //结点
            Node<T> node = pair.getKey();
            //层
            int level = pair.getValue();
            ;
            System.out.println("[val:" + node.ele + ",level:" + level + "]");
            //2-2.判断左右子树是否为空
            if (node.left != null) {
                queue.add(new AbstractMap.SimpleEntry<>(node.left, level + 1));
            }
            if (node.right != null) {
                queue.add(new AbstractMap.SimpleEntry<>(node.right, level + 1));
            }
        }
    }

    //找树中的最小元素
    public T getMinValue() {
        if (this.isEmpty()) {
            return null;
        }
        Optional<Node<T>> optional = getMinNode();
        return optional.get().ele;
    }

    //找树中的最大元素
    public T getMaxValue() {
        if (this.isEmpty()) {
            return null;
        }
        Optional<Node<T>> optional = getMaxNode(this.root);
        return optional.get().ele;

    }

    private Optional<Node<T>> getMinNode() {
        if (this.root == null) {
            return Optional.empty();
        }
        //一直向左查找
        Node<T> node = this.root;
        while (node.left != null) {
            node = node.left;
        }
        return Optional.of(node);
    }

    //递归
    //语义:在以Node为根结点的树中查找最小结点
    private Optional<Node<T>> getMinNode(Node<T> node) {
        if (node.left == null) {
            return Optional.of(node);
        }
        return getMinNode(node.left);
    }

    //语义:在以Node为根结点的树中查找最大结点
    private Optional<Node<T>> getMaxNode(Node<T> node) {
        if (node.right == null) {
            return Optional.of(node);
        }
        return getMaxNode(node.right);
    }

    //删除操作
    //从树中删除最小的结点
    public T removeMinNode() {
        T result = getMinValue();
        if (result == null) {
            return null;
        }
        //更新根结点
        this.root = removeMinNode(this.root);
        return result;
    }

    //语义:从以Node为根的二分搜索树中删除元素最小的结点
    private Node<T> removeMinNode(Node<T> node) {
        //递归终止条件
        if (node.left == null) {
            //删除操作
            //1.记录右子树
            Node<T> rightTree = node.right;
            //失去关联关系
            node.right = null;
            //3.跟新size
            this.size--;
            return rightTree;
        }
        //递归操作
        node.left = removeMinNode(node.left);
        return node;
    }

    //删除操作
    //从树中删除最大的结点
    public T removeMaxNode() {
        T result = getMaxValue();
        if (result == null) {
            return null;
        }
        //更新根结点
        this.root = removeMaxNode(this.root);
        return result;
    }

    //语义:从以Node为根的二分搜索树中删除元素最大的结点
    private Node<T> removeMaxNode(Node<T> node) {
        //递归终止条件
        if (node.right == null) {
            //删除操作
            //1.记录左子树
            Node<T> leftTree = node.left;
            //失去关联关系
            node.left = null;
            //3.跟新size
            this.size--;
            return leftTree;
        }
        //递归操作
        node.right = removeMaxNode(node.right);
        return node;
    }

    //删除任意结点
    public void remove(T ele) {
        //根据值查找结点
        this.root = remove(this.root, ele);
    }

    //语义:从以Node为根的二分搜索树中删除值为ele的结点
    private Node<T> remove(Node<T> node, T ele) {
        //递归终止的条件
        //没有找到
        if (node == null) {
            return null;
        }
        //找到了
        if (node.ele.compareTo(ele) == 0) {
            this.size--;
            //Node就是要删除的结点
            if (node.left == null) {
                Node<T>rightNode=node.right;
                node.right=null;
                return rightNode;
            } else if (node.right == null) {
                Node<T>leftNode=node.left;
                node.left=null;
                return leftNode;
            } else {
                Node<T> suffixNode = getMinNode(node.right).get();
                suffixNode.right=removeMinNode(node.right);
                suffixNode.left=node.left;
                this.size++;
                //失去关联关系
                node.left=node.right=null;
                return suffixNode;
            }
        }
        //递归操作
        if (node.ele.compareTo(ele) > 0) {
            node.left = remove(node.left, ele);
        } else {
            node.right = remove(node.right, ele);
        }
        return node;
    }

    //删除根节点
    public void removeRoot(){
        if(this.root==null){
            return;
        }
        remove(this.root.ele);
    }

}

五、例题

1.700. 二叉搜索树中的搜索

​​​​数据结构——用Java实现二分搜索树,数据结构

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null){
            return null;
        }
        if(val==root.val){
            return root;
        }
        return searchBST(val<root.val?root.left:root.right,val);
    }
}

2.力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

数据结构——用Java实现二分搜索树,数据结构

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
//更新根结点
        return root = addDG(root, val);
    }

    //语义:向以root为根的二分搜索树中添加元素ele
    private TreeNode addDG(TreeNode root, int val) {
        //递归终止条件
        if (root == null) {
            return new TreeNode(val);
        }
        //递归操作
        if (root.val>val) {
            root.left = addDG(root.left, val);
        } else if (root.val<val) {
            root.right = addDG(root.right, val);
        }
        return root;
    }
}

3.力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

数据结构——用Java实现二分搜索树,数据结构文章来源地址https://www.toymoban.com/news/detail-827952.html

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int temp = queue.size();
            for (int i = 1; i <= temp; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            list.add(level);
        }
        return list;
    }
}

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

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

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

相关文章

  • Java 数据结构篇-实现二叉搜索树的核心方法

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍   文章目录         1.0 二叉搜索树的概述         2.0 二叉搜索树的成员变量及其构造方法         3.0 实现二叉树的核心接口         3.1 实现二叉搜索树 - 获取值 get(int key)         3.2 实现二叉搜索树

    2024年02月04日
    浏览(51)
  • Java数据结构与算法:查找算法之二分查找

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,欢迎回到本专栏。在这个冰冷的季节里,我们将一同探讨Java中一种高效的查找算法——二分查找。让我们点燃知识的火花,一同解锁这个查找奇迹的秘密! 二分查找简介 二分查找,也称为折半查找,

    2024年01月21日
    浏览(45)
  • 【数据结构与算法】python实现二分查找

    二分查找 又称折半查找,它是一种效率较高的查找方法 原理:首先,假设表中元素是按升序排列,将表中间位置记录的与查找比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的大于查找,则

    2024年02月05日
    浏览(40)
  • 数据结构-查找(顺序查找与二分查找的讲解与代码实现)

    顺序查找概念:从表的另一端开始,一次将记录的和给定值进行比较,若某个记录的和给定的值相等,则查找成功,反之则查找失败。 ASL:平均查找长度 pi查找概率,ci查找次数 eg:序列1,2,3 查找1的次数为1概率为1/3,2为两次概率1/3,3的次数为3概率1/3  将12

    2024年02月06日
    浏览(68)
  • Java数据结构与算法:二叉搜索树

    Java数据结构与算法:二叉搜索树 大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 在计算机科学中,二叉搜索树(Binary Search Tree,简称BST)是一种常见的树形数据结构,它具有良好的查找和插入性能。每

    2024年01月24日
    浏览(43)
  • 【数据结构】 二叉搜索树的实现

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 比如以下就为一个人二叉搜

    2024年02月09日
    浏览(36)
  • 数据结构:二叉搜索树(非递归实现)

    目录 1、二叉搜索树 2、二叉搜索树的相关操作。 1、查找 2、插入 3、删除 3、代码实现(非递归) 二叉搜索树(Binary Search Tree,简称BST)是一种特殊的二叉树,其中每个节点的值大于其左子树中所有节点的值,小于其右子树中所有节点的值。这种特性使得二叉搜索树具有快速

    2024年03月08日
    浏览(33)
  • 【数据结构】搜索二叉树(C++实现)

    ​ ​📝个人主页:@Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯 长路漫漫浩浩,万事皆有期待 上一篇博客:【C++】C++模板进阶 —— 非类型模板参数、模板的特化以及模板的分离编译 二叉搜索树又称二叉排序树,它或者是一棵空

    2024年02月07日
    浏览(51)
  • 【数据结构】搜索树 与 Java集合框架中的Set,Map

    作者主页:paper jie_博客 本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于《JAVA数据结构》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将javaSE基础知识一网打尽,希望可以帮到读者们哦。 其他专栏:《

    2024年02月08日
    浏览(37)
  • 【数据结构】—搜索二叉树(C++实现,超详细!)

                                                           🎬 慕斯主页 : 修仙—别有洞天                                                        ♈️ 今日夜电波 :消えてしまいそうです—真夜中                                              

    2024年02月05日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包