Java教程

数据结构Java版Map&Set&搜索树

本文主要是介绍数据结构Java版Map&Set&搜索树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!


 欢迎来访~

目录

1.搜索

1.1概念及场景

1.2模型

2.Map 的使用

2.1 关于Map的说明

2.2 关于Map.Entry的说明,>

2.3 Map 的常用方法说明

3. Set 的说明

3.1常见方法说明

4.搜索树

4.1概念

4.2搜索树的查找

4.3搜索树的插入

4.4搜索树的删除


1.搜索

1.1概念及场景

①Map和Set的作用: 一种专门用来进行搜索的容器或者数据结构,其搜索的效率与其具体的实例化子类有关 。 ②Map和Set相比于其他类型的优点: 之前我们学过的常见搜索方式有:  直接遍历, 二分查找等 上述排序比较适合静态类型的查找,即一般不会对区间进行插入和删除操作了,而现实中的查找比如: 1. 根据姓名查询考试成绩 2. 通讯录,即根据姓名查询联系方式 3. 不重复集合,即需要先搜索关键字是否已经在集合中 可能在查找时进行一些插入和删除的操作,即动态查找,那上述两种方式就不太适合了,本节介绍的 Map 和 Set 是 一种适合 动态查找的集合容器 。

1.2模型

1. 纯 key 模型:

eg.有一个英文词典,快速查找一个单词是否在词典中 ;快速查找某个名字在不在通讯录中

2.Key-Value 模型: eg.统计文件中每个单词出现的次数,统计结果是每个单词都有与其对应的次数:<单词,单词出现的次数 > ;梁山好汉的江湖绰号:每个好汉都有自己的江湖绰号 而 Map中存储的就是key-value的键值对,Set中只存储了Key

2.Map 的使用

2.1 关于Map的说明

Map是一个接口类,该类没有继承自Collection,该类中存储的是<K,V>结构的键值对,并且K一定是唯一的,不能重复。(当后续出现重复的key值时,原来的value将会被替代)

解释图如下:(当后续出现重复的key值时,原来的value将会被替代)

2.2 关于Map.Entry<K, V>的说明

①内在结构:

Map.Entry<K, V> Map内部实现的用来存放<key, value>键值对映射关系的内部类,该内部类中主要提供了 <key, value>的获取,value的设置以及Key的比较方式。

将Map.Entry<K, V>中的<K,V>看作一个整体,来进行存储

②常用方法
方法解释
K getKey () 返回 entry 中的 key
V getValue () 返回 entry 中的 value
V setValue(V value) 将键值对中的 value 替换为指定 value

2.3 Map 的常用方法说明

①常用方法说明:
方法解释
V get(Object key) 返回 key 对应的 value
V getOrDefault(Object key, V defaultValue)返回 key 对应的 value,key 不存在,返回默认值
V put(K key, V value)设置 key 对应的 value
V remove(Object key)删除 key 对应的映射关系
Set<K> keySet()返回所有 key 的不重复集合
Collection<V> values()返回所有 value 的可重复集合
Set<Map.Entry<K, V>> entrySet()返回所有的 key-value 映射关系
boolean containsKey(Object key)判断是否包含 key
boolean containsValue(Object value)判断是否包含 value

②使用范例如下: 

③注意事项:

a.Map是一个接口,不能直接实例化对象,如果要实例化对象只能实例化其实现类TreeMap或者HashMap

b.Map中存放键值对的Key是唯一的,value是可以重复的 

c.在Map中插入键值对时,key不能为空,否则就会抛NullPointerException异常,但是value可以为空

d.Map中的value可以全部分离出来,存储在Collection的任何一个子集合中(value可能有重复)。

e.Map中键值对的Key不能直接修改,value可以修改,如果要修改key,只能先将该key删除掉,然后再来进行 重新插入。

3. Set 的说明

Set与Map主要的不同有两点:Set是继承自Collection的接口类,Set中只存储了Key

3.1常见方法说明

①常用方法说明:
方法解释
boolean add(E e)添加元素,但重复元素不会被添加成功
void clear()清空集合
boolean contains(Object o)判断 o 是否在集合中
Iterator<E> iterator()返回迭代器
boolean remove(Object o)删除集合中的 o
int size() 返回set中元素的个数
boolean isEmpty()检测set是否为空,空返回true,否则返回false
Object[] toArray()将set中的元素转换为数组返回
boolean containsAll(Collection<?> c)集合c中的元素是否在set中全部存在,是返回true,否则返回false
boolean addAll(Collection<? extends E> c) 将集合c中的元素添加到set中,可以达到去重的效果

②使用范例如下: 

 ③注意事项:

Set中只存储了key,并且要求key一定要唯一(与Map尤为不同的一点)

4.搜索树

4.1概念

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

①如果它的左子树不为空,则左子树上所有节点的值都小于根节点的值

②如果它的右子树不为空,则右子树上所有节点的值都大于根节点的值

③它的左右子树也分别为二叉搜索树

4.2搜索树的查找

解题思路:

代码如下:

//创建结点
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node(int val) {
        this.val = val;
    }
}

public class BinnarySearchTree {
    public Node root = null;
    public Node search(int value) {
        Node cur = root;
        while (cur != null) {
            if (cur.val < value) {
                cur = cur.right;
            } else if (cur.val == value) {
                return cur;
            } else {
                cur = cur.left;
            }
        }
        return null;//代表没有这个数据
    }

4.3搜索树的插入

解题思路:(与查找二叉树相似)

①查找到该根结点应该存储的位置

②存入该节点 

代码如下:

  public boolean insert(int val) {
        if (root == null) {
            root = new Node(val);
            return true;
        }

        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return false;//不能有相同的数据
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        Node node = new Node(val);
        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        return true;
    }

4.4搜索树的删除(难点)

解题思路:

1. cur.left == null

①cur 是 root ,则 root = cur.right ②cur 不是 root , cur 是 parent.left ,则 parent.left = cur.right ③cur 不是 root, cur 是 parent.right ,则 parent.right = cur.right 2. cur.right == null ①cur 是 root ,则 root = cur.left ②cur 不是 root , cur 是 parent.left ,则 parent.left = cur.left ③cur 不是 root , cur 是 parent.right ,则 parent.right = cur.left

 

3. cur.left != null && cur.right != null(难点)

思路: 需要使用 替换法 进行删除,即在它的右子树中寻找中序下的第一个结点 ( 关键码最小 ) ,用它的值填补到被删除节点中,再来处理该结点的删除问题

整体代码如下:

//创建节点
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node(int val) {
        this.val = val;
    }
}
public void remove(int key) {
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if(cur.val == key) {
                //这里开始删除
                removeNode(cur,parent);
                break;
            }else if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

    public void removeNode(Node cur,Node parent) {
        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 = cur.left;
            }
        }else {
            Node targetParent = cur;
            Node target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if(target == targetParent.left) {
                targetParent.left = target.right;
            }else {
                targetParent.right = target.right;
            }
        }
    }
//中序遍历
    public void inOrder(Node root) {
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

 感谢观看~

这篇关于数据结构Java版Map&Set&搜索树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!