文档章节

排序二叉树

JiaChang
 JiaChang
发布于 2016/08/12 11:43
字数 1431
阅读 11
收藏 0
点赞 0
评论 0

排序二叉树

排序二叉树要么是一棵空二叉树,要么是具有以下性质的二叉树

(1)若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值。

(2)若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值。

(3)它的左,右子树也分别为排序二叉树。

创建排序二叉树

(1)以根节点为当前节点开始搜索

(2)拿新节点的值和当前节点的值比较

(3)如果新节点的值更大,则以当前节点的右子节点作为新的当前节点;如果新节点的值更小,则以当前节点的左子节点作为新的当前节点

(4)重复2和3两个步骤,直到搜索到合适的叶子节点

(5)将新节点添加为第4步找到的叶子节点的子节点,如果新节点更大,则添加为右子节点;否则,添加为左子节点

删除节点

当从排序二叉树中删除一个节点之后,为了让它依然保持为排序二叉树,必须对该排序二叉树进行维护。维护可以分成如下几种情况

(1)被删除节点是叶子节点,只需将它从父节点中删除

(2)被删除节点p只有左子树或则只有右子树,用p的子节点来代替要删除的节点

 

 

(3)若被删除节点p的左,右子树均非空,则有两种做法,一是用被删除节点最大的左孩子来代替删除节点,二是用被删除节点最小的右孩子来代替删除节点。

 

排序二叉树的节点定义

//排序二叉树节点结构
	class Node{
		Object data;
		Node left;
		Node right;
		Node parent;
		
		public String toString(){
			return "[data="+this.data+"]";
		}
		
		public boolean equals(Object obj){
			if(this==obj){
				return true;
			}
			if(obj.getClass() == Node.class){
				Node target = (Node)obj;
				return this.data.equals(target.data)
						&& this.left == target.left
						&& this.right == target.right
						&& this.parent == target.parent;
			}
			return false;
		}
	}

排序二叉树添加节点

/***
	 * 添加节点
	 * @param data 新添加节点的数据
	 */
	public void add(E data){
		if(root==null){
			new SortedBinTree(data);	//如果树根为null,则先构造树根节点
		}
		else{
			int cmp = 0;
			Node parent = null;
			Node current = root;
			do{
				parent = current;
				cmp = data.compareTo(current.data);		
				//如果新节点的值大于当前节点的值
				if(cmp>0){
					current = current.right;	//以右子节点作为当前节点
				}
				else {		//否则新节点小于当前节点的值
					current = current.left;		//以左子节点当作当前节点
				}
			}while(current!=null);		//当前节点不为null继续遍历
			//创建新节点
			Node newNode = new Node();
			newNode.data = data;
			newNode.parent = parent;
			if(cmp>0){
				parent.right = newNode;
			}
			else {
				parent.left = newNode;
			}
		}
		
	}

排序二叉树删除节点

/***
	 * 删除指定节点
	 * @param element 删除节点
	 * @return 被删除节点存在则删除并将该节点返回,不存在则返回null
	 */
	public Node remove(E element){

		Node target = getNode(element);
		if(target == null){
			return null;
		}
		//第一种情况:被删除节点为叶子节点,(处理方法:直接删除即可)
		if(target.left == null && target.right == null){
			Node deleteNode = target;
			//如果要删除的节点是根节点
			if(target == root){
				root = null;
			}
			else {
				//要删除节点是父节点的左孩子节点,直接删除即可
				if(target == target.parent.left){
					target.parent.left = null;					
				}
				//要删除节点是父节点的右孩子节点
				else {
					target.parent.right = null;	
				}
			}
			//删除目标节点
			target = null;
			return deleteNode;
		}
		//第二种情况:被删除节点只有左孩子节点(处理方法:用要删除节点的左孩子节点代替要删除节点)
		else if(target.left != null && target.right == null){
			Node deleteNode = target;
			if(target == root){
				root = target.left;
			}
			else {
				//如果要删除节点是父节点的左孩子节点
				if(target == target.parent.left){
					//用要删除节点的左孩子节点代替要删除节点
					target.parent.left = target.left;
				}
				else {
					target.parent.right = target.left;
				}
				//让target的左子树的parent指向target的parent
				target.left.parent = target.parent;
			}
			//删除目标节点
			target = null;
			return deleteNode;
		}
		//第三种情况:被删除节点只有右孩子节点(处理方法:用要删除节点的右孩子节点代替要删除节点)
		else if(target.left == null && target.right != null){
			Node deleteNode = target;
			//被删除节点是根节点
			if(target == root){
				root = target.right;	
			}
			else {
				//如果被删除节点是父节点的左孩子节点
				if(target == target.parent.left){
					target.parent.left = target.right;
				}
				//否则被删除节点是父节点的右孩子节点
				else {
					target.parent.right = target.right;
				}
				//让target的右子树的parent指向target的parent
				target.right.parent = target.parent;
			}
			//删除目标节点
			target = null;
			return deleteNode;
		}
		//第四种情况:被删除节点非叶子节点,并且左右孩子都不为null(处理方法有两种:一种是用被删除节点的最大左孩子节点代替删除节点,另一种是用被删除节点最小的右孩子节点代替删除节点)
		else {
			Node deleteNode = target;
			Node maxLeftNode = target.left;
			//找到删除节点的最大左孩子节点
			while(maxLeftNode.right!=null){
				maxLeftNode = maxLeftNode.right;
			}
			//从原有的子树中删除最大的左孩子节点
			maxLeftNode.parent.right = null;
			//如果删除节点为父节点的左孩子节点
			if(target == target.parent.left){
				target.parent.left = maxLeftNode;
			}
			//否则删除节点为父节点的右孩子节点
			else {
				target.parent.right = maxLeftNode;
			}
			//用被删除节点的最大左孩子节点代替删除节点
			maxLeftNode.parent = target.parent;
			maxLeftNode.left = target.left;
			maxLeftNode.right = target.right;
			target = null;
			return deleteNode;
		}
		
		
	}

