文档章节

排序二叉树

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

没有更多内容

加载失败,请刷新页面

加载更多

关于Excel表格导出方法--application/vnd.ms-excel

关于Excel表格导出方法--application/vnd.ms-excel 由于本人所做的项目中需要用到两种将JSP页面table导出到Excel表格的方法(老板也是坑爹),一种是在后台操作数据库来实现,比较简单。由于...

DemonsI
25分钟前
2
0
springboot配置读写分离

我不提供内容,我只是好文章的搬运工 https://www.cnblogs.com/wuyoucao/p/9610882.html

颖辉小居
29分钟前
2
0
Spring 传参

spring传参之@RequestParam注解 @RequestParam注解有三个参数分别是: value、 required、 defaultValue 代码: @RequestMapping(value="test1", method = RequestMethod.GET) public String......

休辞醉倒
30分钟前
2
0
go http 框架性能大幅下降原因分析

最近在开发一个web 框架,然后业务方使用过程中,跟我们说,压测qps 上不去,我就很纳闷,httprouter + net/http.httpserver , 性能不可能这么差啊,网上的压测结果都是10w qps 以上,几个m...

鼎铭
31分钟前
11
0
GCC编译过程记

GCC编译过程记 一、引言 对于编程工作者来说,GCC是一个熟悉的名字,它的全称是“GNU Compiler Collection”。GCC是一组编译器集合,目前其支持C、C++、Objective-C、Objective-C++、Go和RBI...

珲少
32分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部