文档章节

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

CheN_exe
 CheN_exe
发布于 2014/01/26 07:25
字数 1149
阅读 1031
收藏 11

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

二叉树算法笔记:二叉树基础操作(三链二叉树) in java
http://my.oschina.net/wangchen881202/blog/195027

二叉树算法笔记:二叉树基础操作(二链二叉树) in java
http://my.oschina.net/wangchen881202/blog/195025


本文不包含二叉平衡树和红黑树,这两部分将在两个单独的博客中贴出。

 

 

二叉树结点类,注:包含toArray()方法和toList()方法:

public class BinaryTreeNode {
	
	private BinaryTreeNode leftChild;
	private BinaryTreeNode rightChild;
	private BinaryTreeNode parent;
	private int value;
	
	public BinaryTreeNode(){
	}

	public BinaryTreeNode( int value ){
		this.value = value;
	}
	
	public BinaryTreeNode getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(BinaryTreeNode leftChild) {
		this.leftChild = leftChild;
	}

	public BinaryTreeNode getRightChild() {
		return rightChild;
	}

	public void setRightChild(BinaryTreeNode rightChild) {
		this.rightChild = rightChild;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	public BinaryTreeNode getParent() {
		return parent;
	}

	public void setParent(BinaryTreeNode parent) {
		this.parent = parent;
	}

	public LinkedList<BinaryTreeNode> toList(){
		LinkedList<BinaryTreeNode> list = new LinkedList<BinaryTreeNode>();
		toList( this , list );
		return list;
	}
	
	private void toList( BinaryTreeNode root , List<BinaryTreeNode> list ){
		if( root != null ){
			list.add( root );
			toList( root , list );
			toList( root , list );
		}
	}
	
	public int[] toArray(){
		int[] array = new int[BinaryTree2Links.getSubNodeNum(this) + 1 ];
		toArray( this , array , 0 );
		return array;
	}
	
	private void toArray( BinaryTreeNode root , int[] array, int i ){
		if( root != null ){
			array[i++] = root.getValue();
			toArray( root , array , i );
			toArray( root , array , i );
		}
	}
}

 

 

二叉排序树操作类:

/**
 * 二叉排序树
 * 定义:左子树若不为空,左子树均小于根节点;若右子树不为空,右子树均大于根节点。左右子树分别为二叉排序树。
 * 	特点:
 * 		复杂度为:O(logn)
 * 			最坏情况:O(n)
 * 	由此引申出来的概念:平衡二叉树、红黑树
 * 
 * @author CheN
 *
 */
public class BinarySortingTree {
	/**
	 * 将数组转化为二叉排序树
	 * @param array
	 */
	public static void buildBinarySortingTree( int[] array ){
		BinaryTreeNode root = new BinaryTreeNode();
		root.setValue(array[0]);
		for( int i = 1 ; i < array.length ; i++ ){
			addBinarySortingTreeNode( root , array[i] );
		}
	}
	
	/**
	 * 将二叉树转化为二叉排序树简单二叉排序树
	 * @param root
	 */
	public static void buildBinarySortingTree( BinaryTreeNode root ){
		List<BinaryTreeNode> list = root.toList();
		for(int i = 0 ; i < list.size() ; i++ ){
			if( list.get(i) == root )
				continue;
			addBinarySortingTreeNode( root , list.get(i).getValue() );
		}
	}
	
	/**
	 * 将数组转化为二叉排序树,注:array中不要包含root已赋值给root的值,否则会多出一个值
	 * @param root
	 * @param array
	 */
	public static void buildBinarySortingTree( BinaryTreeNode root , int[] array ){
		for(int i = 0 ; i < array.length ; i++ ){
			addBinarySortingTreeNode( root , array[i] );
		}
	}
	
