二叉查找树(排序树)与java实现
一.二叉查找树的基本特点
二.java实现
三.二叉查找树增删改查时间复杂度
一.二叉查找树基本特点
1.1 若任意节点的左子树不空，则左子树上所有节点的值均小于等于它的根节点的值；
1.2 若任意节点的右子树不空，则右子树上所有节点的值均大于等于它的根节点的值；
1.3 任意节点的左、右子树也分别为二叉查找树。
二.二叉查找树的java实现
package comUtils;
/**@description
* 二叉查找树(排序树)基本类
* @author Jintao_Ma
*/
public class BSTree<T extends Comparable<T>>{
/*基本方法*/
private boolean isNull(BSNode<T> bSNode){
return null == bSNode;
}
private boolean isNotNull(BSNode<T> bSNode){
return !isNull(bSNode);
}
BSNode<T> root; /*根节点*/
public class BSNode<S extends Comparable<T>>{
S key; /*当前节点的值*/
BSNode<S> parent; /*父节点,设置该属性是为了更方便的查找上级*/
BSNode<S> left; /*左孩子*/
BSNode<S> right; /*右孩子*/
public BSNode(S key, BSNode<S> parent, BSNode<S> left, BSNode<S> right) {
super();
this.key = key;
this.parent = parent;
this.left = left;
this.right = right;
}
}
/**@description
* 初始化二叉树
*/
public BSTree(){
}
/**@description
* 判断树是否为空
*/
public boolean isEmpty(){
return isNull(root);
}
/**@description
* 初始化二叉树
*/
public void init(){
root = null;
}
/**@description
* 判断节点是不是根节点
*/
public boolean isRoot(BSNode<T> bSNode){
return (root == bSNode)? true:false;
}
/**@description
* 添加节点
*/
public boolean addBSNode(T key){
/*判断添加节点是否成功*/
boolean result = true;
BSNode<T> bSNode = new BSNode<T>(key, null, null, null);
if(isEmpty()){
root = bSNode;
}else{
result = insert(root,bSNode);
}
return result;
}
private boolean insert(BSNode<T> root,BSNode<T> bSNode){
/*判断添加节点是否成功*/
boolean result = true;
if(bSNode.key.compareTo(root.key) < 0){
if(isNotNull(root.left)){
result = insert(root.left,bSNode);
}else{
root.left = bSNode;
bSNode.parent = root;
}
}else if(bSNode.key.compareTo(root.key) > 0){
if(isNotNull(root.right)){
result = insert(root.right,bSNode);
}else{
root.right = bSNode;
bSNode.parent = root;
}
}else{
result = false;/*值相等什么也不做*/
}
return result;
}
/**@description
* 删除节点,如果不破坏树的结构(中序遍历是递增的)，那么分三种情况：
* 1)需要删除的节点下并没有其他子节点
* 2)需要删除的节点下有一个子节点(左或者右)
* 3)需要删除的节点下有两个子节点(通过查找它的前驱节点(后继节点)，然后替换该节点，最后删除前驱节点(后继节点)),然后执行步骤2)
*/
public boolean delBSNode(T key){
boolean del = false;
BSNode<T> BSNode = findAllNode(key);
if(isNull(BSNode)){
return del;
}else{
}
/**该节点无任何子节点*/
if(isNull(BSNode.left) && isNull(BSNode.right)){
if(!isRoot(BSNode)){ /*非根节点*/
if(BSNode==BSNode.parent.left){ /*如果是父节点的左孩子*/
BSNode.parent.left = null; /*删除父节点的左引用*/
}else{
BSNode.parent.right = null; /*删除父节点的右引用*/
}
}else{ /*根节点*/
init();
}
del = true;
/**该节点只有一个子节点*/
}else if(isNull(BSNode.left) || isNull(BSNode.right)){
if(!isRoot(BSNode)){ /*非根节点*/
if(isNull(BSNode.left)){ /*该节点只有一个右孩子*/
if(BSNode==BSNode.parent.left){ /*如果是父节点的左孩子*/
BSNode.parent.left = BSNode.right; /*父节点的左引用指向该节点的右孩子*/
}else{
BSNode.parent.right = BSNode.right; /*父节点的右引用指向该节点的右孩子*/
}
BSNode.right.parent = BSNode.parent; /*修改右孩子的父引用*/
}else{ /*该节点只有一个左孩子*/
if(BSNode==BSNode.parent.left){ /*如果是父节点的左孩子*/
BSNode.parent.left = BSNode.left; /*父节点的左引用指向该节点的左孩子*/
}else{
BSNode.parent.right = BSNode.left; /*父节点的右引用指向该节点的左孩子*/
}
BSNode.left.parent = BSNode.parent; /*修改左孩子的父引用*/
}
}else{ /*根节点*/
if(isNull(BSNode.left)){
BSNode.right.parent = null;
root = BSNode.right;
}else{
BSNode.left.parent = null;
root = BSNode.left;
}
}
del = true;
/**两个子节点*/
}else{
BSNode<T> preNode = MaxBode(BSNode.left);/*先查找该节点的前驱节点(后继节点)*/
SwitchKey(preNode,BSNode);/*交换两个BSNode的值*/
del = delBSNode(preNode.key);
}
return del;
}
/**@description
* 交换两个Node的值
*/
public void SwitchKey(BSNode<T> A,BSNode<T> B){
T key;
key = A.key;
A.key = B.key;
B.key = key;
}
/**@description
* 返回key所在的节点(中序查找所有节点)
*/
public BSNode<T> findAllNode(T key){
return isNull(root)? null:middleFindByKey(root,key);
}
public BSNode<T> middleFindByKey(BSNode<T> treeNode,T key){
BSNode<T> bSNode = null;
/*优先查找左自树*/
if(isNotNull(treeNode.left)){
bSNode = middleFindByKey(treeNode.left,key);
if(isNotNull(bSNode)){
return bSNode;
}
}else{
}
/*查找中间节点*/
if(0 == treeNode.key.compareTo(key)){
return bSNode = treeNode;
}else{
}
/*查找右子树*/
if(isNotNull(treeNode.right)){
bSNode = middleFindByKey(treeNode.right,key);
if(isNotNull(bSNode)){
return bSNode;
}
}else{
}
return bSNode;
}
public BSNode<T> middleFindByKey(T key){
return middleFindByKey(root,key);
}
/**@description
* 查找树(子树)中的最大节点 即后继节点
* @return
* BSNode<T>
*/
public BSNode<T> MaxBode(BSNode<T> tree){
if(isNotNull(tree)){
if(isNotNull(tree.right)){
return MaxBode(tree.right);
}else{
return tree;
}
}else{
return null;
}
}
/**@description
* 查找树(子树)中的最小节点 即前驱节点
* @return
* BSNode<T>
*/
public BSNode<T> MinBode(BSNode<T> tree){
if(isNotNull(tree)){
if(isNotNull(tree.left)){
return MinBode(tree.left);
}else{
return tree;
}
}else{
return null;
}
}
/**@description
* 前序遍历
*/
public void beforeFind(BSNode<T> treeNode){
if(isNotNull(treeNode)){
System.out.println(treeNode.key);
beforeFind(treeNode.left);
beforeFind(treeNode.right);
}else{
}
}
public void beforeFind(){
beforeFind(root);
}
/**@description
* 中序遍历
*/
public void middleFind(BSNode<T> treeNode){
if(isNotNull(treeNode)){
middleFind(treeNode.left);
System.out.println(treeNode.key);
middleFind(treeNode.right);
}else{
}
}
public void middleFind(){
middleFind(root);
}
/**@description
* 后序遍历
*/
public void afterFind(BSNode<T> treeNode){
if(isNotNull(treeNode)){
afterFind(treeNode.left);
afterFind(treeNode.right);
System.out.println(treeNode.key);
}else{
}
}
public void afterFind(){
afterFind(root);
}
/*测试函数*/
public static void main(String[] args) {
BSTree<Integer> bSTree = new BSTree<Integer>();
bSTree.addBSNode(new Integer(2));
bSTree.addBSNode(new Integer(1));
bSTree.addBSNode(new Integer(4));
bSTree.addBSNode(new Integer(3));
bSTree.addBSNode(new Integer(5));
bSTree.addBSNode(new Integer(6));
bSTree.addBSNode(new Integer(9));
bSTree.addBSNode(new Integer(7));
bSTree.addBSNode(new Integer(8));
//bSTree.delBSNode(new Integer(2));
//bSTree.beforeFind();/*先序遍历*/
bSTree.middleFind();/*中序遍历*/
//bSTree.afterFind();/*后序遍历*/
}
}
关于删除的详细算法可参照此文:http://blog.csdn.net/wangyunyun00/article/details/23708055
三.二叉查找树增删改查时间复杂度
3.1 二叉树的所有操作均基于查找: 如果树趋于饱和的话，查找基本等同于折半查找，设所有节点总数N，则查找次数为为时间复杂度为Log2(N+1)（即树的高度）,那么时间复杂度就是LogN；
3.2 修改基于查找，复杂度也是LogN
3.3 新增意味着添加新的叶子节点，只需要查到到合适的添加位置，复杂度也是LogN
3.4 删除的话，如果删除的是节点是叶子节点或者只有一个子树，那么直接删除即可。如果删除的结点有左右子树，那么找到节点后，还需要先查找其前驱或者后继节点，不过这部影响复杂度，复杂度仍为LogN
3.5 另外需要注意的是，实际情况下，二叉查找树并不一定是一颗满树，甚至有可能是一颗线性树(节点数就是树的高度)，那么复杂度就是N;综上，二叉查找树的时间复杂度介于LogN和N之间