这个main函数的测试类要怎么写才好呢，总是出错！怎么实现二叉排序树的插入与删除呢？？？？遍历已经实现了.
import java.io.BufferedReader;排序树 二叉树 java main函数
import java.io.InputStreamReader;
public class BinTreeNode3{ //三叉链结点类
private BinTreeNode3 lChild,rChild,parent; //左右孩子、双亲结点引用
private int data;
public BinTreeNode3(){ //无参构造函数
lChild=null;
rChild=null;
}
public BinTreeNode3(int item){ //带参构造函数
lChild=null;
rChild=null;
data=item;
}
public BinTreeNode3(int item,BinTreeNode3 left,BinTreeNode3 right){
//构造函数
data=item;
lChild=left;
rChild=right;
}
public void setParent(BinTreeNode3 parent){//设置双亲指针
this.parent=parent;
}
public BinTreeNode3 getParent(){ //返回双亲指针
return parent;
}
public void setLeft(BinTreeNode3 left){//设置左孩子
lChild=left;
}
public BinTreeNode3 getLeft(){ //返回左孩子指针
return lChild;
}
public void setRight(BinTreeNode3 right){
//设置右孩子
rChild=right;
}
public BinTreeNode3 getRight(){
//返回右孩子指针
return rChild;
}
public void setData(int data){
//设置数据域
this.data=data;
}
public int getData(){
//设置数据域
return data;
}
public void insertBST(BinTreeNode3 Ra, BinTreeNode3 Rroot){
//将Ra插入到以Rroot为根的二叉排序树中
if(Ra.getData()<Rroot.getData()){
//插入到左子树
if(Rroot.getLeft()==null){
//左孩子空，Ra作为左孩子
Rroot.setLeft(Ra);
Ra.setParent(Rroot);
//同时设置双亲指针
}
else
insertBST(Ra,Rroot.getLeft());
//左孩子非空，Ra插入左子树
}
else{ //插入到右子树
if(Rroot.getRight()==null){ //右孩子空，Ra作为右孩子
Rroot.setRight(Ra);
Ra.setParent(Rroot); //同时设置双亲指针
}
else
insertBST(Ra,Rroot.getRight()); //右孩子非空，Ra插入右子树
}
return ;
}
public BinSearchTree createSortTree(){ //创建二叉排序树
BinSearchTree tree = new BinSearchTree(); //创建二叉排序树对象
try {
int num;
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
num = Integer.parseInt(in.readLine()); //输入整数
BinTreeNode3 Rroot, Ri;
Rroot = new BinTreeNode3(num); //创建根结点
num = Integer.parseInt(in.readLine()); //输入整数
while (num != -1) { //当输入的字符是-1时结束创建
Ri = new BinTreeNode3(num); //创建新结点
insertBST(Ri, Rroot); //插入二叉排序树
num = Integer.parseInt(in.readLine()); //输入整数
}
tree.setRoot(Rroot); //设置对象根结点
} catch (Exception e) {
// TODO: handle exception
}
return tree;
}
}
public class BinSearchTree{
private BinTreeNode3 root;//根结点
public BinSearchTree(){//构造函数
root=null;
}
public BinSearchTree(int item, BinSearchTree left, BinSearchTree right) {
BinTreeNode3 l=null,r=null;
if(left==null)
l=null;
else
l=left.root;
if(right==null)
r=null;
else
r=right.root;
root=new BinTreeNode3(item,l,r);
// TODO Auto-generated constructor stub
}
private void preOrder(BinTreeNode3 r,Visit vs){
//前序遍历
if(r!=null){
vs.print(new Integer(r.getData()));
preOrder(r.getLeft(),vs);
preOrder(r.getRight(),vs);
}
}
private void inOrder(BinTreeNode3 r,Visit vs){
//中序遍历
if(r!=null){
inOrder(r.getLeft(),vs);
vs.print(new Integer(r.getData()));
inOrder(r.getRight(),vs);
}
}
private void postOrder(BinTreeNode3 r,Visit vs){
//后序遍历
if(r!=null){
postOrder(r.getLeft(),vs);
postOrder(r.getRight(),vs);
vs.print(new Integer(r.getData()));
}
}
public void setRoot(BinTreeNode3 r){//设置根结点
root=r;
}
public BinTreeNode3 getRoot(){//返回根结点
return root;
}
public BinTreeNode3 getLeft(BinTreeNode3 curr){//返回左孩子
return curr!=null?curr.getLeft():null;
}
public BinTreeNode3 getRight(BinTreeNode3 curr){//返回右孩子
return curr!=null?curr.getRight():null;
}
public void preOrder(Visit vs){//前序遍历
preOrder(root,vs);
}
public void inOrder(Visit vs){//中序遍历
inOrder(root,vs);
}
public void postOrder(Visit vs){//后序遍历
postOrder(root,vs);
}
public void insert(BinTreeNode3 p,int item){ //插入结点
if(item<p.getData()){ //比较，获得插入位置
if(p.getLeft()==null){//插入
BinTreeNode3 temp=new BinTreeNode3(item); //生成新结点
temp.setParent(p);//设置双亲指针
p.setLeft(temp);
//插入结点作为左孩子
}
else
insert(p.getLeft(),item);
//在左子树插入
}
else if(item>p.getData()){ //在右子树插入
if(p.getRight()==null){
//插入
BinTreeNode3 temp=new BinTreeNode3(item);//生成新结点
temp.setParent(p); //设置双亲结点
p.setRight(temp);
//插入结点作为右孩子
}
else
insert(p.getRight(),item);
//在右子树插入
}
return;
}
public void delete(BinTreeNode3 p, int item){
//删除结点
if(p!=null){
if(item<p.getData()) //在左子树中删除
delete(p.getLeft(),item);
//在左子树中递归搜索
else if(item>p.getData()) //在右子树中删除
delete(p.getRight(),item);
//在右子树中递归搜索
else if(p.getLeft()!=null && p.getRight()!=null){ //相等且该结点有左右子树
BinTreeNode3 temp;
temp=p.getRight();
//查找右子树中的直接后继
while(temp.getLeft()!=null) //找右子树的最左孩子
temp=temp.getLeft();
p.setData(temp.getData()); //复制数据域
delete(p.getRight(),temp.getData()); //递归删除p结点
}
else{
if(p.getLeft()==null && p.getRight()!=null){
//左子树空
//p的双亲的右孩子指向p的右孩子
p.getParent().setRight(p.getRight());
//p的右孩子的双亲指向p的双亲
p.getRight().setParent(p.getParent());
}
else if(p.getRight()==null && p.getLeft()!=null)
{//右子树空
//p的双亲的左孩子指向p的左孩子
p.getParent().setLeft(p.getLeft());
//p的左孩子的双亲指针指向p的双亲
p.getLeft().setParent(p.getParent());
}
else{//无孩子结点，即叶子结点
BinTreeNode3 temp=p.getParent();
if(temp.getLeft()==p)//如果待删除结点在双亲的左孩子上
temp.setLeft(null);//双亲的左孩子指针置空
else//如果待删除结点在双亲的右孩子上
temp.setRight(null); //双亲的右孩子指针置空
}
}
}
}
public class Visit {
public void print(Object item){
System.out.print(item+"");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
BinSearchTree t4=new BinSearchTree(4,null,null);
BinSearchTree t2=new BinSearchTree(2,t4,null);
BinSearchTree t5=new BinSearchTree(5,null,null);
BinSearchTree t7=new BinSearchTree(7,null,null);
BinSearchTree t6=new BinSearchTree(6,null,t7);
BinSearchTree t3=new BinSearchTree(3,t5,t6);
BinSearchTree t =new BinSearchTree(1,t2,t3);
Visit vs=new Visit();
System.out.println("前序");
t.preOrder(t.getRoot(),vs);
System.out.println("\r\n中序");
t.inOrder(t.getRoot(),vs);
System.out.println("\r\n后序");
t.postOrder(t.getRoot(),vs);
BinTreeNode3 p=new BinTreeNode3();
System.out.println("Insert a number into the tree:");
//t.insert(t.getRoot(),p);
}
}
