您的位置: 首页  >  文章  >  数据结构二叉树的递归非递归前中后序，层序遍历。

数据结构二叉树的递归非递归前中后序，层序遍历。

分类: 文章 • 2024-10-23 22:20:10

话不多说看代码。

 

数据结构二叉树的递归非递归前中后序，层序遍历。

 

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

#define TRUE 1
#define ERROR 0
#define OK 1
#define FALSE 0
#define OVERFLOW -2
#define STACK_SIZE 100
#define STACKINCREMENT 10

typedef struct BiTNode{

    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


typedef BiTree SElemType;

typedef struct{

    SElemType *head;
    SElemType *top;
    int stacksize;
}SqStack;



typedef BiTree QElemType;

typedef struct QNode{

    QElemType data;
    struct QNode *next;

}QNode,*QueuePrt;

typedef struct{

    QueuePrt front;
    QueuePrt rear;
}LinkQueue;

int InitStack(SqStack &S){                                      //创建一个栈

    S.head=(SElemType*)malloc(STACK_SIZE*sizeof(SElemType));
    if(!S.head)
        exit(OVERFLOW);
    S.head=S.top;
    S.stacksize=STACK_SIZE;

    return OK;
}
int Push(SqStack &S,SElemType &e){                                 //进栈

    if(S.top-S.head>=S.stacksize){
        S.head=(SElemType*)realloc(S.head,(STACK_SIZE+STACKINCREMENT)*sizeof(SElemType));
        if(S.head)
            exit(OVERFLOW);
        S.top=S.head+S.stacksize;
        S.stacksize+=STACKINCREMENT;
        }
        *S.top=e;
        S.top++;
    return OK;
}
int Pop(SqStack &S,SElemType &e){                                   //出栈

    if(S.head==S.top)
        return ERROR;
    S.top--;
    e=*S.top;

    return OK;
}
int StackEmpty(SqStack &S){                                         //判断是否栈空
    if(S.top-S.head==0)
        return OK;
    else
        return ERROR;
}
SElemType GetTop(SqStack S){                                        //获取栈顶元素
    if(S.top!=S.head)
        return *(S.top-1);
}

int InitQueue(LinkQueue &Q){                                        //构造一个队列

    Q.front=Q.rear=(QueuePrt)malloc(sizeof(QNode));
    if(!Q.front)
        exit(OVERFLOW);
    Q.front->next=NULL;

    return OK;
}

int QueueEmpty(LinkQueue Q){                                        //判断是否队空
    if(Q.front==Q.rear)
        return TRUE;
    else
        return FALSE;
}

int EnQueue(LinkQueue &Q,QElemType &e){                              //插入元素e为Q的新的队尾元素

    QueuePrt p;
    p=(QueuePrt)malloc(sizeof(QNode));
    if(!p)
        exit(OVERFLOW);
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;

    return OK;
}

int DeQueue(LinkQueue &Q,QElemType &e){                             //删除队头元素

    QueuePrt p=Q.front;
    if(Q.front==Q.rear){

        return ERROR;
    }
    p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)
        Q.rear=Q.front;
    free(p);
        return OK;
}
int CreateBiTree(BiTree &T){                                    //按照先序创建一颗树

    char e;
    e=getchar();
    if(e=='#')
        T=NULL;
    else{
        T=(BiTree)malloc(sizeof(BiTNode));
        if(!T)
            exit(OVERFLOW);
        T->data=e;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
        }
    return OK;
}

void PreOrderTree(BiTree T){                            //递归先序遍历二叉树

    if(T){
        printf("%c",T->data);
        PreOrderTree(T->lchild);
        PreOrderTree(T->rchild);

        }
}
void InOrderTree(BiTree T){                             //递归中序遍历二叉树

    if(T){
        InOrderTree(T->lchild);
        printf("%c",T->data);
        InOrderTree(T->rchild);

        }
}
void PostOrderTree(BiTree T){                           //递归后序遍历二叉树

    if(T){
        PostOrderTree(T->lchild);
        PostOrderTree(T->rchild);
        printf("%c",T->data);

        }
}
int BiTreeNode(BiTree T){                               //二叉树节点个数

    if(T!=NULL){

        return 1+BiTreeNode(T->lchild)+BiTreeNode(T->rchild);

    }
}
void PreOrderTraverse(BiTree T){                    //非递归先序遍历
    SqStack S;
    InitStack(S);
    BiTree p=T;
    while(p||!StackEmpty(S)){

        if(p){
                Push(S,p);
                printf("%c",p->data);
                p=p->lchild;

                }
        else{
            Pop(S,p);
            p=p->rchild;
        }
    }
}
void InOrderTraverse(BiTree T){                     //非递归中序遍历
    SqStack S;
    InitStack(S);
    BiTree p=T;
    while(p||!StackEmpty(S)){
        if(p){
            Push(S,p);
            p=p->lchild;
            }
        else{
            Pop(S,p);
            printf("%c",p->data);
            p=p->rchild;
        }
    }
}
void PostOrderTraverse(BiTree T){
    SqStack S;
    InitStack(S);
    BiTree p=T,q=NULL;
    if(T==NULL){
        return;
    }
    Push(S,p);
    while(!StackEmpty(S)){
        p=GetTop(S);
        if((p->lchild==NULL&&p->rchild==NULL)||(q!=NULL&&(q==p->lchild)||(q==p->rchild))){
                /*左右子树都为空或者都已遍历*/
            printf("%c",p->data);
            q=p;
            Pop(S,p);
        }
        else{
            if(p->rchild!=NULL){
                Push(S,p->rchild);
            }
            if(p->lchild!=NULL){
                Push(S,p->lchild);
            }
        }
    }
}
void SeqTraverse(BiTree T){                 //层序遍历
    LinkQueue Q;
    InitQueue(Q);
    BiTree p=T;
    EnQueue(Q,T);
    while(!QueueEmpty(Q)){
        p=NULL;
        DeQueue(Q,p);

        if(p->lchild!=NULL){
            EnQueue(Q,p->lchild);
        }
        if(p->rchild!=NULL){
            EnQueue(Q,p->rchild);
        }
        printf("%c",p->data);
    }
}
int main(){
    BiTree T;
    int i;
    printf("请按先序输入树：\n");
    CreateBiTree(T);
    printf("\n1、递归遍历\n");
    printf("2、非递归遍历\n");
    printf("3、层序遍历\n");
    while(1){
        printf("\n请输入你要进行的操作：");
        scanf("%d",&i);
        switch(i){


            case 1:
                    printf("\n递归先序输出：");
                    PreOrderTree(T);
                    printf("\n递归中序输出：");
                    InOrderTree(T);
                    printf("\n递归后序输出：");
                    PostOrderTree(T);
                    printf("\n节点个数：%d",BiTreeNode(T));
                    break;
            case 2:
                    printf("\n非递归先序遍历：");
                    PreOrderTraverse(T);
                    printf("\n非递归中序遍历：");
                    InOrderTraverse(T);
                    printf("\n非递归后序遍历：");
                    PostOrderTraverse(T);
                    break;
            case 3:

                    printf("\n层序遍历：");
                    SeqTraverse(T);
                    break;
            }
    }





    return 0;
}

 

相关推荐