Frost_Jiang
2015-06-28 02:42
采纳率: 50%
浏览 2.2k
已采纳

求助C语言大神! 二叉排序树

求用C实现:输入初始关键字序列,构造一个二叉排序树。 谢谢!
不用C++

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 收藏
  • 邀请回答

4条回答 默认 最新

  • 江南丨烟雨 2015-06-28 02:47
    已采纳
     // 二叉树_C.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include "malloc.h"
    #define MAX 1240
    
    typedef struct bitnode
    {
        char data;
        struct bitnode *lchild,*rchild;
    }BiTNode,*BiTree;
    
    /*初始化*/
    BiTree Initiate()
    {
        BiTNode *bt;
        bt=NULL;
        return bt;
    }
    
    /*生成根节点*/
    BiTree Create(char x,BiTree lbt,BiTree rbt)
    {
        BiTree p;
        if((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL)return NULL;
        p->data=x;
        p->lchild=lbt;
        p->rchild=rbt;
        return p;
    }
    
    /*添加左节点*/
    BiTree InsertL(BiTree bt,char x,BiTree parent)
    {
        BiTree p;
        if(parent==NULL)
        {
            printf("\n插入出错!\n");
            return NULL;
        }
        if((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL;
        p->data=x;
        p->lchild=NULL;
        p->rchild=NULL;
        if(parent->lchild==NULL) parent->lchild=p;
        else
        {
            p->lchild=parent->lchild;
            parent->lchild=p;
        }
        return bt;
    }
    
    /*添加右节点*/
    BiTree InsertR(BiTree bt,char x,BiTree parent)
    {
        BiTree p;
        if(parent==NULL)
        {
            printf("\n插入出错!");
            return NULL;
        }
        if((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL;
        p->data=x;
        p->lchild=NULL;
        p->rchild=NULL;
        if(parent->rchild==NULL) parent->rchild=p;
        else
        {
            p->rchild=parent->rchild;
            parent->rchild=p;
        }
        return bt;
    }
    
    /*删除左子树*/
    BiTree DeleteL(BiTree bt,BiTree parent)
    {
        BiTree p;
        if(parent==NULL||parent->lchild==NULL)
        {
            printf("\n删除出错!");
            return NULL;
        }
        p=parent->lchild;
        parent->lchild=NULL;
        free(p);
        return bt;
    }
    
    /*删除右子树*/
    BiTree DeleteR(BiTree bt,BiTree parent)
    {
        BiTree p;
        if(parent==NULL||parent->rchild==NULL)
        {
            printf("\n删除出错!");
            return NULL;
        }
        p=parent->rchild;
        parent->rchild=NULL;
        free(p);
        return bt;
    }
    
    /*访问节点值*/
    void Vist(BiTree bt)
    {
        printf("%c\t",bt->data);
    }
    
    /*递归前序遍历*/
    void PreOrder(BiTree bt)
    {
        if(bt==NULL) return;
        Vist(bt);
        PreOrder(bt->lchild);
        PreOrder(bt->rchild);
    }
    
    /*递归中序遍历*/
    void InOrder(BiTree bt)
    {
        if(bt==NULL) return;
        InOrder(bt->lchild);
        Vist(bt);
        InOrder(bt->rchild);
    }
    
    /*递归后序遍历*/
    void PostOrder(BiTree bt)
    {
        if(bt==NULL) return;
        PostOrder(bt->lchild);
        PostOrder(bt->rchild);
        Vist(bt);
    }
    
    /*非递归前序遍历*/
    void NRPreOrder(BiTree bt)
    {
        BiTNode *stack[MAX],*p; 
        int top=-1;                     //栈初始化为空
        if(bt==NULL) return;
        p=bt;                           //p指向根结点
        while(! (p == NULL && top == -1))
        {
            while(p!=NULL)
            {
                Vist(p);
                top++;
                stack[top]=p;
                p=p->lchild;
            }
            if(top<0) return;
            else 
            {
                p=stack[top];
                top--;
                p=p->rchild;
            }
        }
    }
    
    /*非递归中序遍历*/
    void NRInOrder(BiTree bt)
    {
        BiTNode *stack[MAX],*p; 
        int top=-1;                     //栈初始化为空
        if(bt==NULL) return;
        p=bt;                           //p指向根结点
        while(! (p == NULL && top == -1))
        {
            while(p!=NULL)
            {   
                top++;
                stack[top]=p;
                p=p->lchild;
            }
            if(top<0) return;
            else 
            {   
                p=stack[top];
                Vist(p);
                top--;
                p=p->rchild;
            }
        }
    }
    
    /*非递归后序遍历*/
    void NRPostOrder(BiTree bt)
    {
        BiTNode *stack[MAX];
        int Frist[MAX];         //判断在栈中的次数,正则第一次,负则第二次
        BiTNode *p; 
        int top=-1;             //栈初始化为空
        if(bt==NULL) return;
        p=bt;                   //p指向根结点
        while(! (p == NULL && top == -1))
        {
            while(p != NULL)
            {   
                top++;
                stack[top]=p;
                Frist[top]=1;
                p=p->lchild;
            }
            if(top > -1)
            {
                if(Frist[top] > 0)
                {
                    p=stack[top]->rchild;
                    Frist[top]=-Frist[top];
                }
                else
                {
                    p=stack[top];
                    top--;
                    Vist(p);
                    p=NULL;
                }
            }
        }
    }
    
    /*层次遍历*/
    void LevelOrder(BiTree bt)
    {
        BiTNode *Queue[MAX];
        int front,rear;
        if(bt==NULL)return;
        front=-1;
        rear=0;
        Queue[rear]=bt;
        while(front!=rear)
        {
            front++;
            Vist(Queue[front]);                     //出队,并取值输出
    
            if(Queue[front]->lchild!=NULL)          //入队操作
            {
                rear++;
                Queue[rear]=Queue[front]->lchild;
    
            }
            if(Queue[front]->rchild!=NULL)
            {
                rear++;
                Queue[rear]=Queue[front]->rchild;
            }
        }
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
        BiTree t,tr=NULL,tl=NULL;
        t=Initiate();
        t=Create('A',tl,tr);
        printf("根节点:\n");
        PreOrder(t);
        t=InsertL(t,'B',t);
        t=InsertR(t,'C',t);
        t=InsertL(t,'D',t->lchild);
        t=InsertR(t,'G',t->lchild->lchild);
        t=InsertL(t,'E',t->rchild);
        t=InsertR(t,'F',t->rchild);
        printf("\n二叉树遍历情况如下:\n");
        printf("递归法前序遍历:  ");
        PreOrder(t);
        printf("\n");
        printf("非递归法前序遍历:");
        NRPreOrder(t);
        printf("\n");
        printf("\n");
        printf("递归法中序遍历:  ");
        InOrder(t);
        printf("\n");
        printf("非递归法中序遍历:");
        NRInOrder(t);
        printf("\n");
        printf("\n");
        printf("递归法后序遍历:  ");
        PostOrder(t);
        printf("\n");
        printf("非递归法中序遍历:");
        NRPostOrder(t);
        printf("\n");
        printf("\n");
        printf("层次遍历:        ");
        LevelOrder(t);
        printf("\n");
        //printf("\n删除后的为:\n");
        //t=DeleteL(t,t->lchild);
        //printf("前序遍历:");
        //PreOrder(t);
        return 0;
    }
    
    
    评论
    解决 无用
    打赏 举报
查看更多回答(3条)

相关推荐 更多相似问题