c语言描述的二叉树的基本操作(层序遍历,递归,非递归遍历)

时间:2021-05-29 11:23:02
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int Status;
typedef char ElemType;
typedef struct BTNode{//定义树节点结构体
    ElemType data;
    struct BTNode *l;
    struct BTNode *r;
}BTNode,*BinTree;
typedef BinTree SElemType;
typedef struct{//非递归遍历要使用的栈操作定义
    SElemType *base;
    SElemType *top;
    int stacksize;//当前的栈空间容量
}SqStack;
//定义二叉树的基本操作
BinTree CreateBinTree(BinTree T);//创建二叉树并且返回一个指针
Status Visit(ElemType e);
Status Depth(BinTree T);
Status PreOrderRecursionTraverse(BinTree T,Status(*Visit)(ElemType e));
Status LevelOrderRecursionTraverse(BinTree T,Status(*Visit)(ElemType e));
//定义栈的基本操作
Status InitStack(SqStack *S);
Status Destroy(SqStack *S);
Status StackEmpty(SqStack S);
Status GetTop(SqStack *s,SElemType *e);
Status Pop(SqStack *S,SElemType *e);
Status Push(SqStack *S,SElemType e);
Status StackTraverse(const SqStack *S);//常量?

Status PreOrderNoneRecursionTraverse(BinTree T,Status(*Visit)(ElemType e));//非递归先序遍历

int main(){
    //int depth;
    BinTree Tree=NULL;
    Status(*Visit)(ElemType e)=Visit;//使用函数指针,用指针调用函数
    printf("请按先序遍历输入二叉树元素(空节点为=):\n");
    Tree=CreateBinTree(Tree);
    printf("\n先序遍历:\n");
    PreOrderRecursionTraverse(Tree,Visit);
    printf("\n层序遍历:\n");
    LevelOrderRecursionTraverse(Tree,Visit);
}
BinTree CreateBinTree(BinTree T){
    char ch;
    scanf("%c",&ch);
    if(ch=='='){
        T=NULL;
    }else{
        if(!(T=(BTNode *)malloc(sizeof(BTNode)))){
            exit(OVERFLOW);
        }
        T->data=ch;
        T->l=CreateBinTree(T->l);
        T->r=CreateBinTree(T->r);
    }
    return T;//返回的T为最后一个结点
}
Status Visit(ElemType e){
    if(e=='\0'){
        return ERROR;
    }else{
        printf("%c",e);
    }
    return OK;
}
Status PreOrderRecursionTraverse(BinTree T,Status(*Visit)(ElemType e))
{
    if(T){//判空
        if(!Visit(T->data)){//访问不成功,visit返回的是error
            return ERROR;
        }
        PreOrderRecursionTraverse(T->l,Visit);
        PreOrderRecursionTraverse(T->r,Visit);
    }
    return OK;
}
//层遍历
Status LevelOrderRecursionTraverse(BinTree T,Status(*Visit)(ElemType e))
{
    if(T){
        int front=-1;//每一次循环中表示从左到右的父节点的增加
        int rear=-1;//每一次循环当中用来表示front下一层该父节点左右子节点的变化增加
        BTNode *Q[100];//用来存储呢每一层从左到右的每一个树节点
        Q[++rear]=T;
        printf("根节点的数据:%d ",T->data);
        while(front!=rear){
            BTNode *p;
            if(!(p=(BTNode *)malloc(sizeof(BTNode)))){
                exit(OVERFLOW);
            }
            p=Q[++front];
            if(p->l){                
                Q[++rear]=p->l;
                printf("节点%d 的数据:%d",rear,p->l->data);
            }
            if(p->r){
                Q[++rear]=p->r;
                printf("节点%d 的数据:%d",rear,p->r->data);
            }
        }
        
    }
    
}
/*
Status Depth(BinTree T){
    int a,b;
    if(!T){
        return ERROR;
    }else{
        a=Depth(T->l)+1;
        b=Depth(T->r)+1;
        return a>b?a:b;
    }
}
Status PreOrderNoneRecursionTraverse(BinTree T,Status(*Visit)(ElemType e)){
        SqStack S;
        SElemType p;
        InitStack(&S);
        Push(&S,T);//将T入栈作为第一个操作结点
        while(S.base!=S.top){//栈不为空就一直循环,从上到下从左到右的取出
            Pop(&S,&p);
            if(!Visit(p->data)){//判断是否访问成功
                return ERROR;
            }
            if(p->l){
                Push(&S,p->r);//右结点先入栈为了后出栈
            }
            if(p->r){
                Push(&S,p->l);
            }
        }
        DestroyStack(&S);//释放栈
        return OK;
}*/