com.github.houbb.data.struct.core.util.tree

类 BinarySearchTree<V extends Comparable<? super V>>

java.lang.Object

com.github.houbb.data.struct.core.util.tree.BinarySearchTree<V>

所有已实现的接口:

ISortTree<V>

public class BinarySearchTree<V extends Comparable<? super V>>
extends Object
implements ISortTree<V>

二叉树

从以下版本开始:

0.0.4

作者:

binbin.hou

构造器概要

构造器

构造器和说明
BinarySearchTree()

方法概要

限定符和类型	方法和说明
void	add(V data) Inserts the given data into the binary tree.
boolean	contains(V data) * Returns true if the given target is in the binary tree
int	getHeight() 最大深度
V	getMaxValue() 获取最大值
V	getMinValue() 获取最小值
int	getSize() 返回元素的个数
TreeNode<V>	getSuccessor(TreeNode<V> delNode) 寻找中继节点
List<V>	inOrder() 中序遍历：即左-根-右遍历，对于给定的二叉树根，寻找其左子树；对于其左子树的根，再去寻找其左子树；递归遍历，直到寻找最左边的节点i，其必然为叶子，然后遍历i的父节点，再遍历i的兄弟节点。
boolean	isBalanced() 是否为平衡树
boolean	isEmpty() 是否为空
List<V>	levelOrder() 层级遍历
List<List<V>>	pathList() 获取所有路径列表 从根节点，到叶子节点的路径
List<V>	postOrder() 后序遍历：即左-右-根遍历，不再详述。
List<V>	preOrder() 先序遍历：即根-左-右遍历，不再详述。
void	print() 打印思路
boolean	remove(V data) 情况 1：如果删除的节点没有右孩子，那么就选择它的左孩子来代替原来的节点。

从类继承的方法 java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

构造器详细资料

BinarySearchTree

public BinarySearchTree()

方法详细资料

contains

public boolean contains(V data)

* Returns true if the given target is in the binary tree. * Uses a recursive helper. * @since 0.0.4

指定者:

contains 在接口中 ISortTree<V extends Comparable<? super V>>

参数:

data - 元素

返回:

是否包含

add

public void add(V data)

Inserts the given data into the binary tree. Uses a recursive helper. * @param data 待插入元素

指定者:

add 在接口中 ISortTree<V extends Comparable<? super V>>

参数:

data - 元素

remove

public boolean remove(V data)

情况 1：如果删除的节点没有右孩子，那么就选择它的左孩子来代替原来的节点。 二叉查找树的性质保证了被删除节点的左子树必然符合二叉查找树的性质。 因此左子树的值要么都大于，要么都小于被删除节点的父节点的值，这取决于被删除节点是左孩子还是右孩子。 因此用被删除节点的左子树来替代被删除节点，是完全符合二叉搜索树的性质的。 情况 2：如果被删除节点的右孩子没有左孩子，那么这个右孩子被用来替换被删除节点。 因为被删除节点的右孩子都大于被删除节点左子树的所有节点，同时也大于或小于被删除节点的父节点，这同样取决于被删除节点是左孩子还是右孩子。 因此，用右孩子来替换被删除节点，符合二叉查找树的性质。 情况 3：如果被删除节点的右孩子有左孩子，就需要用被删除节点右孩子的左子树中的最下面的节点来替换它， 就是说，我们用被删除节点的右子树中最小值的节点来替换。

指定者:

remove 在接口中 ISortTree<V extends Comparable<? super V>>

参数:

data - 元素

返回:

是否删除

getSuccessor

public TreeNode<V> getSuccessor(TreeNode<V> delNode)

寻找中继节点

参数:

delNode - 删除元素

返回:

中继节点

从以下版本开始:

0.0.4

getSize

public int getSize()

从接口复制的说明: ISortTree

返回元素的个数

指定者:

getSize 在接口中 ISortTree<V extends Comparable<? super V>>

返回:

个数

isEmpty

public boolean isEmpty()

从接口复制的说明: ISortTree

是否为空

指定者:

isEmpty 在接口中 ISortTree<V extends Comparable<? super V>>

返回:

是否为空

getHeight

public int getHeight()

从接口复制的说明: ISortTree

最大深度

指定者:

getHeight 在接口中 ISortTree<V extends Comparable<? super V>>

返回:

深度

getMinValue

public V getMinValue()

从接口复制的说明: ISortTree

获取最小值

指定者:

getMinValue 在接口中 ISortTree<V extends Comparable<? super V>>

返回:

最小值

getMaxValue

public V getMaxValue()

从接口复制的说明: ISortTree

获取最大值

指定者:

getMaxValue 在接口中 ISortTree<V extends Comparable<? super V>>

返回:

最大值

inOrder

public List<V> inOrder()

从接口复制的说明: ISortTree

中序遍历：即左-根-右遍历，对于给定的二叉树根，寻找其左子树；对于其左子树的根，再去寻找其左子树；递归遍历，直到寻找最左边的节点i，其必然为叶子，然后遍历i的父节点，再遍历i的兄弟节点。随着递归的逐渐出栈，最终完成遍历。

指定者:

inOrder 在接口中 ISortTree<V extends Comparable<? super V>>

返回:

结果

preOrder

public List<V> preOrder()

从接口复制的说明: ISortTree

先序遍历：即根-左-右遍历，不再详述。

指定者:

preOrder 在接口中 ISortTree<V extends Comparable<? super V>>

返回:

结果

postOrder

public List<V> postOrder()

从接口复制的说明: ISortTree

后序遍历：即左-右-根遍历，不再详述。

指定者:

postOrder 在接口中 ISortTree<V extends Comparable<? super V>>

返回:

结果

levelOrder

public List<V> levelOrder()

从接口复制的说明: ISortTree

层级遍历

指定者:

levelOrder 在接口中 ISortTree<V extends Comparable<? super V>>

返回:

结果

pathList

public List<List<V>> pathList()

从接口复制的说明: ISortTree

获取所有路径列表 从根节点，到叶子节点的路径

指定者:

pathList 在接口中 ISortTree<V extends Comparable<? super V>>

返回:

0.0.4

print

public void print()

打印思路

指定者:

print 在接口中 ISortTree<V extends Comparable<? super V>>

isBalanced

public boolean isBalanced()

从接口复制的说明: ISortTree

是否为平衡树

指定者:

isBalanced 在接口中 ISortTree<V extends Comparable<? super V>>

返回:

平衡树