C++ 二叉树的层次建树及其遍历

#include <iostream>

#define MaxSize 10 // 栈中元素的最大个数

using namespace std;

typedef char ElemType;

// 树
struct BiTNode {
    ElemType data;            // 数据域
    BiTNode *lchild, *rchild; // 左孩子，右孩子
};

// 辅助队列结点，不带头结点，通过头指针 phead 访问
struct LinkNode {
    BiTNode *p; // 树中对应结点的地址
    LinkNode *pNext;
};

// 链式队列，辅助层次遍历
struct LinkQueue {
    LinkNode *front, *rear; // 队头指针，队尾指针
};

typedef BiTNode *BiTree; // 代指二叉树

// 树的初始化
bool InitTree(BiTree &T) {
    T = NULL;
    return true;
}

//层次建树
void BuildBinaryTree(BiTree &T, LinkNode *&phead, LinkNode *&ptail,
                     ElemType val) {
    // 此处申请空间，不能使用new，会进入死循环，我也不知道为啥
    BiTNode *pTreeNew =
        (BiTNode *)calloc(1, sizeof(BiTNode)); // 为树结点申请空间
    LinkNode *pQueueNew =
        (LinkNode *)calloc(1, sizeof(LinkNode)); // 为队列结点申请空间
    LinkNode *pCur = phead; // 始终指向当前操作位置

    pTreeNew->data = val;    // 树结点的赋值
    pQueueNew->p = pTreeNew; // 队列新结点的数据域为树的新结点

    if (T == NULL) { // 空树时，新结点置为树根
        T = pTreeNew;
        phead = pQueueNew;
        ptail = pQueueNew;
    } else {
        ptail->pNext = pQueueNew; //尾插法
        ptail = pQueueNew;        // 更新尾指针

        if (pCur->p->lchild == NULL) { // 左孩子为空
            pCur->p->lchild = pTreeNew;
        } else if (pCur->p->rchild == NULL) { // 右孩子为空
            pCur->p->rchild = pTreeNew;
            phead = pCur->pNext; //该结点左右孩子已满，队头指针后移
            free(pCur);          // 该代码中，PCur
                        // 是每次建树时重新定义的，所以在建树最后，要释放并置为
                        // NULL
            pCur = NULL;
        }
    }
}

//前序遍历（深度优先遍历）：根左右
void PreOrder(BiTNode *p) {
    if (p != NULL) {
        putchar(p->data);
        PreOrder(p->lchild);
        PreOrder(p->rchild);
    }
}

// 中序遍历：左根右
void InOrder(BiTNode *p) {
    if (p != NULL) {
        InOrder(p->lchild);
        putchar(p->data);
        InOrder(p->rchild);
    }
}

// 后序遍历：左右根
void PostOrder(BiTNode *p) {
    if (p != NULL) {
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        putchar(p->data);
    }
}

// 初始化队列
bool InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = new LinkNode; // 为队列申请一个结点作为头结点
    Q.front->pNext = NULL;
    return true;
}

// 队列判空
bool QueueEmpty(LinkQueue &Q) {
    if (Q.front == Q.rear) {
        return true;
    } else {
        return false;
    }
}

// 入队
bool EnQueue(LinkQueue &Q, BiTNode *x) {
    LinkNode *p = new LinkNode;
    p->p = x;
    p->pNext = NULL;
    Q.rear->pNext = p; // 入队
    Q.rear = p;        // 更新队尾
    return true;
}

// 出队
bool DeQueue(LinkQueue &Q, BiTNode *&x) {
    if (Q.rear == Q.front) {
        return false;
    } else {
        LinkNode *p = Q.front->pNext; // 指向队头元素
        x = p->p;
        Q.front->pNext = p->pNext;
        if (Q.rear == p) { // 即队列中只剩一个元素
            Q.front = Q.rear;
        }
        delete p;
        return true;
    }
}

// 层序遍历，广度优先遍历
void LevelOrder(BiTree T) {
    LinkQueue Q;
    InitQueue(Q);
    BiTNode *p;
    EnQueue(Q, T); // 树根入队
    while (!QueueEmpty(Q)) {
        DeQueue(Q, p); // p为引用，此时p为对应的树结点
        putchar(p->data);
        if (p->lchild != NULL) {
            EnQueue(Q, p->lchild);
        }
        if (p->rchild != NULL) {
            EnQueue(Q, p->rchild); // 立即使p的左右孩子入队，保证层序遍历
        }
    }
}

int main() {
    ElemType val;
    BiTree T;
    InitTree(T);

    LinkNode *phead = NULL;
    LinkNode *ptail = NULL; // 头指针，尾指针
    while (scanf("%c", &val) != EOF) {
        if (val == '\n') {
            break;
        } else {
            BuildBinaryTree(T, phead, ptail, val);
        }
    }

    cout << "-----前序遍历-----" << endl;
    PreOrder(T);
    cout << endl;

    cout << "-----中序遍历-----" << endl;
    InOrder(T);
    cout << endl;

    cout << "-----后序遍历-----" << endl;
    PostOrder(T);
    cout << endl;

    cout << "-----层序遍历-----" << endl;
    LevelOrder(T);
    cout << endl;

    return 0;
}