-
数据结构--------二叉排序树
2021-02-16 15:55:02二叉排序树 先看一个需求 给你一个数列(7,3, 10, 12,5,1,9),要求能够高效的完成对数据的查询和添加。 方案我们一般首先会想到数组的方式 ...我们前面说到树存储可以有效解决,到底是为什么呢? 二叉排序树 介绍二叉排序树
先看一个需求
给你一个数列(7,3, 10, 12,5,1,9),要求能够高效的完成对数据的查询和添加。
方案我们一般首先会想到数组的方式
数组未排序,优点:直接在数组尾添加,速度快。缺点:查找速度慢.
数组排序,优点:可以使用二分查找,查找速度快,缺点:为了保证数组有序在添加新数据时,找到插入位置后,后面的数据需整体移动,速度慢。链式存储呢?
不管链表是否有序,查找速度都慢,添加数据速度比数组快,不需要数据整体
移动。我们前面说到树存储可以有效解决,到底是为什么呢?
二叉排序树
介绍
二叉排序树: BST: (Binary Sort(Search) Tree),对于二叉排序树的任何一个非叶子节点,
要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。
特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点二叉排序树的创建和遍历
package 二叉排序树; public class BinarySortTree { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr= {7,3,10,12,5,1,9}; BinarySortTreeDemo binarySortTree = new BinarySortTreeDemo(); //循环添加节点到二叉树 for (int i = 0; i < arr.length; i++) { binarySortTree.addNode(new Node(arr[i])); } // System.out.println("中序遍历二叉树"); binarySortTree.infixOrder(); } } //创建二叉排序树 class BinarySortTreeDemo{ private Node root; //添加节点的方法 public void addNode(Node node){ if(root == null){ root = node; }else{ root.addNode(node); } } //中序遍历 public void infixOrder(){ if(root != null){ root.infixOrder(); }else{ System.out.println("空树"); } } } class Node{ int value; Node left; Node right; public Node(int value) { super(); this.value = value; } @Override public String toString() { return "Node [value=" + value + "]"; } //添加节点的方法 //递归的形式添加节点,需要满足二叉排序树 public void addNode(Node node){ if(node == null){ return; } //判断传入的节点值,跟当前子树根节点值的关系 if(node.value < this.value){ //如果当前节点的左子节点为空 if(this.left == null){ this.left = node; }else { this.left.addNode(node);//递归添加 } }else{ if(this.right == null){ this.right = node; }else{ this.right.addNode(node); } } } //中序遍历 public void infixOrder(){ if(this.left != null){ this.left.infixOrder(); } System.out.println(this); if(this.right != null){ this.right.infixOrder(); } } }
二叉排序树的删除
这里面有很多情况:
1.删除叶子结点
2.删除只有一颗子树的节点
3.删除有两颗子树的节点
思路
情况一:删除叶子节点
1.需要先找到待删除的节点targetNode
2.找到待删除节点的父节点parent(考虑是否有父节点)
3.判断targetNode是parent的左子节点还是右子节点
4.根据前面,对应删除
情况二:删除只有一颗子树的节点
1.需要先找到待删除的节点targetNode
2.找到待删除节点的父节点parent(考虑是否有父节点)
3.确定targetNode的子节点是左子节点还是右子节点
4.确定targetNode是parent的左子节点还是右子节点
5.如果targetNode有左子节点
1)targetNode是parent的左子节点
parent.left = targetNode = left;
2)targetNode是parent的右子节点
parent.left = targetNode .right;
6.如果targetNode有右子节点同理
情况三:删除有两颗子树的节点
1.需要先找到待删除的节点targetNode
2.找到待删除节点的父节点parent(考虑是否有父节点)
3.从targetNode的右子树找到最小的节点
4.用临时变量将最小节点的值保存起来 temp
5.删除最小节点
6.targetNode.value = temp
删除节点代码
package 二叉排序树; public class BinarySortTree { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr= {7,3,10,12,5,1,9,2}; BinarySortTreeDemo binarySortTree = new BinarySortTreeDemo(); //循环添加节点到二叉树 for (int i = 0; i < arr.length; i++) { binarySortTree.addNode(new Node(arr[i])); } // System.out.println("中序遍历二叉树"); binarySortTree.infixOrder(); //测试删除叶子节点 // binarySortTree.delNode(2); // System.out.println("删除2节点后"); // binarySortTree.infixOrder(); binarySortTree.delNode(10); binarySortTree.infixOrder(); } } //创建二叉排序树 class BinarySortTreeDemo{ private Node root; //添加节点的方法 public void addNode(Node node){ if(root == null){ root = node; }else{ root.addNode(node); } } //中序遍历 public void infixOrder(){ if(root != null){ root.infixOrder(); }else{ System.out.println("空树"); } } //查找要删除的节点 public Node search(int value){ if(root == null){ return null; }else{ return root.search(value); } } //查找待删除节点的父节点 public Node searchParent(int value){ if(root == null){ return null; }else{ return root.searchParent(value); } } //编写方法 /** * 返回最小节点值,并且删除以node为根节点的二叉排序树的最小节点 * @param node 当做一颗二叉排序树的根节点 * @return 返回的以node为根节点的二叉排序树的最小节点的值 */ public int delRightTreeMin(Node node){ Node target = node; //循环查找左子节点,就会找到最小值 while(target.left != null){ target = target.left; } //这是target就指向了最小节点 //删除最小节点 delNode(target.value); return target.value; } //删除叶子结点的方法 public void delNode(int value){ if(root == null){ return; }else{ //1.需要先去找到待删除节点 Node targetNode = search(value); //如果没有找到 if(targetNode == null){ return; } //如果当前这课二叉排序树只有一个节点 if(root.left == null&& root.right == null){ root = null; return; } //去查找targetNode的父节点 Node parent = searchParent(value); //如果待删除的节点是叶子结点 if(targetNode.left == null && targetNode.right == null){ //如果targetNode是parent的左子节点 if(parent.left != null && parent.left.value == targetNode.value){ parent.left = null; }else if(parent.right != null && parent.right.value == targetNode.value){ parent.right = null; } }else if(targetNode.left!=null && targetNode.right != null){ int minValue = delRightTreeMin(targetNode.right); targetNode.value = minValue; }else{ //删除只有一个子树的节点 //如果删除的节点有左子节点 if(targetNode.left != null){ if(parent.left.value == targetNode.value){ parent.left = targetNode.left; }else{ parent.right = targetNode.left; } }else{ //要删除的节点有右子节点 if(parent.left.value == targetNode.value){ parent.left = targetNode.right; }else{ parent.right = targetNode.right; } } } } } } class Node{ int value; Node left; Node right; public Node(int value) { super(); this.value = value; } @Override public String toString() { return "Node [value=" + value + "]"; } /** * 查找待删除的节点 * @param value 待删除节点的值 * @return */ public Node search(int value){ if(value == this.value){ return this; }else if(value < this.value){//应该向左子树递归查找 if(this.left != null){ return this.left.search(value); }else{ return null; } }else{ if(this.right == null){ return null; }else{ return this.right.search(value); } } } /** * 查找待删除节点的父节点 * @param value 待删除节点的值 * @return 返回待删除节点的父节点 */ public Node searchParent(int value){ if((this.left !=null && this.left.value == value) || (this.right != null && this.right.value == value)){ //当前节点就是待删除节点的父节点 return this; }else{ //如果查找的值,小于当前节点的值,且当前节点的左子节点不为空 if(value < this.value && this.left != null){ return this.left.searchParent(value); }else if(value >= this.value && this.right != null){ return this.right.searchParent(value); }else{ return null;//没有找到父节点 } } } //添加节点的方法 //递归的形式添加节点,需要满足二叉排序树 public void addNode(Node node){ if(node == null){ return; } //判断传入的节点值,跟当前子树根节点值的关系 if(node.value < this.value){ //如果当前节点的左子节点为空 if(this.left == null){ this.left = node; }else { this.left.addNode(node);//递归添加 } }else{ if(this.right == null){ this.right = node; }else{ this.right.addNode(node); } } } //中序遍历 public void infixOrder(){ if(this.left != null){ this.left.infixOrder(); } System.out.println(this); if(this.right != null){ this.right.infixOrder(); } } }
注意事项
删除多个节点的时候一定要注意顺序,有的顺序可以正常删除,但是有的顺序会报空指针错误,原因就是删除的顺序有问题,导致我们删除方法中的判断出了问题,就是根节点这个地方,他没有父节点,但是我们判断了,所以在这出错
-
入门学习Linux常用必会60个命令实例详解doc/txt
2011-06-09 00:08:45文件为doc版,可自行转成txt,在手机上看挺好的。 本资源来自网络,如有纰漏还请告知,如觉得还不错,请留言告知后来人,谢谢!!!!! 入门学习Linux常用必会60个命令实例详解 Linux必学的60个命令 Linux提供... -
SQL Server编程必知必会(Amazon全五星评价)--详细书签版
2013-02-06 13:55:1423.2 为什么要使用存储过程 162 23.3 使用存储过程 163 23.3.1 执行存储过程 163 23.3.2 创建存储过程 163 23.3.3 删除存储过程 164 23.3.4 使用参数 164 23.3.5 建立智能存储过程 167 23.4 小结 ... -
MySQL必知必会(Amazon全五星评价)--详细书签版
2013-02-05 16:15:5923.2 为什么要使用存储过程 164 23.3 使用存储过程 165 23.3.1 执行存储过程 165 23.3.2 创建存储过程 165 23.3.3 删除存储过程 167 23.3.4 使用参数 167 23.3.5 建立智能存储过程 170 23.3.6 检查存储过程 ... -
第二大、第三大的数都是4,位置在1、3随便输出哪一个均可。 3.5.3 给40亿个不重复的unsigned int的整数,没排过序的,然后再给几个数,如何快速判断这几个数是否在那40亿个数当中? 3.5.4 在一个文件中有10G个整数...
-
单条消息及群发消息表结构设计改善
2010-02-26 10:58:24消息大于10条时会返回消息的排序为 最新的、最近的。 ============================================================= 针对以上需求,目前设计的表结构主要字段如下: 1)、message_info_t表部分字段... -
Oracle SQL高级编程(资深Oracle专家力作,OakTable团队推荐)--详细书签版
2013-02-04 12:43:52Karen Morton及其团队在本书中提供了专业的方案:先掌握语言特性,再学习Oracle为提升语言效率而加入的支持特性,进而将两者综合考虑并在工作中加以应用。作者通过总结各自多年的软件开发和教学培训经验,与大家... -
Oracle SQL高级编程(资深Oracle专家力作,OakTable团队推荐)--随书源代码
2013-02-04 12:49:33Karen Morton及其团队在本书中提供了专业的方案:先掌握语言特性,再学习Oracle为提升语言效率而加入的支持特性,进而将两者综合考虑并在工作中加以应用。作者通过总结各自多年的软件开发和教学培训经验,与大家... -
c/c++ 学习总结 初学者必备
2009-09-16 08:50:1021、为什么数组名作为参数,会改变数组的内容,而其它类型如int却不会改变变量的值? 答: 当数组名作为参数时,传递的实际上是地址。而其他类型如int作为参数时,由于函数参数值实质上是实参的一份拷贝,被调函数内部对... -
《数据结构 1800题》
2012-12-27 16:52:0310.在下面的程序段中,对x的赋值语句的频度为__t(n)=O(n3)____(表示为 n的函数) FOR i:=1 TO n DO FOR j:=1 TO i DO FOR k:=1 TO j DO x:=x+delta; 【北京工业大学 1999 一、6(2分)】 ... -
数据结构(C++)有关练习题
2008-01-02 11:27:187、 编写一个程序,将10进制数转换为其它(2-9)进制数。可以将要转换的数重复除以基数,然后讲除的余数按反方向排列来实现; 8、 已知A[n]为正数数组,试写出实现下列运算的递归算法; a. 求数组A中的... -
oracle学习文档 笔记 全面 深刻 详细 通俗易懂 doc word格式 清晰 连接字符串
2017-05-06 20:26:52在创建表时,经常会创建该表的主键、外键、唯一约束、Check约束等 语法结构 create table 表名( [字段名] [类型] [约束] ……….. CONSTRAINT fk_column FOREIGN KEY(column1,column2,…..column_n) ... -
C#微软培训教材(高清PDF)
2009-07-30 08:51:17<<page 1>> page begin==================== 目 目目 目 录 录录 录 第一部分 C#语言概述.4 第一章 第一章第一章 第一章 .NET 编 编 编程语言 程语言编程语言 程语言 C#.4 1.1 Microsoft... -
C#微软培训资料
2014-01-22 14:10:17<<page 1>> page begin==================== 目 目目 目 录 录录 录 第一部分 C#语言概述.4 第一章 第一章第一章 第一章 .NET 编 编 编程语言 程语言编程语言 程语言 C#.4 1.1 Microsoft... -
MySQL命令大全
2018-01-15 11:19:171:使用SHOW语句找出在服务器上当前存在什么数据库: mysql> SHOW DATABASES; 2:2、创建一个数据库MYSQLDATA mysql> Create DATABASE MYSQLDATA; 3:选择你所创建的数据库 mysql> USE MYSQLDATA; (按回车键出现... -
MYSQL常用命令大全
2011-05-30 13:31:241:使用SHOW语句找出在服务器上当前存在什么数据库: mysql> SHOW DATABASES; 2:2、创建一个数据库MYSQLDATA mysql> Create DATABASE MYSQLDATA; 3:选择你所创建的数据库 mysql> USE MYSQLDATA; (按回车键出现... -
java常用工具类的使用
2012-03-19 20:11:37Q 老师,时间毫秒值从1970年1月1日0:00.000开始计算,上面示例中10年后应该是1980年1月1日0:00.000,为什么输出结果是:1980年1月1日 8:00呢? A java.util.Date类型表示的是GMT时间,本身输出是国际化输出,... -
2009达内SQL学习笔记
2010-02-10 19:46:58在处理SQL语句时,其中所有的空格都被忽略(空格只用来分开单词,连续多个空格当一个用)。 SQL语句可以在一行上写出,建议多行写出,便于阅读和调试。 多条SQL语句必须以分号分隔。多数DBMS不需要在单条SQL语句后... -
Quartus_II使用教程
2012-11-26 23:20:43电路设计完成后,就是在此编译了,如果前面点选了别的文件为top-level entity不要忘 了设置下,把memory设为top-level entity。 在原理图的设计时,自己可以尝试用用工具栏中的各种辅助工具,比如注释工具,使得 ... -
c++ 面试题 总结
2009-09-16 08:44:40为什么? int n; if (n == 10) // 第一种判断方式 if (10 == n) // 第二种判断方式 如果少了个=号,编译时就会报错,减少了出错的可能行,可以检测出是否少了= -------------------------------------------------... -
SQL查询安全性及性能优化
2012-03-07 20:51:39为什么要优化 开发是对性能考虑不多【技术差、项目工期紧等原因没有考虑性能问题】 系统运行中,数据量扩大,访问量增多,蹩脚的SQL危害开始显露 低效SQL的危害 系统响应变慢,软件开发中的8秒定律,当打开一个... -
用来排序时应当先根据拼音前缀的首字母来排序,相同的再根据前缀+名称进行排序 pinyin string name的完整拼音 ext_id long 数据源原始的编号;如果是添加的数据,此编号为0 ext_name string 数据源原始的名称...
-
Linux常用的命令
2014-09-21 19:43:32ln file1 file2 为file1创建file3 的硬连接 同时删除file1 和file2 才能删除文件 分发系统: 1. 支持pxe client 功能,有pxe的网卡 (client端) 2. 有配置文件config system-config-kick 创建kick 文件 (server端) ... -
oracle数据库经典题目
2011-02-17 15:05:20同义词是数据库对象的一个替代名,在使用同义词时,Oracle会将其翻译为对应的对象名称 B.在创建同义词时,所替代的模式对象必须存在 C.Oracle中的同义词分为公有同义词和私有同义词 D.公有同义词在数据库中所有的... -
写给 Jscex 的一些建议
2020-11-28 13:18:24为什么要用 await ? 而不是更直白的 wait 或 sleep ?</li></ol> 开发指南 <ol><li><code>require("jscex-parser").init()</code> 建议简化成 <code>require("jscex-parser")</code>,init ... -
C语言程序设计标准教程
2009-05-22 18:43:58例如pf1和pf2 是指向同一浮点数组的两个指针变量,设pf1的值为2010H,pf2的值为2000H,而浮点数组每个元素占4个字节,所以pf1-pf2的结果为(2000H-2010H)/4=4,表示pf1和 pf2之间相差4个元素。两个指针变量不能进行... -
10. 跨考北邮计算机应该准备些什么,会不会歧视跨考? 11. 报考学硕or专硕? 12. 北邮学硕和专硕的学制是几年? 13. 北邮学硕和专硕的学费和奖学金政策是怎么规定的? 复试篇 分数线 1. 分数线简介 2. ...
-
Oracle DBA手记:数据库诊断案例与性能优化实践(一线Oracle DBA工作思考的心得,盖国强亲自策划)--详细书签...
2013-02-06 14:40:452009年8月,我们终于完成了这本书的组稿、编辑工作,可以将它呈现给大家,在这里我想和大家分享一下为什么会有这本书,以及这本书的来龙去脉。 一、选题及出发 在2008年底,我修订了《深入浅出Oracle》一书... -
(重要)AIX command 使用总结.txt
2011-12-25 16:40:17//设置文件系统/tellinshare/sms的mind属性,否则当文件系统中有足够多的大文件(指32K以上的文件)时会出问题 #chfs -a options=rw,mind /tellinshare/sms mkgroup id=101 informix //创建组informix, 组编号101 ... -
疯狂JAVA讲义
2014-10-17 13:35:01学生提问:为什么即使我没有给多行文本域编写右键菜单,但当我在多行文本域上单击右键时一样会弹出右键菜单? 418 11.7 在AWT中绘图 418 11.7.1 画图的实现原理 418 11.7.2 使用Graphics类 419 11.8 处理位图 ...