二叉查找树(二叉排序树)在二叉树的基础上，增加了
节点总数是n，那么查找节点的时间复杂度就是O(logn)，
中序遍历二叉查找树，输出结果完全按照升序排列
插入和和查找过程是类似的，定位插入的位置
没有孩子，因此直接删除即可：
让孩子节点取代被删除的节点，孩子节点以下的节点关系无须变动：
需要选择与待删除节点最接近的节点来取代它
习惯上我们选择仅大于待删除节点的节点，
（被选中的节点6，仅大于节点5，因此一定没有左孩子。所以我们按照情况1或情况2的方式，删除多余的节点6：）
// 结点类
private class Node {
int data;
Node right;
Node left;
Node(int data){
this.data = data;
}
}
//根节点引用（指针）
private Node root;
//插入结点
public boolean insert(int data) {
Node node = new Node(data);
if(root == null){
root = node;
return true;
}
Node targetNode = root;
while (targetNode != null) {
if( data == targetNode.data){
System.out.println("二叉查找树中已有重复的结点：" + data);
return false;
}
else if (data > targetNode.data) {
if(targetNode.right == null){
targetNode.right = node;
return true;
}
targetNode = targetNode.right;
}
else {
if(targetNode.left == null){
targetNode.left = node;
return true;
}
targetNode = targetNode.left;
}
}
return true;
}
//中序遍历
public static void inOrderTraversal(Node node){
if(node == null){
return;
}
inOrderTraversal(node.left);
System.out.print(node.data + " ");
inOrderTraversal(node.right);
}
//查找结点
public Node search(int data) {
Node targetNode = root;
while (targetNode!=null && targetNode.data != data) {
if (data > targetNode.data) {
targetNode = targetNode.right;
} else {
targetNode = targetNode.left;
}
}
if(targetNode == null){
System.out.println("未找到结点：" + data);
} else {
System.out.println("已找到结点：" + data);
}
return targetNode;
}
//删除结点
public boolean delete(int data) {
Node targetNode = root;
Node parentNode = new Node(data);
//判断待删除结点是否存在
while (targetNode.data != data) {
parentNode = targetNode;
if (data > targetNode.data) {
targetNode = targetNode.right;
} else {
targetNode = targetNode.left;
}
if (targetNode == null) {
// 没有找到待删除结点
return false;
}
}
// 待删除结点没有子节点
if (targetNode.right==null && targetNode.left==null) {
if (targetNode == root) {
//待删除结点是根结点
root = null;
} else {
if (parentNode.right == targetNode) {
parentNode.right = null;
} else {
parentNode.left = null;
}
}
}
//待删除结点有一个子结点（右）
else if(targetNode.left == null) {
if(targetNode == root) {
root = targetNode.right;
} else if(parentNode.right == targetNode) {
parentNode.right = targetNode.right;
} else {
parentNode.left = targetNode.right;
}
}
//待删除结点有一个子结点（左）
else if(targetNode.right == null) {
if(targetNode == root) {
root = targetNode.left;
} else if(parentNode.right == targetNode) {
parentNode.right = targetNode.left;
} else {
parentNode.left = targetNode.left;
}
}
//待删除结点有两个子结点
else {
//待删除结点的后继结点的父结点
Node successParentNode = targetNode;
//待删除结点的后继结点
Node successNode = targetNode.right;
//这一个while循环找到删除节点的子节点中，刚好比删除节点大的那个节点的值
//这个值就是退出循环的successNode.data
while(successNode.left != null)
{
successParentNode = successNode;
successNode = successNode.left;
}
//把后继结点复制到待删除结点位置
targetNode.data = successNode.data;
//删除后继结点
//被选中的节点，仅大于待删除的节点，因此一定被选中的节点successNode一定没有左孩子。
//successNode只可能有：successNode.right
// 所以我们按照情况1或情况2的方式，删除多余的节点successNode：
//这里我感觉只要else {
// successParentNode.left = successNode.right;
// }就行了，应为successNode是仅大于待删除的节点。
if(successParentNode.right == successNode) {
successParentNode.right = successNode.right;
//System.out.println("xxxx");
} else {
successParentNode.left = successNode.right;
}
}
return true;
}
测试方法：
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
int input[]= {6,3,8,2,5,7,9,1,4};
for(int i=0; i<input.length; i++) {
tree.insert(input[i]);
}
inOrderTraversal(tree.root);
System.out.println();
tree.search(3);
tree.delete(3);
tree.search(3);
tree.delete(6);
inOrderTraversal(tree.root);
}
虽然这样一棵树也符合二叉查找树的特性，但是查找节点的时间复杂度退化成了O(n)。
要解决这个问题，需要用到平衡二叉树