获取指定节点

/***
	 * 根据节点的数据获取指定节点
	 * @param element
	 * @return
	 */
	public Node getNode(E element){
		if(root == null){
			
		}
		Node p = root;
		while(p != null){
			int cmp = element.compareTo(p.data);
			if(cmp>0){
				p = p.right;
			}
			else if(cmp<0){
				p = p.left;
			}
			else return p;
		}
		return null;
	}

广度优先遍历

/***
	 * 广度优先遍历
	 * 利用队列实现
	 * @return list
	 */
	public List<Node> breadthFirst(){
		Queue<Node> queue = new ArrayDeque<>();
		List<Node> list = new ArrayList<>();
		if(root != null){
			queue.add(root);
		}
		while(!queue.isEmpty()){
			Node node = queue.poll();
			list.add(node);
			if(node.left != null){
				queue.add(node.left);
			}
			if(node.right != null){
				queue.add(node.right);
			}
		}
		return list;
	}

深度优先遍历

public void inOrderIterator(Node root){
		if(root !=null){
			inOrderIterator(root.left);
			System.out.println(root);
			inOrderIterator(root.right);
		}
	}

 

© 著作权归作者所有

共有 人打赏支持
JiaChang
粉丝 2
博文 32
码字总数 18002
作品 0
海口
程序员
二叉树知识点回忆以及整理

二叉树 在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”,左子树和右子树同时也是二叉树。二叉树的子树有左右之分,并且次序不能任意颠倒。...

静默加载 ⋅ 2017/10/19 ⋅ 0

js之排序二叉树

先说说什么是二叉树 在计算机科学中,二叉树(英语:Binary tree)是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有...

Gesangs ⋅ 2017/10/30 ⋅ 0

二叉树算法笔记:二叉排序树(二叉搜索树) in java

本内容仅贴出三链二叉树的操作(在二叉树的两篇文章里已经有了如下代码,完全相同,只是这里把二叉排序树的代码提取出来而已)。 二叉树算法笔记:二叉树基础操作(三链二叉树) in java http:...

CheN_exe ⋅ 2014/01/26 ⋅ 0

平衡二叉树、完全二叉树、满二叉树、二叉搜索(查找 / 排序)树、平衡二叉搜索树、二叉堆

查了一些博客、百科整理出以下关于树的定义以及易混点: 平衡二叉树:一棵空树或左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是平衡二叉树。(注意:实际应用中很少有不是二叉搜...

BeerBread134 ⋅ 2017/06/03 ⋅ 0

树/二叉树(哈夫曼树/红黑树)笔记

1.树是一种常用数据结构,它是非线性结构。 2.树中任一普通节点可以有0或者多个子节点,但只能有一个父节点。 根节点没有父节点,叶子节点没有子节点。 3.二叉树: 1)每个节点最多只能有两个...

6pker ⋅ 2015/08/14 ⋅ 0

堆排序、胜者树、败者树,孰优孰劣?

在顺序存储结构中,堆排序是一种非常不错的高级选择排序算法,普通情况和最差情况下都可以将时间复杂度控制在O(n * logn)。 堆排序可以用在顺序存储结构,是因为完全二叉树的一种独特性质。而...

刘地 ⋅ 2015/03/15 ⋅ 0

