//
//实现了如下功能
public class BinarySearchTree {/** * * @author Administrator *嵌套类构造结点 * @param <Integer> */private static class BinaryNode<Integer>{public Integer data;public BinaryNode<Integer> lchild;public BinaryNode<Integer> rchild;public BinaryNode(Integer d,BinaryNode<Integer> l,BinaryNode<Integer> r){this.data = d;this.lchild = l;this.rchild = r;}}//根节点private BinaryNode<Integer> root;public BinarySearchTree(){root = null;}/** * 返回根节点 * @param x * @param r * @return */public BinaryNode<Integer> add(Integer x,BinaryNode<Integer> r){BinaryNode<Integer> tmp = r;BinaryNode<Integer> p = new BinaryNode<Integer>(x,null,null);if(r == null){r = p;}else{while(tmp.lchild!=p && tmp.rchild != p){if(x<tmp.data){if(tmp.lchild == null){tmp.lchild = p;}else{tmp = tmp.lchild;} }else if(x>tmp.data){ if(tmp.rchild == null){tmp.rchild = p;}else{tmp = tmp.rchild;}}}}return r;}/** * 返回最小的结点 * @param r * @return */public BinaryNode<Integer> findMin(BinaryNode<Integer> r){if(r != null){while(r.lchild != null){r = r.lchild;}}return r;}/** * 返回最大的结点 * @param r * @return */public BinaryNode<Integer> findMax(BinaryNode<Integer> r){if(r != null){while(r.rchild != null){r = r.rchild;}}return r;}//删除一个节点public BinaryNode<Integer> remove(Integer x,BinaryNode<Integer> r){BinaryNode<Integer> tmp = r;BinaryNode<Integer> p = null ;//指示目标结点的父亲if(r == null){throw new NullPointerException();}while(tmp.data != x){if(x<tmp.data){p = tmp;tmp = tmp.lchild;}else if(x<tmp.data){p = tmp;tmp = tmp.rchild;}}//如果待删结点是叶子结点if(tmp.lchild == null && tmp.rchild == null){if(tmp == r){tmp = null; //若为根节点，将根节点置空}else if(p.lchild == tmp){p.lchild = null;}else{p.rchild = null;}}else//如果为单叶子结点if(tmp.lchild == null || tmp.rchild == null){if(tmp == r){if(tmp.lchild == null){tmp = tmp.rchild;}else if(tmp.rchild == null){tmp = tmp.lchild;}}elseif(p.lchild == tmp){if(tmp.lchild == null){p.lchild = tmp.rchild;}else if(tmp.rchild == null){p.lchild = tmp.lchild;}} else if(p.rchild == tmp){if(tmp.lchild == null){p.lchild = tmp.rchild;}else if(tmp.rchild == null){p.lchild = tmp.lchild;}}}else {//目标结点的子结点都不为空BinaryNode<Integer> a = tmp ;BinaryNode<Integer> b = tmp.rchild ;while(b.lchild != null){//选右边数最小的数据a = b;b = b.lchild;}tmp.data = b.data;if(a == tmp){tmp.rchild = b.rchild;//若目标结点的右子结点没有左子节点}else{a.lchild = b.rchild;}}return r;}}
