网站结构布局,500m主机空间能做视频网站吗,科技创新与应用,网站建设开发案例教程视频目录
1.二叉搜索树
1.1二叉搜索树的介绍
1.2.二叉搜索树的实现
1.2.1二叉搜索树的创建
1.2.2查找关键字 1.2.3插入 1.2.4删除 1.3二叉搜索树的性能分析
2.Map Map官方文档 2.1Map 的常用方法说明
2.2关于Map.Entry的说明, 2.3注意事项
2.4reeMap和HashMap的区别
…目录
1.二叉搜索树
1.1二叉搜索树的介绍
1.2.二叉搜索树的实现
1.2.1二叉搜索树的创建
1.2.2查找关键字 1.2.3插入 1.2.4删除 1.3二叉搜索树的性能分析
2.Map Map官方文档 2.1Map 的常用方法说明
2.2关于Map.Entry的说明, 2.3注意事项
2.4reeMap和HashMap的区别
3.Set
3.1常见方法说明 3.2注意事项
3.3TreeSet和HashSet的区别 1.二叉搜索树
1.1二叉搜索树的介绍 二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树 : 1若它的左子树不为空则左子树上所有节点的值都小于根节点的值 2若它的右子树不为空则右子树上所有节点的值都大于根节点的值 3它的左右子树也分别为二叉搜索树 比如以下
int[] array {5,3,4,1,7,8,2,6,0,9}; 1.2.二叉搜索树的实现
1.2.1二叉搜索树的创建
public class BinarySearchTree {class TreeNode {public int val ;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val val;}}public TreeNode root;//根节点
}
1.2.2查找关键字
步骤 若根节点不为空 如果根节点key查找key返回true如果根节点key 查找key在其左子树查找如果根节点key 查找key在其右子树查找 找不到返回false 代码 public boolean search(int key) {TreeNode cur root;while (cur ! null) {if (cur.val key){return true;} else if (cur.valkey) {curcur.left;}else{curcur.right;}}return false;} 1.2.3插入
插入操作可以分为以下两种情况
1如果树为空树即根 null直接插入
2如果树不是空树按照查找逻辑确定插入位置插入新结点
那怎么找合适位置呢 如果节点root.valval该值在搜索数中已经存在无需插入return flase;如果节点root.valval在其左子树找合适位置如果节点root.valval在其右子树找合适位置 代码 public boolean insert(int val) {TreeNode treeNode new TreeNode(val);if (root null) {roottreeNode;return true;}TreeNode curroot;TreeNode parent null;while(cur!null){if (cur.val val) {return false;} else if (cur.val val) {parentcur;cur cur.left;} else {parentcur;cur cur.right;}}if(parent.valval){parent.lefttreeNode;}else {parent.righttreeNode;}return true;} 1.2.4删除 设待删除结点为 cur, 待删除结点的双亲结点为 parent 1. cur.left null 1 cur 是 root 则 root cur.right 2 cur 不是 rootcur 是 parent.left则 parent.left cur.right 3 cur 不是 rootcur 是 parent.right则 parent.right cur.right 2. cur.right null 1 cur 是 root 则 root cur.left 2 cur 不是 root cur 是 parent.left 则 parent.left cur.left 3 cur 不是 root cur 是 parent.right 则 parent.right cur.left 这里与1. cur.left null大同小异不做过多解释 3. cur.left ! null cur.right ! null 步骤 我们使用target来遍历寻找子树中关键节点targetParent用来记录target的父亲节点 找到相应节点后与待删除的cur节点的值进行替换最后删除target结点即可 例子 代码 public void remove(int val) {TreeNode cur root;TreeNode parent null;while (cur ! null) {if (val cur.val) {removeNode(parent, cur);break;} else if (val cur.val) {parent cur;cur cur.left;} else {parent cur;cur cur.right;}}}private void removeNode(TreeNode parent, TreeNode cur) {if (cur.leftnull){if(curroot){rootcur.right;}else if(parent.leftcur){parent.leftcur.right;}else{parent.rightcur.right;}} else if (cur.rightnull) {if(curroot){rootcur.left;}else if(parent.leftcur){parent.leftcur.left;}else{parent.rightcur.left;}}else{TreeNode target cur.right;TreeNode targetParent cur;while(target.left!null){targetParent target;target target.left;}if(targetParent.lefttarget){targetParent.lefttarget.right;}else{targetParent.righttarget.right;}}} 1.3二叉搜索树的性能分析 插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有 n 个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度 的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 2.Map
Map官方文档 Map 是一个接口类该类没有继承自 Collection 该类中存储的是 K,V 结构的键值对并且 K 一定是唯一的不 能重复 。 2.1Map 的常用方法说明 举例部分方法 public class TestMap {public static void main(String[] args) {MapString,Integer mapnew TreeMap();map.put(wang,1);map.put(zhang,3);map.put(li,5);System.out.println(map);//{li5, wang1, zhang3}// GetOrDefault(): 如果key存在返回与key所对应的value如果key不存在返回一个默认值System.out.println(map.getOrDefault(wang,0));//1System.out.println(map.getOrDefault(abcdef,0));//0// 返回所有 key 的不重复集合Set keysmap.keySet();System.out.println(keys);//[li, wang, zhang]//返回所有 value 的可重复集合Collection vals map.values();System.out.println(vals);//[5, 1, 3]// 打印所有的键值对// entrySet(): 将Map中的键值对放在Set中返回了for(Map.EntryString, Integer entry : map.entrySet()){System.out.println(entry.getKey() --- entry.getValue());}//li---5//wang---1//zhang---3}} 2.2关于Map.EntryK, V的说明 Map.EntryK, V 是 Map 内部实现的用来存放 key, value 键值对映射关系的内部类 该内部类中主要提供了 key, value的获取 value 的设置以及 Key 的比较方式。 注意Map.EntryK,V并没有提供设置Key的方法 2.3注意事项 1. Map 是一个接口不能直接实例化对象 如果 要实例化对象只能实例化其实现类 TreeMap 或者 HashMap 2. Map 中存放键值对的 Key 是唯一的 value 是可以重复的 3. 在 TreeMap 中插入键值对时 key 不能为空否则就会抛 NullPointerException 异常 value 可以为空。但 是HashMap 的 key 和 value 都可以为空。 4. Map 中的 Key 可以全部分离出来存储到 Set 中 来进行访问 ( 因为 Key 不能重复 ) 5. Map 中的 value 可以全部分离出来存储在 Collection 的任何一个子集合中 (value 可能有重复 ) 。 6. Map 中键值对的 Key 不能直接修改 value 可以修改如果要修改 key 只能先将该 key 删除掉然后再来进行 重新插入。 2.4reeMap和HashMap的区别 3.Set
Set官方文档
Set与Map主要的不同有两点Set是继承自Collection的接口类Set中只存储了Key。 set的底层是map 3.1常见方法说明 举例部分方法
public class TextSet {public static void main(String[] args) {SetString setnew TreeSet();// add(key): 如果key不存在则插入返回ture// 如果key存在返回falseset.add(wang);set.add(hang);set.add(li);IteratorString itset.iterator();while(it.hasNext()){System.out.println(it.next());}//hang//li//wang}
}3.2注意事项 1. Set 是继承自 Collection 的一个接口类 2. Set 中只存储了 key 并且要求 key 一定要唯一 3. TreeSet 的底层是使用 Map 来实现的其使用 key 与 Object 的一个默认对象作为键值对插入到 Map 中的 4. Set 最大的功能就是对集合中的元素进行去重 5. 实现 Set 接口的常用类有 TreeSet 和 HashSet 还有一个 LinkedHashSet LinkedHashSet 是在 HashSet 的基础 上维护了一个双向链表来记录元素的插入次序。 6. Set 中的 Key 不能修改如果要修改先将原来的删除掉然后再重新插入 7. TreeSet 中不能插入 null 的 key HashSet 可以。 3.3TreeSet和HashSet的区别 以上为我个人的小分享如有问题欢迎讨论
都看到这了不如关注一下给个免费的赞
