树的遍历(指针方式孩子表示法)

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

#define MAX_SIZE 100
typedef char dadaType;

// 6.4.1 树的遍历(指针方式孩子表示法)
#define m 3 //树的度
typedef struct node
{
    dadaType data;
    struct node *child[m]; // 指向孩子的指针数组
}node, *tree;

typedef struct queue // 用于层序遍历的队列
{
    node data[MAX_SIZE];
    int front, rear; // 对头指针和队尾指针
}queue;

// 1. 初始化循环队列
void init(queue *q)
{
    q->front = q->rear = 0;
}

// 2. 判断队列是否为空
int empty(queue q)
{
    return q.rear == q.front;
}

// 3. 入队
void insert(queue *q, node x)
{
    if((q->rear + 1)%MAX_SIZE == q->front)
    {
        printf("队列已满，无法入队！\n");
        exit(1);
    }
    q->data[q->rear] = x;
    q->rear = (q->rear + 1)%MAX_SIZE;
}

// 4. 队列出队
node del(queue *q)
{
    int front = q->front;
    if(q->rear == front)
    {
        printf("队列为空，无法出队！\n");
        exit(1);
    }
    q->front = (front + 1)%MAX_SIZE;
    return q->data[front];
}

// 5. 树的前序遍历
void preOrder(tree p)
{
    if(p)
    {
        printf("%c ",p->data);
        for (int i = 0; i < m; i++)
            preOrder(p->child[i]);
    }
}

// 6. 树的后序遍历
void postOrder(tree p)
{
    if(p)
    {
        for (int i = 0; i < m; i++)
            postOrder(p->child[i]);
        printf("%c ",p->data);
    }
}

// 7. 树的层序遍历
void leverOrder(tree t)
{
    queue q;
    init(&q);
    if(t) // 树非空时
        insert(&q,*t); // 队列初始为根结点
    while (!empty(q)) // 当队列非空
    {
        node n = del(&q); // 出队并访问
        printf("%c ",n.data);
        for (int i = 0; i < m; ++i)
        {
            if(n.child[i])
                insert(&q,*n.child[i]); // 每个结点的非空孩子入队
        }
    }
}

// 8.按前序遍历顺序建立一棵度为3的树
tree creatTree()
{
    char c;
    tree t;
    if((c = getchar()) == '#')
        t = NULL;
    else
    {
        t = (tree) malloc(sizeof(node));
        t->data = c;
        for (int i = 0; i < m; ++i)
            t->child[i] = creatTree();
    }
    return t;
}

int main()
{
    tree root; // 声明一棵度为3的树
    // AB###CE###FH###I####G###D###(样例)
    printf("创建一颗度为3的树，请输入结点，#表示空结点:\n");
    root = creatTree();
    printf("前序遍历为：\n");
    preOrder(root);
    printf("\n后序遍历为：\n");
    postOrder(root);
    printf("\n层序遍历为：\n");
    leverOrder(root);
    return 0;
}