#include <iostream>

using namespace std;

typedef char ElemType;
typedef struct node { // 二叉链表存储结构
    ElemType data;
    struct node *Lchild, *Rchild;
} Bnode, *Bintree;

/**
 * 先序建立二叉树 TLR
 * @param T 引用 main 函数中定义的树根节点的地址
 */
void createBintree(Bintree &T) {
    ElemType ch;
    cin >> ch;
    getchar(); // 接收 space 或 enter

    if (ch == '#') { // # 结束符
        T = nullptr;
    } else {
        T = (Bintree) malloc(sizeof(Bnode)); // 新建节点
        T->data = ch;
        cout << ch << " 左节点(#结束): ";
        createBintree(T->Lchild);
        cout << ch << " 右节点(#结束): ";
        createBintree(T->Rchild);
    }
}

/**
 * 先序遍历
 */
void preOrder(Bintree T) {
    if (T) {
        cout << T->data << " ";
        preOrder(T->Lchild);
        preOrder(T->Rchild);
    }
}

/**
 * 中序遍历
 */
void inOrder(Bintree T) {
    if (T) {
        inOrder(T->Lchild);
        cout << T->data << " ";
        inOrder(T->Rchild);
    }
}

/**
 * 后序遍历
 */
void postOrder(Bintree T) {
    if (T) {
        postOrder(T->Lchild);
        postOrder(T->Rchild);
        cout << T->data << " ";
    }
}

/**
 * 层序遍历
 */
void levelOrder(Bintree T) {

    // 定义 Bintree 类型循环队列
    // 循环队列不能只保存data，因为还要通过出队列的元素获得其左右孩子
    Bintree queue[10];
    int front = 0, rear = 0; // 头尾

    // 根节点进队列
    Bintree p = T;
    if (p) {
        rear = (rear + 1) % 10;
        queue[rear] = p;
    }

    // 循环队列遍历
    while (front != rear) { // 判断循环队列不为空

        // 队头元素出队列
        front = (front + 1) % 10;
        p = queue[front];
        cout << p->data << " ";

        // 并将对头元素的孩子节点进队列
        if (p->Lchild) { // 若左孩子不空，进队
            rear = (rear + 1) % 10;
            queue[rear] = p->Lchild;
        }
        if (p->Rchild) { // 若右孩子不空，进队
            rear = (rear + 1) % 10;
            queue[rear] = p->Rchild;
        }
    }
}

/**
 * 树的高度
 * @param T
 * @return
 */
int depthBintree(Bintree T) {
    int depL, depR, dep;
    if (T == nullptr) {
        dep = 0;//空树的深度为0
    } else {
        depL = depthBintree(T->Lchild);
        depR = depthBintree(T->Rchild);
        dep = depL > depR ? depL + 1 : depR + 1; // 树的深度为其左、右子树中最深的子树加1
    }
    return dep;
}

void swapTree(Bintree T) {
    if (T) {
        Bintree p = T->Lchild;
        T->Lchild = T->Rchild;
        T->Rchild = p; // 1轮交换
        swapTree(T->Lchild);
        swapTree(T->Rchild);
    }
}

int main() {

    // 创建树
    Bintree bintree;
    cout << "输入树的根节点: ";
    createBintree(bintree);
    cout << endl;

    // 三序遍历 + 层序
    cout << "先序遍历: ";
    preOrder(bintree);
    cout << endl;
    cout << "中序遍历: ";
    inOrder(bintree);
    cout << endl;
    cout << "后序遍历: ";
    postOrder(bintree);
    cout << endl;
    cout << "层序遍历: ";
    levelOrder(bintree);
    cout << endl;

    // 树高
    cout << "树的高度: " << depthBintree(bintree) << endl << endl;

    // 交换树
    cout << "交换树" << endl;
    swapTree(bintree);

    // 交换后 三序遍历 + 层序
    cout << "先序遍历: ";
    preOrder(bintree);
    cout << endl;
    cout << "中序遍历: ";
    inOrder(bintree);
    cout << endl;
    cout << "后序遍历: ";
    postOrder(bintree);
    cout << endl;
    cout << "层序遍历: ";
    levelOrder(bintree);
    cout << endl;

    return 0;
}

测试树

输入树的根节点: 1
1 左节点(#结束): 2
2 左节点(#结束): #
2 右节点(#结束): #
1 右节点(#结束): 3
3 左节点(#结束): 4
4 左节点(#结束): #
4 右节点(#结束): #
3 右节点(#结束): 5
5 左节点(#结束): #
5 右节点(#结束): #

先序遍历: 1 2 3 4 5 
中序遍历: 2 1 4 3 5 
后序遍历: 2 4 5 3 1 
层序遍历: 1 2 3 4 5 
树的高度: 3

交换树
先序遍历: 1 3 5 4 2 
中序遍历: 5 3 4 1 2 
后序遍历: 5 4 3 2 1 
层序遍历: 1 3 2 5 4