这个main函数的测试类要如何写才好呢，总是出错！如何实现二叉排序树的插入与删除呢？遍历已经实现了
日期：2014-05-20 浏览次数：20744 次
这个main函数的测试类要怎么写才好呢，总是出错！怎么实现二叉排序树的插入与删除呢？？？？遍历已经实现了.
import java.io.BufferedReader;
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
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
