c_数据结构_二叉树的遍历实现_C

概述#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -2#define True 1// 定义二叉树的节点类型typedef struct BiTNode{ char data; struct BiTNode *lchild; // 定义节点

#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -2#define True 1// 定义二叉树的节点类型typedef struct BiTNode{     char data;    struct BiTNode *lchild;  // 定义节点的左孩子指针，有孩子指针    struct BiTNode *rchild;}BiTNode,*BiTree;//先序遍历构造二叉链表表示对二叉树Tint CreateBiTree(BiTree &T){    char ch;    scanf("%c",&ch);    fflush(stdin);          // 对键盘缓冲区的处理            if(ch==‘#‘){         //如果输入#，创建空节点        T=NulL;    }else{        if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))){           //申请根节点的空间              printf("申请节点空间失败！！");            exit(OVERFLOW);                               }else{            T->data=ch;                //生成根节点                    CreateBiTree(T->lchild);               //构建左子树                        CreateBiTree(T->rchild);             //构建右子树                }        return OK;    }    return ERROR;        }//先序遍历二叉树int DLR(BiTree T){        if(T!=NulL)              // 如果树不为空    {        printf("%c\n",T->data);        DLR(T->lchild);          // 递归遍历        DLR(T->rchild);    }else{        return ERROR;        //树为空    }    return OK;       // 遍历成功}//中序遍历二叉树int LDR(BiTree T){        if(T!=NulL)    {        LDR(T->lchild);            // 递归遍历        printf("%c\n",T->data);        LDR(T->rchild);    }else{        return ERROR;       //树为空    }    return OK;       // 遍历成功}//后序遍历二叉树int LRD(BiTree T){     if(T!=NulL)    {        LRD(T->lchild);     // 递归遍历        LRD(T->rchild);        printf("%c\n",T->data);    }else{        return ERROR;       //树为空    }    return OK;       // 遍历成功}// 树的叶子数voID yezi(BiTree T){    if(T!=NulL){            if(!T->lchild&&!T->rchild){                            printf("%c\n",T->data);    // 打印叶子节点        }        yezi(T->lchild);        yezi(T->rchild);        }}// 树的深度int shendu(BiTree T){    int h=0,h1,h2;    if(T==NulL)        return h;    else{        h1=shendu(T->lchild);        h2=shendu(T->rchild);        if(h1>=h2)       // 最后加的数为树的最深            h=h1+1;        else            h=h2+1;    }    return h;}voID OperateMenu(){    printf("\n--------------请选择元素处理方式---------\n\n");    printf("\n注：请输入数字\n");    printf("0>:退出 *** 作\n");    printf("1>:先序遍历二叉树\n");    printf("2>:中序遍历二叉树\n");    printf("3>:后序遍历二叉树\n");    printf("4>:树的叶子节点\n");    printf("5>:树的深度\n");    printf("请选择对元素的处理：");}voID zushi(){    printf("注：此过程为二叉树的建立及其对其的相关 *** 作\n\t以下为树的大致模型\t\n");    printf("              1                \n");    printf("            /   \              \n");    printf("           2     3             \n");    printf("          / \   / \            \n");        printf("         #   # #   #           \n");    printf("\n 注！！！楼上输入 # 表示无孩子为空\n故输入序列为12##3###\n");    printf("实际形成序列形成的树为为：\n");    printf("              1                \n");    printf("            /   \              \n");    printf("           2     3             \n");}int main(){    int w=0,k,n,boo=1;    BiTree T;    printf("请用户选择创建二叉树或退出程序：\n\n");    printf("创建二叉树请输入：‘1‘\n\n");    printf("退出请选择‘0‘或 其它！！\n\n");    printf("请选择：");    scanf("%d",&w);    if(w==1){        zushi();        printf("\n请输入树节点元素（请回车输入下一个数）：\n");        fflush(stdin);           boo=CreateBiTree(T);        if(!boo){            //printf("\n构建成功！！\n");            while(!boo){                printf("\n构建树为空树，请重新构建：");                        printf("\n请输入树节点元素（请回车输入下一个数）：\n");                            boo=CreateBiTree(T);            }        }else{            printf("\n构建成功！！\n");        }        OperateMenu();        scanf("%d",&k);        while(k){            switch(k){            case 0:break;            case 1:                printf("先序遍历结果为：\n");                boo=DLR(T);                if(boo)                    printf("\n先序遍历成功！！\n");                else                    printf("\n先序遍历失败！！\n");                break;            case 2:                printf("中序遍历结果为：\n");                boo=LDR(T);                if(boo)                    printf("\n中序遍历成功！！\n");                else                    printf("\n中序遍历失败！！\n");                break;            case 3:                printf("后序遍历结果为：\n");                boo=LRD(T);                if(boo)                    printf("\n后序遍历成功！！\n");                else                    printf("\n后序遍历失败！！\n");                break;            case 4:                printf("其中是叶子节点的是：\n");                yezi(T);                break;            case 5:n=shendu(T);                printf("树的深度为：%d",n);                break;                        }        OperateMenu();        scanf("%d",&k);        }        }    return OK;}