二叉查找树
- 基本性质：对任何节点x,其左子树的任意key不大于x.key,其右子树的任意节点不小于x.key
- 实现集合操作 search，minimum，maximum，predecessor，successor，insert，delete
- 以上操作的最坏运行时间与树的高度成正比，平均时间复杂度O(h)，其中h为树的高度
- 树的中序遍历是有序序列
- 可以用其实现有序字典，优先队列，实现时间复杂度O(h)
树的基本节点
每个节点除了key和卫星数据外，还有left,right,p表示左右孩子和父节点
public class TreeNode {
public int key;
public TreeNode left;
public TreeNode right;
public TreeNode p;
public TreeNode(int key){
this.key=key;
}
@Override
public String toString() {
return key+"";
}
} 基本操作实现
实现操作：求最大 ，最小，查找，插入，删除，前驱，后继
public class BinarySearchTree {
private TreeNode root;
public TreeNode minimum(){
return minimum(root);
}
public TreeNode maximum(){
return maximum(root);
}
//如果存在右孩子，右子树最小值即为后继，否则，后继为向祖先回溯过程中的第一个做为祖先左孩子的节点的父节点
public TreeNode successor(TreeNode x){
if (x == null){
return null;
}
if (x.right != null){
return minimum(x.right);
}else{
TreeNode y = x.p;
while(y!=null && x == y.right){
x = y;
y = y.p;
}
return y;
}
}
//如果存在左子树，前驱为左子树的最大节点，否则前驱为向其祖先回溯过程中第一个为其祖先的右孩子的节点的父节点
public TreeNode predecessor(TreeNode x){
if(x==null){
return null;
}
if(x.left != null){
return maximum(x.left);
}else{
TreeNode y = x.p;
while(y!=null && x == y.left){
x = y;
y = y.p;
}
return y;
}
}
// 中序遍历为有序序列
public void walk(){
inOrderTraversal(root);
}
// 查找值小于当前节点就到当前节点左子树，大于当前节点就到右子树，否则返回当前节点
public TreeNode search(int key){
TreeNode node = root;
while(node!=null){
if(key < node.key){
node = node.left;
}else if(key>node.key){
node = node.right;
}else{
return node;
}
}
return null;
}
public TreeNode recursiveSearch(TreeNode root, int key){
if(root==null || root.key==key){
return root;
}else if(key>root.key){
return recursiveSearch(root.right,key);
}else{
return recursiveSearch(root.left,key);
}
}
// 待插入值小于当前节点就到当前节点左子树，否则跳就到右子树，直到叶子节点，根据最后的比较情况将当前节点作为该叶子节点的左孩子或者右孩子
public void insert(TreeNode node){
TreeNode p = null;
TreeNode t = root;
while(t != null){
p = t;
if(node.key < t.key){
t = t.left;
}else{
t = t.right;
}
}
node.p = p;
if(p == null){
root = node;
}else if(node.key > p.key){
p.right = node;
}else{
p.left = node;
}
}
//分三种情况：1. 如果节点没有左子树或者右子树就直接将右孩子或左孩子替换当前节点 2. 如果既有左孩子，又有右孩子，且右孩子为当前节点的直接后继（右孩子没有左孩子），将节点右孩子替换当前节点并将当前节点左孩子连接到当前节点右孩子上 3. 否则，假设右子树的最小节点s（没有左孩子），首先将s的右孩子替换s，再用s替换当前节点，并将当前节点的左右孩子赋值给s的左右孩子
public void delete(TreeNode node){
if(node.left == null){
transplant(node, node.right);
}else if(node.right == null){
transplant(node, node.left);
}else{
TreeNode s = minimum(node.right);
if(s.p != node){
transplant(s,s.right);
s.right = node.right;
s.right.p = s;
}
transplant(node,s);
s.left = node.left;
s.left.p = s;
}
}
private void transplant(TreeNode u,TreeNode v){
if(u.p == null){
root = v;
}else if(u == u.p.left){
u.p.left = v;
}else{
u.p.right = v;
}
if(v != null){
v.p = u.p;
}
}
private TreeNode minimum(TreeNode x){
if(root == null){
return null;
}
while(x.left != null){
x = x.left;
}
return x;
}
private TreeNode maximum(TreeNode x){
if(x==null){
return null;
}
while(x.right!=null){
x = x.right;
}
return x;
}
private void inOrderTraversal(TreeNode root){
if(root == null){
return;
}
Stack<TreeNode> s = new Stack<TreeNode>();
while(true){
while(root!=null){
s.push(root);
root = root.left;
}
if(s.isEmpty()){
return;
}
TreeNode node = s.pop();
System.out.println(node.key);
root = node.right;
}
}验证
public class BinarySearchTreeDemo {
// 层序遍历打印一棵树，其中#代表null节点，为方便阅读去掉了代表叶子节点的null孩子的#符号
public static void printTree(TreeNode root){
Queue<TreeNode> q = new LinkedList<TreeNode>();
StringBuilder sb = new StringBuilder();
q.offer(root);
while(!q.isEmpty() ){
TreeNode node = q.poll();
if(node == null){
sb.append("#");
continue;
}else{
sb.append(node.key);
q.offer(node.left);
q.offer(node.right);
}
}
int p=sb.length();
while(p>0){
if(sb.charAt(p-1)!='#'){
break;
}
p--;
}
System.out.println(sb.substring(0,p).toString());
}
public static void main(String[] args) {
TreeNode root = new TreeNode(0);
TreeNode one = new TreeNode(1);
TreeNode two = new TreeNode(2);
TreeNode three = new TreeNode(3);
TreeNode four = new TreeNode(4);
TreeNode five = new TreeNode(5);
BinarySearchTree bst = new BinarySearchTree();
bst.insert(one);
bst.insert(three);
bst.insert(root);
bst.insert(four);
bst.insert(five);
bst.insert(two);
bst.walk();
System.out.println(bst.minimum());
System.out.println(bst.maximum());
bst.delete(one);
bst.walk();
printTree(two);
System.out.println(bst.search(1));
System.out.println(bst.search(4));
System.out.println(bst.predecessor(two));
System.out.println(bst.successor(root));
}
} 