编程论坛 » 数据结构与算法 » 急！一个二叉排序树算法程序，运行时有错误，大家请帮忙改改

jiajiaj 发表于 2007-12-15 09:00

急！一个二叉排序树算法程序，运行时有错误，大家请帮忙改改

请大家帮忙看看，谢谢…
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAX 50

typedef struct BNode{
        char data;
        struct BNode *lchild;
        struct BNode *rchild;
}BNode;//,*BiTree;
typedef BNode *BiTree;

//插入新结点
int InsertNode(BiTree *T,char e){
        BNode *f,*p;
        p=*T;
        while(p){
                f=p;
                if(p->data==e) return 0;
                else if(e<p->data) p=p->lchild;
                else p=p->rchild;
        }
        p=(BiTree)malloc(sizeof(BNode));
        p->data=e;
        p->lchild=NULL;
        p->rchild=NULL;
        if(*T==NULL) *T=p;
        else if(e<f->data) f->lchild=p;
        else f->rchild=p;
        return 1;
}

//二叉排序树的创建
BiTree Creat(BiTree T){
        //BiTree T=NULL;
        T=NULL;
        char e;
        scanf("%c",&e);
        while(e!='#'){
                InsertNode(&T,e);
                scanf("%c",&e);
        }
        return T;
}

//前序遍历二叉树
int ProTree(BiTree T){
        BiTree p=T;
        if(p){
        printf("%c",p->data);
        ProTree(p->lchild);
    ProTree(p->rchild);
        return 1;
        }
}

//中序遍历二叉树
int MidTree(BiTree T){
        BiTree p=T;
        if(p==NULL) return 0;
    MidTree(p->lchild);
        printf("%c",p->data);
        MidTree(p->rchild);
        return 1;
}

void main(){
    BiTree T;
    Creat(T);
    ProTree(T);
}

jiajiaj 发表于 2007-12-15 12:27

请大家帮帮忙改改。。。

yf_xiaobu 发表于 2007-12-15 14:50

回复 2# 的帖子

#include<iostream>
#include<queue>

using namespace std;

class bftree;
class bfnode
{
        friend class bftree;
private:
        int data;
        bfnode *lchild,*rchild;
public:
        bfnode(int x){data=x;lchild=rchild=0;}
};

///////////////////////////////////////////////

class bftree
{
private:
        bfnode *root;
        void print(bfnode *a);
public:
        bftree(){root=0;}
        bool IsEmpty();
        bfnode* combine(bfnode *a,bfnode *b);        //做二叉查找树的两个子树的合并
        bool Insert(int x);                                                //插入                               
        bool Find(int x);                                                //查找
        void Delete(int x);                                                //删除元素x
        void ioPrint(){cout<<"中序："<<endl;print(root);cout<<endl;}//中序遍历驱动程序
        void levelprint();                                                                                        //层次遍历
       
};

//////////////////////

bool bftree::IsEmpty()
{
        if(!root)
        {
                cout<<"empty"<<endl;
                return true;
        }
        cout<<"not empty"<<endl;
        return false;
}

/////////////////////////////

bool bftree::Insert(int x)
{
        bfnode *y=new bfnode(x);
       
        if(!root)
        {
                root=y;
                return true;
        }

        bfnode *p,*q;
        p=root;
        q=0;
       
        while(p)
        {
                q=p;
                if(x<p->data)p=p->lchild;
                else if(x>p->data)p=p->rchild;
                else
                {
                        //cout<<x<<"已经存在，不能插入"<<endl;
                        return false;
                }
        }
        if(x<q->data)q->lchild=y;
        else q->rchild=y;
        return true;
}

////////////////////////////////

bool bftree::Find(int x)
{
        bfnode *current=root;
        while(current)
        {
                if(x<current->data)current=current->lchild;
                else if(x>current->data)current=current->rchild;
                else
                {
                        return true;
                }

        }
        return false;
}

/////////////////////////////

void bftree::Delete(int x)
{
        bfnode *p=root,*q=0;

        while(p)
        {
                if(x<p->data)
                {
                        q=p;p=p->lchild;
                }
                else if(x>p->data)
                {
                        q=p;p=p->rchild;
                }
                else break;
        }
        if(p)
        {
                cout<<x<<"在二叉查找树中，并将它删除"<<endl;
                bfnode *pl,*pr,*a;//a作为新的根（子树）
                pl=p->lchild;pr=p->rchild;
                a=combine(pl,pr);
                if(p==q->lchild)q->lchild=a;
                else q->rchild=a;
        }
        else{cout<<x<<"不在二叉查找树中"<<endl;}       
}

///////////////////////////////////////////

bfnode * bftree::combine(bfnode *a,bfnode *b)
{
        if(!a)return b;
        else if(!b)return a;
        bfnode *p=a,*q=0;
        while(p&&p->rchild)
        {
                q=p;
                p=p->rchild;
        }
        q->rchild=p->lchild;
        p->lchild=a;
        p->rchild=b;
        return p;
}


//////////////////////////////////////////////////////////

void bftree::print(bfnode *a)
{
        if(a)
        {
                print(a->lchild);
                cout<<a->data<<'\t';
                print(a->rchild);
        }
}


