二叉树的创建及其遍历（递归+非递归） - 数据结构与算法

得分:0

只有非递归的有错误，其他的都对

#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "conio.h"
#define _CRT_SECURE_NO_WARNINGS
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAX 50
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAXSIZE 100
typedef int Status;
typedef int Stack;
typedef int Queue;
typedef char ElemType;
typedef struct BTNode
{
    ElemType data;
    struct BTNode *lchild,*rchild;
}BTNode,*BTree;
typedef struct
{
    BTree *base;
    BTree *top;
    int stacksize;
}SeqStack;
typedef struct
{
    ElemType elem[MAXSIZE];
    int front;
    int rear;
}SeqQueue;

Status InitStack(Stack *S);
Status Push(Stack *S, BTree p);
Status Pop(Stack *S, BTree *p);
Status GetTop(Stack *S, BTree *p);
Status StackEmpty(Stack *S);

/*Status InitQueue(Queue *Q);
Status EnQueue(Queue *Q, BTree p);
Status DeQueue(Queue *Q, BTree *p);
Status GetFront(Queue Q,BTree *p);
Status QueueEmpty(Queue *Q);*/

Status CreatBTree(BTree *T);
Status PreOrderTraverse_Recursive(BTree T, Status(*Visit)(ElemType e));
Status InOrderTraverse_Recursive(BTree T, Status(*Visit)(ElemType e));
Status PostOrderTraverse_Recursive(BTree T, Status(*Visit)(ElemType e));
/*Status PreOrderTraverse_Non_Recursive(BTree T, Status(*Visit)(ElemType e));
Status InOrderTraverse_Non_Recursive(BTree T, Status(*Visit)(ElemType e));
Status InOrderTraverse_Non_Recursive_2(BTree T, Status(*Visit)(ElemType e));
Status PostOrderTraverse_Non_Recursive(BTree T, Status(*Visit)(ElemType e));
Status LevelOrderTraverse(BTree T,Status(*Visit)(ElemType e));*/
Status PrintElement(ElemType e);

