文档章节

排序二叉树

JiaChang
 JiaChang
发布于 2016/08/12 11:43
字数 1431
阅读 11
收藏 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
平衡二叉树、完全二叉树、满二叉树、二叉搜索(查找 / 排序)树、平衡二叉搜索树、二叉堆

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

BeerBread134
2017/06/03
0
0
树/二叉树(哈夫曼树/红黑树)笔记

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

6pker
2015/08/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

49.Nginx防盗链 访问控制 解析php相关 代理服务器

12.13 Nginx防盗链 12.14 Nginx访问控制 12.15 Nginx解析php相关配置(502的问题) 12.16 Nginx代理 扩展 502问题汇总 http://ask.apelearn.com/question/9109 location优先级 http://blog....

王鑫linux
今天
1
0
Nginx防盗链、访问控制、解析php相关配置、Nginx代理

一、Nginx防盗链 1. 编辑虚拟主机配置文件 vim /usr/local/nginx/conf/vhost/test.com.conf 2. 在配置文件中添加如下的内容 { expires 7d; valid_referers none blocked server_names *.tes......

芬野de博客
今天
0
0
spring EL 和资源调用

资源调用 import org.springframework.beans.factory.annotation.Value;import org.springframework.context.annotation.PropertySource;import org.springframework.core.io.Resource;......

Canaan_
今天
1
0
memcached命令行、memcached数据导出和导入

一、memcached命令行 yum装telnet yum install telent 进入memcached telnet 127.0.0.1 11211 命令最后的2表示,两位字节,30表示过期时间(秒) 查看key1 get key1 删除:ctrl+删除键 二、m...

Zhouliang6
今天
1
0
Linux定时备份MySQL数据库

做项目有时候要备份数据库,手动备份太麻烦,所以找了一下定时备份数据库的方法 Linux里有一个 crontab 命令被用来提交和管理用户的需要周期性执行的任务,就像Windows里的定时任务一样,用这...

月夜中徘徊
今天
1
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部