堆、优先级队列和堆排序

堆结构是一种数组对象,其定义如下:它是完全二叉树或者近似完全二叉树。经常作为优先级队列,比如二叉树优先级队列,四叉树优先级队列。 n个关键字序列Kl,K2,…,Kn称为(Heap),当且仅当...

长平狐 ⋅ 2013/12/25 ⋅ 0

判断一棵二叉树是否为搜索二叉树和完全二叉树

【题目】 给定一个二叉树的头结点head,已知其中没有重复值的节点,实现两个函数分别判断这棵二叉树是否是搜索二叉树和完全二叉树。 【回顾】 二叉查找树(Binary Search Tree),(又:二叉...

junjunba2689 ⋅ 04/19 ⋅ 0

排序算法之冒泡排序

关于数据结构和算法,有人可能回觉得很难,还有人觉得工作中用不到.其实简单的数据结构和算法不难,对于一个有基本CS素养的工程师,简单的算法是应该能够徒手写出来的.所以我准备总结一下简单的数...

Lubby ⋅ 2015/05/14 ⋅ 0

二叉树,排序二叉树

说到二叉树,这可是数据结构里面的非常重要的一种数据结构,二叉树是树的一种,本身具有递归性质,所以基于二叉树的一些算法很容易用递归算法去实现。作为一种非线性结构,比起线性结构还是相...

长平狐 ⋅ 2013/12/25 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Redis 单线程 为何却需要事务处理并发问题

Redis是单线程处理,也就是命令会顺序执行。那么为什么会存在并发问题呢? 个人理解是,虽然redis是单线程,但是可以同时有多个客户端访问,每个客户端会有 一个线程。客户端访问之间存在竞争...

码代码的小司机 ⋅ 46分钟前 ⋅ 0

到底会改名吗?微软GVFS 改名之争

微软去年透露了 Git Virtual File System(GVFS)项目,GVFS 是 Git 版本控制系统的一个开源插件,允许 Git 处理 TB 规模的代码库,比如 270 GB 的 Windows 代码库。该项目公布之初就引发了争...

linux-tao ⋅ 56分钟前 ⋅ 0

笔试题之Java基础部分【简】【二】

1.静态变量和实例变量的区别 在语法定义上的区别:静态变量前要加static关键字,而实例变量前则不加。在程序运行时的区别:实例变量属于某个对象的属性,必须创建了实例对象,其中的实例变...

anlve ⋅ 今天 ⋅ 0

Lombok简单介绍及使用

官网 通过简单注解来精简代码达到消除冗长代码的目的 优点 提高编程效率 使代码更简洁 消除冗长代码 避免修改字段名字时忘记修改方法名 4.idea中安装lombnok pom.xml引入 <dependency> <grou...

to_ln ⋅ 今天 ⋅ 0

【转】JS浮点数运算Bug的解决办法

37.5*5.5=206.08 (JS算出来是这样的一个结果,我四舍五入取两位小数) 我先怀疑是四舍五入的问题,就直接用JS算了一个结果为:206.08499999999998 怎么会这样,两个只有一位小数的数字相乘,怎...

NickSoki ⋅ 今天 ⋅ 0

table eg

user_id user_name full_name 1 zhangsan 张三 2 lisi 李四 `` ™ [========] 2018-06-18 09:42:06 星期一½ gdsgagagagdsgasgagadsgdasgagsa...

qwfys ⋅ 今天 ⋅ 0

一个有趣的Java问题

先来看看源码: public class TestDemo { public static void main(String[] args) { Integer a = 10; Integer b = 20; swap(a, b); System.out......

linxyz ⋅ 今天 ⋅ 0

十五周二次课

十五周二次课 17.1mysql主从介绍 17.2准备工作 17.3配置主 17.4配置从 17.5测试主从同步 17.1mysql主从介绍 MySQL主从介绍 MySQL主从又叫做Replication、AB复制。简单讲就是A和B两台机器做主...

河图再现 ⋅ 今天 ⋅ 0

docker安装snmp rrdtool环境

以Ubuntu16:04作为基础版本 docker pull ubuntu:16.04 启动一个容器 docker run -d -i -t --name flow_mete ubuntu:16.04 bash 进入容器 docker exec -it flow_mete bash cd ~ 安装基本软件 ......

messud4312 ⋅ 今天 ⋅ 0

OSChina 周一乱弹 —— 快别开心了,你还没有女友呢。

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子 :分享吴彤的单曲《好春光》 《好春光》- 吴彤 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :小萝莉街上乱跑,误把我认错成...

小小编辑 ⋅ 今天 ⋅ 9

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部