定义：
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的[二叉树]： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为[二叉排序树]
结点的结构代码：
public Node root；
protect int size；
public static class Node {
public Node(Integer value, Node parent, Node left, Node right) {
super();
this.value = value;
this.parent = parent;
this.left = left;
this.right = right;
}
public Integer value;
public Node parent;
public Node left;
public Node right;
public boolean isLeaf() {
return left == null && right == null;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((value == null) ? 0 : value.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (value == null) {
if (other.value != null)
return false;
} else if (!value.equals(other.value))
return false;
return true;
}
}
查询：
#######原理：
如果插入的值比当前结点小，就继续向其左子树继续查找，大就继续向其右子树继续查找，相等就返回当前结点
#######代码：
public Node search(int element) {
Node node = root;
while (node != null && node.value != null && node.value != element) {
if (element < node.value) {
node = node.left;
} else {
node = node.right;
}
}
return node;
}
插入：
#######原理：
如果root是空，则直接插入当前结点到root，否则
定义两个变量，一个searchNode赋值root，一个是insertParent赋值为空，先查询要插入的值，查询过程即搜索二叉树的查询过程，在搜索到结点为空时跳出循环，而insertParent存储每次循环查询前serathNode的值，跳出循环说明，要插入的结点不是在insertParent的左孩子就是右孩子，然后比较大小，大右孩子，小左孩子。
#######代码：
public Node insert(int element) {
if (root == null) {
root = createNode(element, null, null, null);
size++;
return root;
}
Node insertParentNode = null;
Node searchTempNode = root;
while (searchTempNode != null && searchTempNode.value != null) {
insertParentNode = searchTempNode;
if (element < searchTempNode.value) {
searchTempNode = searchTempNode.left;
} else {
searchTempNode = searchTempNode.right;
}
}
Node newNode = createNode(element, insertParentNode, null, null);
if (insertParentNode.value > newNode.value) {
insertParentNode.left = newNode;
} else {
insertParentNode.right = newNode;
}
size++;
return newNode;
}
删除：
#######原理：
看代码注释，总体原理是删除分情况
第一种，要删除结点，他只有左孩子或者右孩子，那么就让他的唯一那个孩子来代替他的环境即可
第二种，要删除的结点他既有左孩子又有右孩子，那么就要选要删除结点的后继节点来替代他的环境，因为他的后继结点就是要删除节点的右子树中最左边的结点，这个结点是他整个右子树的做小的树，而且他还比要删除的结点大，所以选这个结点。在替换环境的时候，要注意全方位替换，即删除结点的左子树环境，右子树环境，父环境都要替换，具体看代码
#######代码：
public Node delete(int element) {
//先查找要删除的结点是否存在
Node deleteNode = search(element);
if (deleteNode != null) {
return delete(deleteNode);
} else {
return null;
}
}
protected Node delete(Node deleteNode) {
if (deleteNode != null) {
Node nodeToReturn = null;
if (deleteNode != null) {
//如果要删除结点的左孩子为空，直接用删除结点的右孩子代替他的位置即可
if (deleteNode.left == null) {
//transplant的作用就是用后面的参数代替前面参数的父环境
nodeToReturn = transplant(deleteNode, deleteNode.right);
} else if (deleteNode.right == null) {
nodeToReturn = transplant(deleteNode, deleteNode.left);
} else {
//获取要删除结点的后继节点，也就是删除结点右孩子的左子树最左的结点，他比要删除的检点大，他是要删除结点右子树的最小值
//所以用它来代替要删除结点的位置
Node successorNode = getMinimum(deleteNode.right);
//又分两中情况，如果要删除结点右孩子的左子树最左的结点就是他自己，就直接用这个节点代替删除结点的环境即可
//否则如下
if (successorNode.parent != deleteNode) {
//用succ结点的右孩子先代替suss结点的父环境
transplant(successorNode, successorNode.right);
//安排要删除结点的右边的子环境，即让删除结点的后继结点succ的右孩子是删除结点的右孩子
successorNode.right = deleteNode.right;
//双向处理，上面一行处理的是让父指向右，这一步是让右指向父
successorNode.right.parent = successorNode;
}
//让succ代替删除节点的父环境
transplant(deleteNode, successorNode);
//让succ代替删除结点的左孩子环境
successorNode.left = deleteNode.left;
successorNode.left.parent = successorNode;
nodeToReturn = successorNode;
}
size--;
}
return nodeToReturn;
}
return null;
}
private Node transplant(Node nodeToReplace, Node newNode) {
if (nodeToReplace.parent == null) {
this.root = newNode;
//要替代结点是他父节点的左孩子
} else if (nodeToReplace == nodeToReplace.parent.left) {
//新节点就变成他父节点新的左孩子
nodeToReplace.parent.left = newNode;
} else {
nodeToReplace.parent.right = newNode;
}
//双向处理
if (newNode != null) {
newNode.parent = nodeToReplace.parent;
}
return newNode;
}
protected Node getMinimum(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
