Question

PTA 4-2 二叉树的基本操作 (10分)

T是一个二叉树，函数CreateBiTree(BiTree &T)是创建一颗二叉树（使用数据结构书上的方式），函数PreOrder(BiTree &T)是输出树的先序遍历，函数InOrder(BiTree &T)是输出树的中序遍历，函数PostOrder(BiTree &T)是输出树的后序遍历，函数LevelOrder(BiTree &T)是输出树的层序遍历。数据保证合法。
函数接口定义：

void CreateBiTree(BiTree &T);
void PreOrder(BiTree &T);
void InOrder(BiTree &T);
void PostOrder(BiTree &T);
void LevelOrder(BiTree &T);
其中 T 是二叉树。
裁判测试程序样例：

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

#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;
typedef char TElemType;

typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode, *BiTree;

/////////////////////////////////
typedef BiTNode * QElemType;

typedef struct QNode {
QElemType data;
struct QNode * next;
}QNode, *QueuePtr;

typedef struct {
QueuePtr front;
QueuePtr rear;
}LinkQueue;

Status InitQueue_L(LinkQueue &Q) {
Q.front = (QueuePtr) malloc (sizeof(QNode));
if (Q.front == NULL)
return OVERFLOW;
Q.front->next = NULL;
Q.rear = Q.front;
return OK;
}

bool QueueEmpty_L(LinkQueue &Q) {
return (Q.front == Q.rear);
}

int QueueLength_L(LinkQueue &Q) {
int count = 0;
for (QNode *p = Q.front->next; p != NULL; p = p->next)
count++;
return count;
}

Status EnQueue_L(LinkQueue &Q, QElemType e) {
QNode *s = (QNode *) malloc (sizeof(QNode));
s->data = e;
s->next = NULL;
Q.rear->next = s;
Q.rear = s;
return OK;
}

Status DeQueue_L(LinkQueue &Q) {
QNode *q = Q.front->next;
Q.front->next = q->next;
if (q->next == NULL)
Q.rear = Q.front;
free(q);
return OK;
}

void PrintQueue_L(LinkQueue &Q) {
for (QNode *p = Q.front->next; p != NULL; p = p->next)
printf("%c", p->data->data);
printf("\n");
}
/////////////////////////////////

void CreateBiTree(BiTree &T);
void PreOrder(BiTree &T);
void InOrder(BiTree &T);
void PostOrder(BiTree &T);
void LevelOrder(BiTree &T);

int main() {
BiTree T;

CreateBiTree(T);

printf("PreOrder:");
PreOrder(T);
printf("\n");

printf("InOrder:");
InOrder(T);
printf("\n");

printf("PostOrder:");
PostOrder(T);
printf("\n");

printf("LevelOrder:");
LevelOrder(T);
printf("\n");

return 0;
}
/* 你的代码将被嵌在这里 */
输入格式：

按照数据结构树上的建图方式，给出建树的字符串
输出格式：

依次输出树的先序遍历，中序遍历，后序遍历和层序遍历
输入样例：

ab#c##d##
输出样例：

PreOrder:abcd
InOrder:bcad
PostOrder:cbda
LevelOrder:abdc
编译器：gcc
时间限制：400ms
内存限制：64MB
代码长度限制：16kB
判题程序：系统默认
作者：wgy
单位：浙江大学

题目判定
解题程序

仅求却的那部分代码，只要c语言的，不要c++！！！
PTA能判过

Answer 1

//输入样例：
//ab#c##d##
//输出样例：
//PreOrder:abcd
//InOrder:bcad
//PostOrder:cbda
//LevelOrder:abdc

//       a
//     /    \
//    b      d
//   / \    / \
//  #   c  #   #
//     / \
//    #   #

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

#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;
typedef char TElemType;

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode, *BiTree;

/////////////////////////////////
typedef BiTNode * QElemType;

typedef struct QNode
{
    QElemType data;
    struct QNode * next;
}QNode, *QueuePtr;

typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

Status InitQueue_L(LinkQueue &Q)
{
    Q.front = (QueuePtr) malloc (sizeof(QNode));
    if (Q.front == NULL)
        return OVERFLOW;
    Q.front->next = NULL;
    Q.rear = Q.front;
    return OK;
}

bool QueueEmpty_L(LinkQueue &Q)
{
    return (Q.front == Q.rear);
}

int QueueLength_L(LinkQueue &Q)
{
    int count = 0;
    for (QNode *p = Q.front->next; p != NULL; p = p->next)
        count++;
    return count;
}

Status EnQueue_L(LinkQueue &Q, QElemType e)
{
    QNode *s = (QNode *) malloc (sizeof(QNode));
    s->data = e;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
    return OK;
}

Status DeQueue_L(LinkQueue &Q)
{
    QNode *q = Q.front->next;
    Q.front->next = q->next;
    if (q->next == NULL)
        Q.rear = Q.front;
    free(q);
    return OK;
}

void PrintQueue_L(LinkQueue &Q)
{
    for(QNode *p = Q.front->next; p != NULL; p = p->next)
        printf("%c", p->data->data);
    printf("\n");
}
/////////////////////////////////

void CreateBiTree(BiTree &T);
void PreOrder(BiTree &T);
void InOrder(BiTree &T);
void PostOrder(BiTree &T);
void LevelOrder(BiTree &T);

int main()
{
    BiTree T;

    CreateBiTree(T);

    printf("PreOrder:");
    PreOrder(T);
    printf("\n");

    printf("InOrder:");
    InOrder(T);
    printf("\n");

    printf("PostOrder:");
    PostOrder(T);
    printf("\n");

    printf("LevelOrder:");
    LevelOrder(T);
    printf("\n");

    return 0;
}
//创建二叉树: 先序扩展序列 + 递归法
void CreateBiTree(BiTree &T)
{
    char input;
    scanf("%c",&input); //输入数据
    if(input == '#')    //'#'是空节点
    {
       T = NULL;
    }
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        if(T == NULL)
        {
            printf("\n分配动态内存时出错.\n");
            exit(1);
        }
        T->data=input;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

void PreOrder(BiTree &T) //先序遍历
{
    if(T != NULL)
    {
        printf("%c",T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

void InOrder(BiTree &T) //中序遍历
{
    if(T != NULL)
    {
        InOrder(T->lchild);
        printf("%c",T->data);
        InOrder(T->rchild);
    }
}

void PostOrder(BiTree &T) //后序遍历
{
    if(T != NULL)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%c",T->data);
    }
}

void LevelOrder(BiTree &T) //层序遍历
{
    LinkQueue Q;
    BiTree p = T;
    if(p == NULL)
    {
        return;
    }
    InitQueue_L(Q);
    EnQueue_L(Q, p);
    while( !QueueEmpty_L(Q) )
    {
        p = Q.front->next->data;
        DeQueue_L(Q);
        printf("%c",p->data);
        if(p->lchild != NULL)
        {
            EnQueue_L(Q, p->lchild);
        }
        if(p->rchild != NULL)
        {
            EnQueue_L(Q, p->rchild);
        }
    }
}

追问