精华内容
下载资源
问答
  • 二叉排序树 先看一个需求 给你一个数列(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提供...
  • 23.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 小结 ...
  • 23.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个整数...
  • 消息大于10时会返回消息的排序为 最新的、最近的。 ============================================================= 针对以上需求,目前设计的表结构主要字段如下: 1)、message_info_t表部分字段...
  • Karen Morton及其团队本书中提供了专业的方案:先掌握语言特性,再学习Oracle提升语言效率而加入的支持特性,进而将两者综合考虑并工作中加以应用。作者通过总结各自多年的软件开发和教学培训经验,与大家...
  • Karen Morton及其团队本书中提供了专业的方案:先掌握语言特性,再学习Oracle提升语言效率而加入的支持特性,进而将两者综合考虑并工作中加以应用。作者通过总结各自多年的软件开发和教学培训经验,与大家...
  • 21、为什么数组名作为参数,改变数组的内容,而其它类型如int却不会改变变量的值? 答: 当数组名作为参数,传递的实际上是地址。而其他类型如int作为参数,由于函数参数值实质上是实参的一份拷贝,被调函数内部对...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    10下面的程序段中,对x的赋值语句的频度__t(n)=O(n3)____(表示 n的函数) FOR i:= TO n DO FOR j:= TO i DO FOR k:=1 TO j DO x:=x+delta; 【北京工业大学 1999 一、6(2分)】 ...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    7、 编写一个程序,将10进制数转换其它(2-9)进制数。可以将要转换的数重复除以基数,然后讲除的余数按反方向排列来实现; 8、 已知A[n]正数数组,试写出实现下列运算的递归算法; a. 求数组A中的...
  • 创建表,经常创建该表的主键、外键、唯一约束、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:17
    1:使用SHOW语句找出服务器上当前存在什么数据库: mysql> SHOW DATABASES; 2:2、创建一个数据库MYSQLDATA mysql> Create DATABASE MYSQLDATA; 3:选择你所创建的数据库 mysql> USE MYSQLDATA; (按回车键出现...
  • MYSQL常用命令大全

    2011-05-30 13:31:24
    1:使用SHOW语句找出服务器上当前存在什么数据库: mysql> SHOW DATABASES; 2:2、创建一个数据库MYSQLDATA mysql> Create DATABASE MYSQLDATA; 3:选择你所创建的数据库 mysql> USE MYSQLDATA; (按回车键出现...
  • java常用工具类的使用

    热门讨论 2012-03-19 20:11:37
    Q 老师,时间毫秒值从1970年11日0:00.000开始计算,上面示例中10年后应该是1980年11日0:00.000,为什么输出结果是:1980年11日 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危害开始显露 低效SQL的危害 系统响应变慢,软件开发中的8秒定律,当打开一个...
  • 用来排序时应当先根据拼音前缀的首字母来排序,相同的再根据前缀+名称进行排序 pinyin string name的完整拼音 ext_id long 数据源原始的编号;如果是添加的数据,此编号0 ext_name string 数据源原始的名称...
  • Linux常用的命令

    2014-09-21 19:43:32
    ln 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 ...
  • 例如pf1和pf2 是指向同一浮点数组的两个指针变量,设pf1的值2010H,pf2的值2000H,而浮点数组每个元素占4个字节,所以pf1-pf2的结果(2000H-2010H)/4=4,表示pf1和 pf2之间相差4个元素。两个指针变量不能进行...
  • 10. 跨考北邮计算机应该准备些什么不会歧视跨考? 11. 报考学硕or专硕? 12. 北邮学硕和专硕的学制是几年? 13. 北邮学硕和专硕的学费和奖学金政策是怎么规定的? 复试篇 分数线 1. 分数线简介 2. ...
  •  2009年8月,我们终于完成了这本书的组稿、编辑工作,可以将它呈现给大家,这里我想和大家分享一下为什么会有这本书,以及这本书的来龙去脉。  一、选题及出发  2008年底,我修订了《深入浅出Oracle》一书...
  • //设置文件系统/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 处理位图 ...

空空如也

空空如也

1 2 3
收藏数 42
精华内容 16
关键字:

为什么排序时会10在1前面