#include
using namespace std;
template
struct BiNode{
DataType data;
BiNode *lchild;
BiNode *rchild;
};
template
class BiSortTree
{
public:
BiSortTree(DataType a[],int n);
~BiSortTree(){
DestoryBiSortTree(root);
}
void InsertBST(BiNode *s){
InsertBST(root,s);
}
void DeleteBST(BiNode *f){
DeleteBST(root,f);
}
BiNode *SearchBST(DataType k){
return SearchBST(root,k);
}
void Levershow();
void Inshow(){
Inshow(root);
}
void Preshow(){
Preshow(root);
}
private:
BiNode *root;
void DestoryBiSortTree(BiNode *bt);
void Preshow(BiNode *root);
void Inshow(BiNode *root);
void InsertBST(BiNode *root,BiNode *s);
void DeleteBST(BiNode *p,BiNode *f);
BiNode *SearchBST(BiNode *root,DataType k);
} ;
template
void BiSortTree::InsertBST(BiNode *root,BiNode *s)
{
if(root==NULL) root=s;
else if(root->data>s->data)
InsertBST(root->lchild,s);
else
InsertBST(root->rchild,s);
}
template
BiSortTree::BiSortTree(DataType a[],int n)
{
//root=new BiNode;
root=NULL;
BiNode *s;
for(int i=0;i s=new BiNode;
s->data=a[i];
s->lchild=NULL;
s->rchild=NULL;
InsertBST(root,s);
}
cout<<"完成构造函数" < }
template
void BiSortTree::DeleteBST(BiNode *p,BiNode *f)
{
if((p->lchild==NULL)&&(p->rchild==NULL)){
f->lchild=NULL;
delete p;
}else if(p->rchild==NULL){
f->lchild=p->lchild;
delete p;
}else if(p->rchild==NULL){
f->lchild=p->rchild;
delete p;
}else{
BiNode *parent,*s;
parent=p;
s=p->rchild;
while(s->lchild!=NULL){
parent=s;
s=s->lchild;
}
p->data=s->data;
if(parent==p) parent->rchild=s->rchild;
else parent->lchild=s->rchild;
delete s;
}
}
template
void BiSortTree::DestoryBiSortTree(BiNode *bt)
{
if(bt!=NULL){
DestoryBiSortTree(bt->lchild);
DestoryBiSortTree(bt->rchild);
delete bt;
}
}
template
BiNode *BiSortTree::SearchBST(BiNode *root,DataType k)
{
if(root==NULL) return NULL;
else if(root->data==k) return root;
else if(root->datarchild,k);
else return SearchBST(root->lchild,k);
}
template
void BiSortTree::Levershow(){
cout<<"采用了层序遍历"< BiNode *Q[1000];
int rear=-1,front=-1;
if(root==NULL) return;
Q[++rear]=root;
BiNode *T;
while(rear!=front){
T=Q[++front];
cout<data<<" ";
if(T->lchild!=NULL) Q[++rear]=T->lchild;
if(T->rchild!=NULL) Q[++rear]=T->rchild;
}
}
template
void BiSortTree::Preshow(BiNode *root)
{
cout<<"采用前序非递归算法：";
BiNode *Q[1000];
int top=-1;
if(root==NULL) return;
Q[++top]=root;
while(top!=-1&&root!=NULL)
{
BiNode *T;
while(root!=NULL)
{
T=Q[--top];
cout<data<<" ";
root=root->lchild;
}
if(top!=-1){
root=Q[--top];
root=root->rchild;
}
}
}
template
void BiSortTree::Inshow(BiNode *root)
{
cout<<"采用中序递归算法"< if(root==NULL) return;
else{
Inshow(root->lchild);
cout<<" "<data;
Inshow(root->rchild);
}
}
int main()
{
int n=10;
int a[10]={63,55,90,42,58,70,10,45,67,83};
int k=55;
//cout<<"Inpput the value you want to find:";
//cin>>k;
BiSortTree example(a,n);
example.Inshow();
cout<<"查找节点值为55的节点";
BiNode *p;
p=example.SearchBST(k);
if(p==NULL) cout<<"lll"< //coutdata;
//example.DeleteBST(p->lchild,p);
example.Levershow();
cout<<"插入一个节点值为58的值：";
BiNode *s;
s->data=58;
example.InsertBST(s);
//example.Preshow();
return 0;
}
对于遍历算法可以不用考虑，只需看二叉排序树的建立上为什么建立不成功？
你这个插入函数InsertBST的参数设定应该有问题，你在构造函数里面给这个函数传参的时候传的是指针s和指针root，若想改变s和root，传参的时候应该传指针的引用，或者二级指针。
改成
组合1⃣️二级指针
InsertBST(BNode**root,BNode**s)
传参改成 InsertBST(&root,&s)
组合2⃣️传引用
InsertBST(BNode&*root,BNode&*s)
传参不改InsertBST(&root,&s)
你这个问题应该是值传递，临时拷贝的问题。
可以了解下参数传值，传指针，传引用的区别。
这是我写的一个排序树的建立，希望能对你有所帮助
typedef struct BiTNode{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int a[1005];
void CreatBiTree(BiTree &T,int a[],int n)
{
BiTree p,f,s;
if(n {
T=NULL;
return;
}
T=(BiTree)malloc(sizeof(BiTNode));
T->data =a[0];
T->lchild =T->rchild =NULL;
for(int i=0;i {
f=NULL;
p=T;
while(p)
if(p->data==a[i]) break;
else if(a[i]data )
{
f=p;
p=p->lchild ;
}
else
{
f=p;
p=p->rchild;
}
if(!p)
{
s=(BiTree)malloc(sizeof(BiTNode)) ;
s->data =a[i];
s->lchild =s->rchild =NULL;
if(s->data<f->data)
f->lchild =s;
else
f->rchild=s;
}
}
}
package cn.sxt;
public class BinaryTree {
int data; //根节点数据
BinaryTree left; //左子树
BinaryTree right; //右子树
public BinaryTree(int data) //实例化二叉树类
{
this.data = data;
left = null;
right = null;
}
public void insert(BinaryTree root,int data){ //向二叉树中插入子节点
if(data>root.data) //二叉树的左节点都比根节点小
{
if(root.right==null){
root.right = new BinaryTree(data);
}else{
this.insert(root.right, data);
}
}else{ //二叉树的右节点都比根节点大
if(root.left==null){
root.left = new BinaryTree(data);
}else{
this.insert(root.left, data);
}
}
}
}
package cn.sxt;
public class BinaryTreePreorder {
public static void preOrder(BinaryTree root){ //先根遍历
if(root!=null){
System.out.print(root.data+"-");
preOrder(root.left);
preOrder(root.right);
}
}
public static void inOrder(BinaryTree root){ //中根遍历
if(root!=null){
inOrder(root.left);
System.out.print(root.data+"--");
inOrder(root.right);
}
}
public static void postOrder(BinaryTree root){ //后根遍历
if(root!=null){
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data+"---");
}
}
public static void main(String[] str){
int[] array = {12,76,35,22,16,48,90,46,9,40};
BinaryTree root = new BinaryTree(array[0]); //创建二叉树
for(int i=1;i<array.length;i++){
root.insert(root, array[i]); //向二叉树中插入数据
}
System.out.println("先根遍历：");
preOrder(root);
System.out.println();
System.out.println("中根遍历：");
inOrder(root);
System.out.println();
System.out.println("后根遍历：");
postOrder(root);
}
}