public class BiSearchTree {
private BiTree root;
public static void main(String[] args) {
BiSearchTree bst = new BiSearchTree();
bst.root = new BiTree(null, null, 45);
bst.insert(bst.root, 24);
bst.insert(bst.root, 53);
bst.insert(bst.root, 12);
bst.insert(bst.root, 90);
bst.insert(bst.root, 30);
bst.insert(bst.root, 25);
System.out.println("构造完成后：");
System.out.println("中序遍历序列为：");
bst.inTraverse(bst.root);
System.out.println();
System.out.println("前序遍历序列为：");
bst.preTraverse(bst.root);
System.out.println();
System.out.println("查找的数据元素为：" + bst.find(bst.root, 24).data);
System.out.println("删除节点45后：");
bst.delete(bst.root, 45);
System.out.println("中序遍历序列为：");
bst.inTraverse(bst.root);
System.out.println();
System.out.println("前序遍历序列为：");
bst.preTraverse(bst.root);
}
public BiTree find(BiTree root, int key) {
if(root == null)return null;
else if(root.data == key)return root;
else if(root.data > key) return find(root.lchild, key);
else return find(root.rchild, key);
}
public void insert(BiTree root, int key) {
if(key < root.data) {
if(root.lchild == null) {
BiTree p = new BiTree(null, null, key);
root.lchild = p;
}
else insert(root.lchild, key);
}
else if(key > root.data) {
if(root.rchild == null) {
BiTree p = new BiTree(null, null, key);
root.rchild = p;
}
else insert(root.rchild, key);
}
return;
}
//分三种情况：左孩子为空，右孩子为空，左右孩子都为空
//当左右孩子都为空时，将被删除节点的左分支节点的最大节点（即左孩子的最右边孩子）复制到被删除节点
public void delete(BiTree root, int key) {
if(root == null)return;
else if(key == root.data) {
if(root.lchild==null) {
root = root.rchild;
}
else if(root.rchild==null) {
root = root.lchild;
}
else{
//q为s的双亲
//s为左孩子的最右边孩子，将其值赋值给被删除节点
BiTree s = root.lchild;
BiTree q = root;
while(s.rchild != null){
q = s;
s = s.rchild;
}
root.data = s.data;
if(q == root) root.lchild = s.lchild;
else q.rchild = s.lchild;
}
}
else if(key < root.data) {
delete(root.lchild, key);
}
else{
delete(root.rchild, key);
}
}
public void inTraverse(BiTree root) {
if(root != null) {
inTraverse(root.lchild);
System.out.print(root.data + " ");
inTraverse(root.rchild);
}
}
public void preTraverse(BiTree root) {
if(root != null) {
System.out.print(root.data + " ");
preTraverse(root.lchild);
preTraverse(root.rchild);
}
}
}
class BiTree {
public BiTree lchild;
public BiTree rchild;
public int data;
public BiTree(BiTree lchild, BiTree rchild, int data) {
super();
this.lchild = lchild;
this.rchild = rchild;
this.data = data;
}
}