	/**
	 * 将二叉树转化为二叉排序树简单二叉排序树:newRoot须为原树中的某一结点
	 * @param root
	 * @param newRoot
	 */
	public static void buildBinarySortingTree( BinaryTreeNode root , BinaryTreeNode newRoot ){
		List<BinaryTreeNode> list = root.toList();
		for(int i = 0 ; i < list.size() ; i++ ){
			if( list.get(i) == newRoot )
				continue;
			addBinarySortingTreeNode( newRoot , list.get(i).getValue() );
		}
	}
	
	/**
	 * 将指定的元素插入二叉排序树中
	 * @param root
	 * @param target
	 */
	private static void addBinarySortingTreeNode( BinaryTreeNode root , int target ){
		int value = root.getValue();
		if( target < value ){//插入右子树
			if(root.getLeftChild()==null){
				BinaryTreeNode node=new BinaryTreeNode(target);
				root.setLeftChild(node);
			}else{
				addBinarySortingTreeNode( root.getLeftChild() , target );
			}
		}else if(target>value){
			if(root.getRightChild()==null){
				BinaryTreeNode node=new BinaryTreeNode(target);
				root.setRightChild(node);
			}else{
				addBinarySortingTreeNode( root.getRightChild() , target );
			}
		}
	}
	
	/**
	 * 查找二叉排序树
	 * @param root
	 * @param target
	 */
	public static BinaryTreeNode BinarySerch( BinaryTreeNode root,int target ){
		if( root == null ){
			return null;
		}else if(root.getValue()==target){
			return root;
		}else if(root.getValue()>target){
			 return BinarySerch(root.getLeftChild(),target);
		}else{
			 return BinarySerch(root.getRightChild(),target);
		}
	}
	
	/**
	 * 获取二叉排序树最小值(即最左侧结点)
	 * @param root
	 * @return
	 */
	public static BinaryTreeNode getMinFromBinarySortingTree( BinaryTreeNode root ){
		if( root.getLeftChild() == null ){
			return root;
		}else{
			return getMinFromBinarySortingTree( root.getLeftChild() );
		}
	}

	/**
	 * 获取二叉排序树最大值(即最右侧结点)
	 * @param root
	 * @return
	 */
	public static BinaryTreeNode getMaxFromBinarySortingTree( BinaryTreeNode root ){
		if( root.getRightChild() == null ){
			return root;
		}else{
			return getMaxFromBinarySortingTree( root.getRightChild() );
		}
	}

	/**
	 * 在二叉排序树上增加结点
	 * @param root
	 * @param node
	 * @return
	 */
	public static boolean addNodeToBinarySortingTree( BinaryTreeNode root , BinaryTreeNode node ){
		if( root.getValue() > node.getValue() ){
			if( root.getLeftChild() == null ){
				BinaryTree3Links.addLeftChild(root, node);
				return true;
			}
			return addNodeToBinarySortingTree( root.getLeftChild() , node );
		}else{
			if( root.getRightChild() == null ){
				BinaryTree3Links.addRightChild(root, node);
				return true;
			}
			return addNodeToBinarySortingTree( root.getRightChild() , node );
		}
	}

