1 思想
二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 1.若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2.若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3.任意节点的左、右子树也分别为二叉查找树。 4.没有键值相等的节点（no duplicate nodes）。 复杂度: 插入和查找的时间复杂度均为O(logN), 最坏为O(N)
2 插入
如果当前结点是null，则创建新结点返回。如果插入结点比当前结点值大，则插入其右孩子结点中。如果插入结点比当前结点值小，则插入其左孩子结点中。复杂度: 平均 O(logn) 最坏O(n)<code>public Tree insert(Tree root, int val) {
if (root == null) {
return new Tree(val);
}
if (val == root.val) {
return root;
} else if (val > root.val) {
root.right = insert(root.right, val);
} else {
root.left = insert(root.left, val);
}
return root;
}
/<code>
3 查找
3.1 某个值
思想:查找方式有点类型二分查找方法，知识这里采用的树结构进行存储。首先与根结点进行判断:
如果当前结点为null，则直接放回Null。如果当前结点值与查找值相同则返回当前结点.如果当前结点值小于查找值，则递归地到当前结点的右孩子查找如果当前结点值大于查找值，则递归地到当前结点的左孩子查找。<code>public Tree search(Tree root, int val) {
if(root == null) {
return null;
}
if(root.val == val) {
return root;
} else if(root.val > val) {
return search(root.left, val);
} else {
return search(root.right, val);
}
}/<code>
3.2 查找最小值
思想:根据二叉搜索树的特点，最小结点都是在最左结点上或者如果根结点无左孩子便是其本身.
<code>public Tree min(Tree root) {
if(root == null) {
return null;
}
if (root.left != null) {
return min(root.left);
}
return root;
}/<code>
3.3 查找最大结点
思想: 同最小结点。
<code>public Tree max(Tree root) {
if(root == null) {
return null;
}
if (root.right != null) {
return max(root.right);
}
return root;
}/<code>
4 删除
4.1 删除最小结点
思想:找到根结点最左结点，如果其不存在右孩子则直接删除，否则用右孩子替换最左结点。需要注意的是根结点可能为null和不存在做孩子的情况。
<code>public Tree deleteMin(Tree root) {
if(root == null) {
return null;
}
if(root.left != null) {
root.left = deleteMin(root.left);
} else if (root.right != null) {
return root.right;
}
return null;
}/<code>
4.2 删除最大结点
思想: 与删除最小结点类型，根据二叉搜索树的特性，最大结点是根结点的最右孩子。所以只要找到最右孩子结点，其存在左结点的话就用左结点替换否则直接删除.
<code>public Tree deleteMax(Tree root) {
if(root == null) {
return null;
}
if(root.right != null) {
root.right = deleteMax(root.right);
} else if(root.left != null) {
return root.left;
}
return null;
}/<code>
4.3 删除某个结点
思想:要删除一个结点首先需要找到该结点的位置，采用上面的查找方式进行查找。找到结点后就是删除的问题的，可以按照下面的策略进行删除。
如果一个结点无左孩子和右孩子，那么就可以直接删除如果只存在一个孩子结点，则用孩子结点替换。如果存在两个孩子结点，那么可以用其左孩子最大的结点或右孩子最小结点替换，并删除最左孩子结点或最右孩子结点。<code>public Tree delete(Tree root, int val) {
if(root == null) {
return null;
}
if(root.val == val) {
if(root.left == null && root.right == null) {
return null;
} else if(root.left!= null && root.right != null) {
Tree leftBig = max(root.left);
root.val = leftBig.val;
root.left = delete(root.left, leftBig.val);
} else if(root.left != null){
return root.left;
} else {
return root.right;
}
} else if(root.val < val) {
root.right = delete(root.right, val);
} else {
root.left = delete(root.left, val);
}
return root;
}/<code>
参考: http://www.cnblogs.com/vamei/archive/2013/03/17/2962290.html http://blog.jobbole.com/79305/