## 二叉树算法笔记：二叉排序树(二叉搜索树) in java 原

CheN_exe

http://my.oschina.net/wangchen881202/blog/195027

http://my.oschina.net/wangchen881202/blog/195025

``````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;
}

toList( this , list );
return list;
}

private void toList( BinaryTreeNode root , List<BinaryTreeNode> list ){
if( root != null ){
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++ ){
}
}

/**
* 将二叉树转化为二叉排序树简单二叉排序树
* @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;
}
}

/**
* 将数组转化为二叉排序树，注：array中不要包含root已赋值给root的值，否则会多出一个值
* @param root
* @param array
*/
public static void buildBinarySortingTree( BinaryTreeNode root , int[] array ){
for(int i = 0 ; i < array.length ; 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;
}
}

/**
* 将指定的元素插入二叉排序树中
* @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{
}
}else if(target>value){
if(root.getRightChild()==null){
BinaryTreeNode node=new BinaryTreeNode(target);
root.setRightChild(node);
}else{
}
}
}

/**
* 查找二叉排序树
* @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 ){
return true;
}
return addNodeToBinarySortingTree( root.getLeftChild() , node );
}else{
if( root.getRightChild() == null ){
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();
parent.setLeftChild(null);
else
parent.setRightChild(null);
node.setParent(null);
return true;
}else{
if( leftChild == null ){//如果只有右结点，则将右结点与父结点相连
parent.setLeftChild(rightChild);
}else{
parent.setLeftChild(leftChild);
}
rightChild.setParent(parent);
node.setRightChild(null);
node.setParent(null);
return true;
}else if(rightChild == null ){//如果只有左结点，则将左结点与父结点相连
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

snailclimb
2018/05/08
0
0

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

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

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

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

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