#include <iostream>

using namespace std;

typedef char ElemType;
typedef struct node { // 二叉鏈表存儲(chǔ)結(jié)構(gòu)
    ElemType data;
    struct node *Lchild, *Rchild;
} Bnode, *Bintree;

/**
 * 先序建立二叉樹(shù) TLR
 * @param T 引用 main 函數(shù)中定義的樹(shù)根節(jié)點(diǎn)的地址
 */
void createBintree(Bintree &T) {
    ElemType ch;
    cin >> ch;
    getchar(); // 接收 space 或 enter

    if (ch == '#') { // # 結(jié)束符
        T = nullptr;
    } else {
        T = (Bintree) malloc(sizeof(Bnode)); // 新建節(jié)點(diǎn)
        T->data = ch;
        cout << ch << " 左節(jié)點(diǎn)(#結(jié)束): ";
        createBintree(T->Lchild);
        cout << ch << " 右節(jié)點(diǎn)(#結(jié)束): ";
        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 類(lèi)型循環(huán)隊(duì)列
    // 循環(huán)隊(duì)列不能只保存data，因?yàn)檫€要通過(guò)出隊(duì)列的元素獲得其左右孩子
    Bintree queue[10];
    int front = 0, rear = 0; // 頭尾

    // 根節(jié)點(diǎn)進(jìn)隊(duì)列
    Bintree p = T;
    if (p) {
        rear = (rear + 1) % 10;
        queue[rear] = p;
    }

    // 循環(huán)隊(duì)列遍歷
    while (front != rear) { // 判斷循環(huán)隊(duì)列不為空

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

        // 并將對(duì)頭元素的孩子節(jié)點(diǎn)進(jìn)隊(duì)列
        if (p->Lchild) { // 若左孩子不空，進(jìn)隊(duì)
            rear = (rear + 1) % 10;
            queue[rear] = p->Lchild;
        }
        if (p->Rchild) { // 若右孩子不空输虱，進(jìn)隊(duì)
            rear = (rear + 1) % 10;
            queue[rear] = p->Rchild;
        }
    }
}

/**
 * 樹(shù)的高度
 * @param T
 * @return
 */
int depthBintree(Bintree T) {
    int depL, depR, dep;
    if (T == nullptr) {
        dep = 0;//空樹(shù)的深度為0
    } else {
        depL = depthBintree(T->Lchild);
        depR = depthBintree(T->Rchild);
        dep = depL > depR ? depL + 1 : depR + 1; // 樹(shù)的深度為其左纺阔、右子樹(shù)中最深的子樹(shù)加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() {

    // 創(chuàng)建樹(shù)
    Bintree bintree;
    cout << "輸入樹(shù)的根節(jié)點(diǎn): ";
    createBintree(bintree);
    cout << endl;

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

    // 樹(shù)高
    cout << "樹(shù)的高度: " << depthBintree(bintree) << endl << endl;

    // 交換樹(shù)
    cout << "交換樹(shù)" << 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;
}

測(cè)試樹(shù)

輸入樹(shù)的根節(jié)點(diǎn): 1
1 左節(jié)點(diǎn)(#結(jié)束): 2
2 左節(jié)點(diǎn)(#結(jié)束): #
2 右節(jié)點(diǎn)(#結(jié)束): #
1 右節(jié)點(diǎn)(#結(jié)束): 3
3 左節(jié)點(diǎn)(#結(jié)束): 4
4 左節(jié)點(diǎn)(#結(jié)束): #
4 右節(jié)點(diǎn)(#結(jié)束): #
3 右節(jié)點(diǎn)(#結(jié)束): 5
5 左節(jié)點(diǎn)(#結(jié)束): #
5 右節(jié)點(diǎn)(#結(jié)束): #

先序遍歷: 1 2 3 4 5 
中序遍歷: 2 1 4 3 5 
后序遍歷: 2 4 5 3 1 
層序遍歷: 1 2 3 4 5 
樹(shù)的高度: 3

交換樹(shù)
先序遍歷: 1 3 5 4 2 
中序遍歷: 5 3 4 1 2 
后序遍歷: 5 4 3 2 1 
層序遍歷: 1 3 2 5 4