当前位置：首页 > news >正文

二叉搜索树（TreeMapTreeSet）

news 来源：原创 2025/8/2 17:00:38

文章目录

- 1.概念
- 2.二叉搜索树的底层代码实现
- - (1)首先构建二叉树
  - (2)实现插入功能；
  - (3)实现查找
  - (4)删除（重点）
- 3.TreeMap

1.概念

TreeMap&TreeSet都是有序的集合都是基于二叉搜索树来实现的
二叉搜索树：是一种特殊的二叉树
若左子树不为空，则左子树上的所有节点都小于根节点
若右子树不为空，则右子树上的所有节点都大于根节点
所有左右子树都满足这个条件
在这里插入图片描述

2.二叉搜索树的底层代码实现

(1)首先构建二叉树

 public class Node {public int val;public Node left;public Node right;public Node(int val) {this.val = val;}}public Node root;

(2)实现插入功能；

分两种情况树是否为空树
当子树为空树直接插入
当子树不为空按照条件限制进行插入
在这里插入图片描述

public void cha(int val) {Node cut = new Node(val);if (root == null) {root = cut;}Node cur = root;Node parter = null;while (cur != null) {if (cut.val > cur.val) {parter = cur;cur = cur.right;} else if (val == cur.val) {//如果树中已经含有val数据则直接退出return;} else {parter = cur;cur = cur.left;}}if (parter.val < cut.val) {//不能使用parter.left(right)！=null去判断两边都是null直接后续插入不了parter.right = cut;} else {parter.left = cut;}}

插入第一张图1~9测试一下

   public static void main(String[] args) {int []arr={5,3,4,1,7,8,2,6,0,9};BinarySearchTree binarySearchTree=new BinarySearchTree();for (int i=0;i< arr.length;i++){binarySearchTree.cha(arr[i]);}}

在这里插入图片描述

(3)实现查找

若根节点不为空
当根节点.val==val 返回true
当根节点.val>val 去左子树找
当根节点.val<val 去右子树找

 public boolean jc(int val) {Node cur = root;while (cur != null) {if (val < cur.val) {cur = cur.left;} else if (val > cur.val) {cur = cur.right;} else {return true;}}return false;}

在这里插入图片描述

(4)删除（重点）

设删除节点为cur，删除节点的双亲节点为parter
分三大方向
(一）：当cur.left==null

1.当cur==root时root=root.right

2.cur!=null时
当parter.left==cur
parte.left=cur.right;

当parter.right==cur
parte.right=cur.right;

(二):当cur.right==null

1.当cur==root时root=root.left

2.cur!=null时
当parter.left==cur
parte.left=cur.left;

当parter.right==cur
parte.right=cur.left;
(三)cur.left!=null&&cur.right!=null
需要使⽤替换法进⾏删除，即在它的右⼦树中寻找中序下的第⼀个结点(关键码最⼩)，⽤它的值填补到被删除节点中，再来处理该结点的删除问题

代码：

 public void remove(int val) {Node cut = new Node(val);Node cur = root;Node parter = null;while (cur != null) {if (cut.val > cur.val) {parter = cur;cur = cur.right;} else if (val < cur.val) {parter = cur;cur = cur.left;} else {delet(parter,cur);return;}}}public void delet(Node parter,Node cur){if(cur.right==null){if(cur==root){root=root.left;}if(parter.left==cur){parter.left=cur.left;}if(parter.right==cur){parter.right=cur.left;}}else if(cur.left==null){if(cur==root){root=root.right;}if(parter.left==cur){parter.left=cur.right;}if(parter.right==cur){parter.right=cur.right;}}else {Node target=cur.right;Node ptarget=cur;while (target.left!=null){ptarget=target;target=target.left;}cur.val=target.val;if(ptarget.left==target){ptarget.left=target.right;}else {ptarget.right=target.right;}}

在这里插入图片描述

3.TreeMap

MapMap是⼀个接⼝，不能直接实例化对象，如果要实例化对象可以实例化其实现类TreeMap

public static void main(String[] args) {Map<String ,Integer>map=new TreeMap<>();map.put("认知觉醒",68);map.put("西游记",66);map.put("骆驼祥子",58);System.out.println(map.get("认知觉醒"));//找到就返回对应的value没找到就返回所赋的默认值System.out.println(map.getOrDefault("红楼梦",0));//返回不重复的集合   根据key的大小进行排序System.out.println(map.keySet());map.put("西游记",44);//value可覆盖System.out.println(map.values());System.out.println(map.containsKey("被讨厌的勇气"));System.out.println(map.containsValue(55));//返回所key与value对应关系Map<String,Integer>map2=new TreeMap<>();String[]arr={"a","b","c","d","a","b","c"};for (String s:arr){if(!map2.containsKey(s)){map2.put(s,1);}else {int temp=map2.get(s);map2.put(s,temp+1);}}for (Map.Entry<String, Integer> entry:map2.entrySet()){System.out.println("该字母是"+entry.getKey()+"出现了"+entry.getValue()+"次");}}

在这里插入图片描述

4.TreeSet
Set继承Collection的接口类

  public static void main(String[] args) {//Set继承了Collection接口Set<String> set=new TreeSet<>();set.add("西游记");set.add("认知觉醒");set.add("骆驼祥子");set.add("西游记");//重复元素不被添加System.out.println(set.toString());System.out.println(set.contains("Sv"));//返回迭代器for (Iterator<String> iterator=set.iterator();iterator.hasNext();){String temp= iterator.next();System.out.println(temp);}System.out.println(set.size());System.out.println(set.isEmpty());int[]arr=new int[set.size()];for (int i = 0; i <set.size() ; i++) {System.out.println(set);}String []arr1={"西游记","认知觉醒","骆驼祥子","红楼梦"};//判断结合arr1中的元素在set中是否存在System.out.println(set.containsAll(Arrays.asList(arr1)));System.out.println();for (int i = 0; i <arr1.length ; i++) {//判断set中是否含有arr1[i]元素  且将set不含的元素添加进去System.out.println(set.addAll(Collections.singleton((arr1[i]))));}System.out.println(set.toString());set.remove("西游记");System.out.println(set.toString());//清空元素set.clear();System.out.println(set.toString());}

在这里插入图片描述

文章目录

1.概念

2.二叉搜索树的底层代码实现

(1)首先构建二叉树

(2)实现插入功能；

(3)实现查找

(4)删除（重点）

3.TreeMap

相关文章：