文档章节

排序二叉树

JiaChang
 JiaChang
发布于 2016/08/12 11:43
字数 1431
阅读 12
收藏 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
海口
程序员
私信 提问
JavaScript实现排序二叉树的基本操作

记得一开始学习数据结构用的是c语言实现,学了这么久前端就想用JavaScript来实现一下,顺便复习下数据结构。 先来了解下什么是排序二叉树,排序二叉树是具有以下特点的二叉树 若左子树不空,...

a独家记忆
06/29
0
0
堆排序 最大堆 最小堆 Java实现

堆排序啊,其实是一种数据结构,二叉树,二叉树分为是满二叉树和完全二叉树。一棵深度为 k,且有 2k - 1 个节点称之为满二叉树,完全二叉树:深度为 k,有 n 个节点的二叉树,当且仅当其每一...

豆芽菜橙
07/03
0
0
二叉树知识点回忆以及整理

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

静默加载
2017/10/19
0
0
二叉树算法笔记:二叉排序树(二叉搜索树) in java

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

CheN_exe
2014/01/26
0
0
平衡二叉树、完全二叉树、满二叉树、二叉搜索(查找 / 排序)树、平衡二叉搜索树、二叉堆

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

BeerBread134
2017/06/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Flink-数据流编程模型

1、抽象等级 Flink提供了不同级别的抽象来开发流/批处理应用程序。 1) 低层级的抽象 最低层次的抽象仅仅提供有状态流。它通过Process函数嵌入到DataStream API中。它允许用户自由地处理来自一...

liwei2000
25分钟前
1
0
Java开发Swing实战JFrame和JTabbedPane容器的用法详细解析

概述: 项目是一个桌面程序,涉及标签和按钮组件、布局管理器组件、面板组件、列表框和下拉框组件等组件,以及Swing事件处理机制。 下面先从最基础的界面开始。 /** * @author: lishuai * @...

金铭鼎IT教育
30分钟前
9
0
flask 之旅

环境 为了正确地跑起来,你的应用需要依赖许多不同的软件。 就算是再怎么否认这一点的人,也无法否认至少需要依赖Flask本身。 你的应用的运行环境,在当你想要让它跑起来时,是至关重要的。 ...

hblt-j
30分钟前
6
0
easyui的上传文件

记录一下自己亲手操刀easyui的心得:不用不知道,一用就问题多,网上查资料,有用的真的太少了 ——————————————————正文 FileBox,还是不错的讲真,至少我去自己写就gaga了...

anlve
31分钟前
4
0
如何做好SQLite 使用质量检测,让事故消灭在摇篮里

本文由云+社区发表 SQLite 在移动端开发中广泛使用,其使用质量直接影响到产品的体验。 常见的 SQLite 质量监控一般都是依赖上线后反馈的机制,比如耗时监控或者用户反馈。这种方式问题是: ...

腾讯云加社区
34分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部