Status CreatBTree(BTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
    {
        (*T)=NULL;
    }
    else {
        if(!((*T)=(BTree)malloc(sizeof(BTNode))))
        exit(OVERFLOW);
        (*T)->data=ch;
        CreatBTree(&((*T)->lchild));
        CreatBTree(&((*T)->rchild));
        return OK;
    }
}
Status PreOrderTraverse_Recursive(BTree T,Status(*Visit)(ElemType e))
{
    if(T)
    {
        if(Visit(T->data))
        if(PreOrderTraverse_Recursive(T->lchild,Visit))
        if(PreOrderTraverse_Recursive(T->rchild,Visit))
        return OK;
        return ERROR;
    }
        else
        {
            return OK;
        }
}
/*Status PreOrderTraverse_Non_Recursive(BTree T,Status(*Visit)(ElemType e))
{
    Stack *S;                                  //栈S中存储指向树结点的指针。
    BTree p;
    S=(Stack*)malloc(sizeof(Stack));
    InitStack(S);
    Push(S,T);                                   //根指针进栈。
    while(!StackEmpty(S))
    {
    //获取栈顶指针，如果栈顶指针不为空，访问该结点。并将该结点的左子树进栈。
        if(GetTop(S,&p)&&p)
        {
            if(Visit(p->data))
            return ERROR;
            Push(S,p->lchild);
        }
        //栈顶指针为空，表明之前压入的左子树或者右子树为空。
        else
        {
            Pop(S,&p);                                   //空指针退栈
            if(!StackEmpty(S))
            {
            Pop(S,&p);                              //已被访问过的根结点退栈。此时，该退栈结点的左子树已被全部访问过。
            Push(S,p->rchild);                       //右子树进栈。
            }
         }
    }
    return OK;
}*/
Status InOrderTraverse_Recursive(BTree T,Status(*Visit)(ElemType e))
{
    if(T)
    {
        if(InOrderTraverse_Recursive(T->lchild,Visit))
        if(Visit(T->data))
        if(InOrderTraverse_Recursive(T->rchild,Visit))
        return OK;
        return ERROR;
    }
        else
        {
            return OK;
        }

}
/*Status InOrderTraverse_Non_Recursive(BTree T,Status(*Visit)(ElemType e))
{
    Stack *S;
    BTree p;
    S=(Stack*)malloc(sizeof(Stack));
    InitStack(S);
    Push(S,T);
    while(!StackEmpty(S))
    {
        while(GetTop(S,&p)&&p)
        {
            Push(S,p->lchild);
        }

            Pop(S,&p);
            if(!StackEmpty(S))
            {
                Pop(S,&p);
                if(Visit(p->data))
                return ERROR;
                Push(S,p->rchild);
            }

    }
    return OK;
}*/
/*Status InOrderTraverse_Non_Recursive_2(BTree T,Status(*Visit)(ElemType e))
{
    Stack *S;
    BTree p=T;
    S=(Stack*)malloc(sizeof(Stack));
    InitStack(S);
    while(p||!StackEmpty(S))
    {
        if(p)
        {
            Push(S,p);
            p=p->lchild;
        }
        else
        {
            Pop(S,&p);
            if(Visit(p->data))
            return ERROR;
            p=p->rchild;
        }
    }
    return OK;
}*/
Status PostOrderTraverse_Recursive(BTree T,Status(*Visit)(ElemType e))
{
    if(T)
    {

        if(PostOrderTraverse_Recursive(T->lchild,Visit))
        if(PostOrderTraverse_Recursive(T->rchild,Visit))
        if(Visit(T->data))
        return OK;
        return ERROR;
    }
        else
        {
            return OK;
        }

}
/*Status PostOrderTraverse_Non_Recursive(BTree T,Status(*Visit)(ElemType e))
{
    Stack *S;
    BTree p,pre=NULL;
    S=(Stack*)malloc(sizeof(Stack));
    InitStack(S);
    Push(S,T);
    while(!StackEmpty(S))
    {
        if(GetTop(S,&p)&&p->lchild&&pre!=p->lchild&&!(p->rchild&&pre==p->rchild))
        {
            Push(S,p->lchild);
        }
        else
        {
            if(p->rchild&&pre!=p->rchild)
            Push(S,p->rchild);
            else
            {
               Pop(S,&p);
               if(!StackEmpty(S))
               {

                if(Visit(p->data))
                return ERROR;
                pre=p;
               }
           }
       }
   }
   return OK;
}*/
/*Status LevelOrderTraverse(BTree T,Status(*Visit)(ElemType e))
{
    Queue Q;
    BTree p=T;
    int front,rear;
    InitQueue(&Q);
    if(T)
    EnQueue(&Q,T);
    while(front<rear)
    {
        DeQueue(&Q,&p);
        Visit(p->data);
        if(p->lchild)
        EnQueue(&Q,p->lchild);
        if(p->rchild)
        EnQueue(&Q,p->rchild);
    }
    return OK;
    return ERROR;
}*/
Status PrintElement(ElemType e)
{
    putchar(e);
    return OK;
}
/*Status InitQueue(SeqQueue *Q)
{
    Q->front=Q->rear=0;
}
Status QueueEmpty(SeqQueue *Q)
{
    if(Q->front==Q->rear)
    return OK;
    return ERROR;
}
Status GetFront(SeqQueue Q,ElemType *n)
{
    if(Q.front==Q.rear)
    return ERROR;
    *n=Q.elem[Q.front];
    return OK;
}
Status EnQueue(SeqQueue *Q,ElemType n)
{
    if((Q->rear+1)%MAXSIZE==Q->front)
    return ERROR;
    Q->elem[Q->rear]=n;
    Q->rear=(Q->rear+1)%MAXSIZE;
    return OK;
}
Status DeQueue(SeqQueue *Q,ElemType *n)
{
    if(Q->front==Q->rear)
    return ERROR;
    *n=Q->elem[Q->front];
    Q->front=(Q->front+1)%MAXSIZE;
    return OK;
}*/
Status InitStack(SeqStack *s)
{
    s->base=(BTree*)malloc(sizeof(BTree)*STACK_INIT_SIZE);
    s->top=s->base;
    s->stacksize=STACK_INIT_SIZE;
    return OK;
}
Status StackEmpty(SeqStack *s)
{
    if(s->top==s->base)
    return OK;
    return ERROR;
}
Status GetTop(SeqStack *s,BTree *c)
{
    if(StackEmpty(s))
    return ERROR;
    *c=*(s->top-1);
    return OK;
}
Status Push(SeqStack *s,BTree c)
{
    if(s->top-s->base>=s->stacksize)
    {
        s->base=(BTree*)realloc(s->base,sizeof(BTree)*(s->stacksize+STACKINCREMENT));
        s->stacksize=s->stacksize+STACKINCREMENT;
    }
    *(s->top++)=c;
    return OK;
}
Status Pop(SeqStack *s,BTree *c)
{
    if(StackEmpty(s))
    return ERROR;
    *c=*(--s->top);
    return OK;
}
int Depth(BTree p)
{
    int hl,hr;
    if(p==NULL)
    return 0;
    else
    {
        hl=Depth(p->lchild);
        hr=Depth(p->rchild);
        if(hl>hr)
        return(hl+1);
        else  return(hr+1);
    }
}
int TestComTree(BTree T)
{
    BTree Queue[MAX],p;
    int front,rear,flag=1,comflag=1;
    if(T)
    {
        Queue[0]=T;
        front=-1;
        rear=0;
        while(front<rear)
        {
            p=Queue[++front];
            if(p->lchild==NULL)
            {
                if(p->rchild!=NULL)
                {
                    comflag=0;
                    break;
                }
                flag=0;
            }
            else
            {
                if(flag==0)
                {
                    comflag=0;
                    break;
                }
                Queue[++rear]=p->lchild;
                if(p->rchild!=NULL)
                Queue[++rear]=p->rchild;
                else
                flag=0;
            }
        }
    }
    return comflag;
}
/*Status PreOrderTraverse(BTree T)
{
    if(T!=NULL)
    {
        if(T->lchild==NULL&&T->rchild==NULL)
        printf("%c ",T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}*/
