BST
启发式搜索算法有点像广度优先搜索，不同的是，它会优先顺着有启发性和具有特定信息的节点搜索下去，这些节点可能是到达目标的最好路径。 我们称这个过程为最优（best-first）或启发式搜索。 下面是其基本思想： 1) 假定有一个启发式(评估)函数ˆf ，可以帮助确定下一个要扩展的最优节点， 我们采用一个约定，即ˆf的值小表示找到了好的节点。 这个函数基于指定问题域的信息，它是状态描述的一个实数值函数。 2) 下一个要扩展的节点n是ˆf(n)值最小的节点(假定节点扩展产生一个节点的所有后 继)。 3) 当下一个要扩展的节点是目标节点时过程终止。
节点类
package com.landry.algorithm;
public class BinaryNode<T> {
T data;
BinaryNode<T> left;
BinaryNode<T> right;
public BinaryNode(T data) {
this(data, null, null);
}
public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
this.data = data;
this.left = left;
this.right = right;
}
public BinaryNode() {
data = null;
this.left = left;
this.right = right;
}
}
BST类。主要实现了remove方法。
package com.landry.algorithm;
/**
* Java实现二叉查找树
*
* @param <T>
* @author Kiritor
*/
public class BinarySearchTree<T extends Comparable<? super T>> {
/**
* 结点数据结构
*/
private BinaryNode<T> rootTree;
/**
* 构造一颗空的二叉查找树
*/
public BinarySearchTree() {
rootTree = null;
}
/**
* 清空二叉查找树
*/
public void clear() {
rootTree = null;
}
/**
* 判断是否为空
*/
public boolean isEmpty() {
return rootTree == null;
}
/**
* 查找指定的元素,默认从
* 根结点出开始查询
*/
public boolean contains(T t) {
return contains(t, rootTree);
}
/**
* 找到二叉查找树中的最小值
*/
public T findMin() {
if (isEmpty()) {
System.out.println("二叉树为空");
return null;
} else
return findMin(rootTree).data;
}
/**
* 找到二叉查找树中的最大值
*/
public T findMax() {
if (isEmpty()) {
System.out.println("二叉树为空");
return null;
} else
return findMax(rootTree).data;
}
/**
* 插入元素
*/
public void insert(T t) {
rootTree = insert(t, rootTree);
}
/**
* 删除元素
*/
public void remove(T t) {
// rootTree = remove(t, rootTree);
//exceptions
BinaryNode<T> temp = rootTree;
//使用哨兵，避免要删除的是根节点。
BinaryNode<T> temp_parent = new BinaryNode<T>(null,rootTree,null);
boolean isLeft = true;
while (null != temp) {
if(t.compareTo(temp.data) < 0) {
temp_parent = temp;
isLeft = true;
temp = temp.left;
} else if (t.compareTo(temp.data) > 0) {
temp_parent = temp;
isLeft = false;
temp = temp.right;
} else {
break;
}
}
//not found.
if (null == temp) {
return ;
}
if (null == temp.left || null == temp.right) {
BinaryNode<T> node = null == temp.left ? temp.right : temp.left;
if(true == isLeft) {
temp_parent.left = node;
} else {
temp_parent.right = node;
}
} else {
//寻找最小的节点,取出其内容复制给temp ，并删除掉这个最小节点
BinaryNode<T> node = temp.right;
if(null == node.left) {
//temp.right最小
temp.data = temp.right.data;
temp.right = temp.right.right;
} else {
while (null != node.left && null != node.left.left) {
node = node.left;
}
//node.left not null but node.left.left null
//so node.left 最小
temp.data = node.left.data;
node.left = node.left.right;
}
}
rootTree = temp_parent.left;
}
/**
* 从某个结点出开始查找元素,node是一颗BST的根结点
*/
private boolean contains(T t, BinaryNode<T> node) {
if (node == null)
return false;
int result = t.compareTo(node.data);
if (result > 0)
return contains(t, node.right);
else if (result < 0)
return contains(t, node.left);
else
return true;
}
/**
* 查询出最小元素所在的结点,node是一颗BST的根结点
*/
private BinaryNode<T> findMin(BinaryNode<T> node) {
/**
*
if(node==null)
return null;
else if(node.left==null)
return node;
return findMin(node.left);//递归查找
*/
if (null == node) {
return null;
}
while (null != node.left) {
node = node.left;
}
return node;
}
/**
* 查询出最大元素所在的结点,node是一颗BST的根结点
*/
private BinaryNode<T> findMax(BinaryNode<T> node) {
if (node != null) {
while (node.right != null)
node = node.right;
}
return node;
}
/**
* 在某个位置开始判断插入元素,node是一颗BST的根结点
*/
private BinaryNode<T> insert(T t, BinaryNode<T> node) {
if (node == null) {
//新构造一个二叉查找树
return new BinaryNode<T>(t, null, null);
}
int result = t.compareTo(node.data);
if (result < 0)
node.left = insert(t, node.left);
else if (result > 0)
node.right = insert(t, node.right);
else
;//doNothing
return node;
}
/**
* 在某个位置开始判断删除某个结点,node是一颗BST的根结点
*/
/*private BinaryNode<T> remove(T t, BinaryNode<T> node) {
if (node == null)
return node;//没有找到,doNothing
int result = t.compareTo(node.data);
if (result > 0)
node.right = remove(t, node.right);
else if (result < 0)
node.left = remove(t, node.left);
else if (node.left != null && node.right != null) {
node.data = findMin(node.right).data;
node.right = remove(node.data, node.right);
} else
node = (node.left != null) ? node.left : node.right;
return node;
}*/
}