	/**
	 * 在二叉排序树上删除节点
	 * @param node
	 * @return
	 */
	public static boolean deleteNodeFromBinarySortingTree( BinaryTreeNode node ){
		BinaryTreeNode parent = node.getParent();
		BinaryTreeNode rightChild = node.getRightChild();
		BinaryTreeNode leftChild = node.getLeftChild();
		if( BinaryTree3Links.isLeaf(node) ){//如果是叶子结点,则直接删了
			if( BinaryTree3Links.isLeftChild(node))
				parent.setLeftChild(null);
			else
				parent.setRightChild(null);
			node.setParent(null);
			return true;
		}else{
			if( leftChild == null ){//如果只有右结点,则将右结点与父结点相连
				if( BinaryTree3Links.isLeftChild(node)){
					parent.setLeftChild(rightChild);
				}else{
					parent.setLeftChild(leftChild);
				}
				rightChild.setParent(parent);
				node.setRightChild(null);
				node.setParent(null);
				return true;
			}else if(rightChild == null ){//如果只有左结点,则将左结点与父结点相连
				if( BinaryTree3Links.isLeftChild(node)){
					parent.setRightChild(rightChild);
				}else{
					parent.setRightChild(leftChild);
				}
				leftChild.setParent(parent);
				node.setLeftChild(null);
				node.setParent(null);
				return true;
			}else{//若左右子树都存在,则在左子树中找到最大的一个结点替代这个结点,若该节点有左子树,则将其左子树与其父结点连接
				BinaryTreeNode temp = leftChild;
				while( temp.getRightChild() != null ){
					temp = temp.getRightChild();
				}
				if( temp.getLeftChild() != null ){
					BinaryTreeNode tempParent = temp.getParent();
					temp.getLeftChild().setParent(tempParent);
					tempParent.setRightChild(temp.getLeftChild());
				}
				temp.setParent(parent);
				temp.setLeftChild(leftChild);
				temp.setRightChild(rightChild);
				node.setParent(null);
				node.setLeftChild(null);
				node.setRightChild(null);
			}
		}
		return false;
	}
}

 

 


若有错误或不妥之处,敬请谅解并指点。

 

© 著作权归作者所有

共有 人打赏支持
CheN_exe
粉丝 3
博文 40
码字总数 17192
作品 0
海淀
程序员
私信 提问
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
2018/05/08
0
0
数据结构笔记--二叉查找树概述以及java代码实现

一些概念:   二叉查找树的重要性质:对于树中的每一个节点X,它的左子树任一节点的值均小于X,右子树上任意节点的值均大于X.   二叉查找树是java的TreeSet和TreeMap类实现的基础.   由于树...

冬至饮雪
2016/05/14
0
0
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
0
0
LeetCode算法题-Convert Sorted Array to Binary Search Tree(Java实现)

这是悦乐书的第166次更新,第168篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第25题(顺位题号是108)。给定一个数组,其中元素按升序排序,将其转换为高度平衡的二叉搜索树...

小川94
2018/11/09
0
0
Java Balanced Binary Tree

Java Balanced Binary Tree 平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和 E.M. Landis发明了这棵树,所以...

秋风醉了
2015/06/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

redis&memcached&SQL&NoSQL

Why 一个应用肯定有两部分逻辑:数据逻辑和业务逻辑。 数据逻辑包括各种I/O,和内部的数据的处理,也就是在内部如何组织数据结构,变量也属于这一部分。 当一个应用变成一个进程,它负责数据逻...

backbye
今天
2
0
什么时候使用字节流、什么时候使用字符流,二者的区别

在程序中所有的数据都是以流的方式进行传输或保存的,程序需要数据的时候要使用输入流读取数据,而当程序需要将一些数据保存起来的时候,就要使用输出流完成。 InputStream 和OutputStream,...

watermelon11
今天
6
0
Alpakka Kafka,反应式Kafka客户端

Alpakka Kafka 是一个要用于 Java 和 Scala 语言的开源的流感知和反应式集成数据线项目。它建立在 Akka Stream之上,提供了 DSL 来支持反应式和流式编程,内置回压功能。Akka Streams 是 Re...

羊八井
今天
5
0
PHP7源码编译安装详解

$ yum groupinstall "development tools"$ yum install -y gcc gcc-c++ autoconf libjpeg libjpeg-devel libpng libpng-devel freetype \freetype-devel libpng libpng-devel libxml2 ......

问题终结者
今天
5
0
Django学习笔记-从创建虚拟环境到启用服务

1 前置条件 windows系统下,目前已经完成anaconda3或miniconda3的安装,这也意味着已经完成了python3的安装。 2 创建虚拟环境 1、通过Anaconda Prompt,使用conda命令创建虚拟环境(base) e...

davidwbnu
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部