Status CountLeaf(BTree p)
{
    int count=0;
    if(p==NULL)
    {
        return ERROR;
    }
    else
    if(p!=NULL)
    {
        if(p->lchild==NULL&&p->rchild==NULL)
        {
               count++;
        count+=CountLeaf(p->lchild);
        count+=CountLeaf(p->rchild);
        return count;
        }

        return (CountLeaf(p->lchild)+CountLeaf(p->rchild));
    }
    else return ERROR;
}
/*Status printTree(BTree p)
{
    Stack *s;
    s=(Stack*)malloc(sizeof(Stack));
    s->top=0;
    while(p!=NULL&&s->top!=0)
    {
        if(p!=NULL)
        {
        printf("p->data");
        s->MAXSIZE[s->top]=p->data;
        s->top++;
        p=p->lchild;
       }

    else
    {
        p=s->MAXSIZE[s->top];
        s->top--;
        if(p->lchild==NULL&&p->rchild==NULL)
        {
            count++;
        }
        p=p->rchild;
    }
    }
}*/
int main()
{
    int height;
    int comflag;
    int count;
    BTree T;
    printf("请输入二叉树中所有的结点:\n");
    CreatBTree(&T);
    printf("\n");
    printf("递归先序为:\n");
    PreOrderTraverse_Recursive(T,PrintElement);
    printf("\n");
    printf("\n");
    /*printf("非递归先序为:\n");
    PreOrderTraverse_Non_Recursive(T,PrintElement);
    printf("\n");
    printf("\n");*/
    printf("递归中序为：\n");
    InOrderTraverse_Recursive(T,PrintElement);
    printf("\n");
    printf("\n");
    /*printf("非递归中序为:\n");
    InOrderTraverse_Non_Recursive(T,PrintElement);
    printf("\n");
    printf("\n");
    printf("非递归中序(2)为:\n");
    InOrderTraverse_Non_Recursive_2(T,PrintElement);
    printf("\n");
    printf("\n");*/
    printf("递归后序为:\n");
    PostOrderTraverse_Recursive(T,PrintElement);
    printf("\n");
    printf("\n");
    /*printf("非递归后序为:\n");
    PostOrderTraverse_Non_Recursive(T,PrintElement);
    printf("\n");
    printf("\n");*/
    /*printf("层序遍历：\n");
    LevelOrderTraverse(T,PrintElement);
    printf("\n");
    printf("\n");*/
    height=Depth(T);
    printf("该二叉树的高度为:%d\n",height);
    printf("\n");
    comflag=TestComTree(T);
    if(comflag=1)
    {
    printf("★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
    printf("★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
    printf("★★★★★★---!!!这是一颗完全二叉树!!!---★★★★★★★★\n");
    printf("★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
    printf("★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
    }
    else
    {
    printf("★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
    printf("★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
    printf("★★★★★★---!!!这不是一颗完全二叉树!!!---★★★★★★★\n");
    printf("★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
    printf("★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
    }
    printf("\n");
    printf("\n");
    count=CountLeaf(T);
    printf("◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆该二叉树中的叶子结点的个数为:%d\n",count);
    return 0;
}

我的类不是你的泪