void bftree::levelprint()
{
        cout<<"按层次："<<endl;
        queue<bfnode *>myq;
        bfnode *currentnode=root;
        myq.push(currentnode);
        while(!myq.empty())
        {
                currentnode=myq.front();
                myq.pop();
                cout<<currentnode->data<<'\t';
                if(currentnode->lchild)myq.push(currentnode->lchild);
                if(currentnode->rchild)myq.push(currentnode->rchild);
        }
        cout<<endl;
}




void main()
{
        rand();
        bftree bft;
        bft.IsEmpty();

        for(int i=0;i<20;i++)bft.Insert(rand());
        bft.Insert(2222);

        bft.ioPrint();
        cout<<endl;
        bft.levelprint();

        int a=rand();

        if(bft.Find(a))cout<<a<<"在二叉查找树中"<<endl;
        else cout<<a<<"不在二叉查找树中"<<endl;

       
        bft.Delete(2222);
        bft.ioPrint();
        cout<<endl;
        bft.levelprint();

        bft.Delete(1);

}

missiyou 发表于 2007-12-15 21:13

没有看出什么错误呀，调用Create()错了，应该是，T=Create();

柒兲 发表于 2007-12-16 12:20

#include <stdio.h>
#include <malloc.h>

typedef struct btnode
{
        char ch;
        struct btnode *lchild,*rchild;
}BTnode;

BTnode *Create()
{
        BTnode *root,*p,*a[100];
        int num;
        char str;
        int j=0;
        printf("\n");
        printf("请输入你要创建树结点的编号和值(请以0和#结束)\n");
        printf("i,string\n");
        scanf("%d,%c",&num,&str);
        getchar();
        while(num!=0 && str !='#')
        {
                p=(BTnode *)malloc(sizeof(BTnode));
            p->ch=str;
                p->lchild=p->rchild=NULL;
                a[num]=p;
                if(num==1)
                        root=p;
                else
                {
                        j=num/2;
                        if(num%2==0)
                                a[j]->lchild=p;
                        else
                                a[j]->rchild=p;
                }
                scanf("%d,%c",&num,&str);
            getchar();
        }
        return root;
}

void Preorder(BTnode *p)//先根遍历
{
        if(p)
        {
                printf("->%c",p->ch);
                Preorder(p->lchild);
                Preorder(p->rchild);
        }
}
void Inorder(BTnode *p)//中根遍历
{
        if(p)
        {
                Inorder(p->lchild);
                printf("->%c",p->ch);
                Inorder(p->rchild);
        }
}
void Posorder(BTnode *p)//先根遍历
{
        if(p)
        {       
                Posorder(p->lchild);
                Posorder(p->rchild);
                printf("->%c",p->ch);
        }
}

void main()
{
    BTnode *head;
        head=Create();
        printf("先根遍历,结果为 ：");
        Preorder(head);
        printf("\n");
        printf("中根遍历,结果为 ：");
        Inorder(head);
        printf("\n");
    printf("后根遍历,结果为 ：");
        Posorder(head);
        printf("\n");
}

scau 发表于 2007-12-18 16:20

我改了一下

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAX 50

typedef struct BNode{
    char data;
    struct BNode *lchild;
    struct BNode *rchild;
}BNode;
typedef BNode *BiTree;

/**插入新结点   **/
int InsertNode(BiTree *T,char e){
    BNode *f,*p;
    p=*T;
    while(p){
        f=p;
        if(p->data==e) return 0;
        else if(e<p->data) p=p->lchild;
        else p=p->rchild;
    }
    p=(BiTree)malloc(sizeof(BNode));
    p->data=e;
    p->lchild=NULL;
    p->rchild=NULL;
    if(*T==NULL) *T=p;
    else if(e<f->data) f->lchild=p;
    else f->rchild=p;
    return 1;
}

/**二叉排序树的创建 **/
BiTree Creat(BiTree T){
    /**BiTree T=NULL;**/
        char e;
        T=NULL;
    scanf("%c",&e);
    while(e!='#'){
        InsertNode(&T,e);
        scanf("%c",&e);
    }
    return T;
}

/**前序遍历二叉树 **/
int ProTree(BiTree T){
    BiTree p=T;
    if(p){
    printf("%c",p->data);
    ProTree(p->lchild);
    ProTree(p->rchild);
    return 1;
    }
}

/**中序遍历二叉树   **/
int MidTree(BiTree T){
    BiTree p=T;
    if(p==NULL) return 0;
    MidTree(p->lchild);
    printf("%c",p->data);
    MidTree(p->rchild);
    return 1;
}

void main(){
    BiTree T;
    Creat(T);
    ProTree(T);
}

jiajiaj 发表于 2007-12-19 22:09

回复 6# 的帖子

先谢谢了[em01] 。。。你那边可以正常运行的吗？怎么我这里输入数后不能遍历输出来的？

zerozou 发表于 2007-12-21 19:51

6#不错哦
可以的
只是你的程序在输出的时候，可以在设计一下

查看完整版本: 急！一个二叉排序树算法程序，运行时有错误，大家请帮忙改改