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
TreeNode<V>	getSuccessor(TreeNode<V> delNode) 寻找中继节点
List<V>	inOrder() 中序遍历：即左-根-右遍历，对于给定的二叉树根，寻找其左子树；对于其左子树的根，再去寻找其左子树；递归遍历，直到寻找最左边的节点i，其必然为叶子，然后遍历i的父节点，再遍历i的兄弟节点。
List<V>	levelOrder() 层级遍历
int	maxDepth() 最大深度
V	maxValue() 获取最大值
V	minValue() 获取最小值
List<List<V>>	pathList() 获取所有路径列表 从根节点，到叶子节点的路径
List<V>	postOrder() 先序遍历：即根-左-右遍历，不再详述。
List<V>	preOrder() 先序遍历：即根-左-右遍历，不再详述。
void	print() 打印思路
boolean	remove(V data) 情况 1：如果删除的节点没有右孩子，那么就选择它的左孩子来代替原来的节点。
int	size() 返回元素的个数

从类继承的方法 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

size

public int size()

从接口复制的说明: ISortTree

返回元素的个数

指定者:

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

返回:

个数

maxDepth

public int maxDepth()

从接口复制的说明: ISortTree

最大深度

指定者:

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

返回:

深度

minValue

public V minValue()

从接口复制的说明: ISortTree

获取最小值

指定者:

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

返回:

最小值

maxValue

public V maxValue()

从接口复制的说明: ISortTree

获取最大值

指定者:

maxValue 在接口中 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>>