学习的二叉树遍历方式有四种：前序遍历、中序遍历、后序遍历、层序遍历。

也比较简单，复习下就ok了。

        A
       / \
      B   C
     / \   \
    D   E   F

1. 前序遍历

顺序是：

根 → 左 → 右

对示例二叉树进行前序遍历：

A → B → D → E → C → F

先访问自己，再访问左边，最后访问右边。

递归代码：

void preOrder(const BiTree &T) {
    if (T != nullptr) {
        std::cout << T->data << " ";
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

2. 中序遍历

顺序是：

左 → 根 → 右

遍历结果：

D → B → E → A → C → F

先访问左边，再访问自己，最后访问右边。

递归代码：

void inOrder(const BiTree &T) {
    if (T != nullptr) {
        inOrder(T->lchild);
        std::cout << T->data << " ";
        inOrder(T->rchild);
    }
}

中序遍历有一个重要特点：如果二叉树是二叉搜索树，中序遍历得到的通常是从小到大的有序序列。

3. 后序遍历

顺序是：

左 → 右 → 根

遍历结果：

D → E → B → F → C → A

先处理左右子节点，最后处理自己。

递归代码：

void PostOrder(const BiTree &T) {
    if (T != nullptr) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        std::cout << T->data << " ";
    }
}

后序遍历适合处理“先处理子节点，再处理父节点”的问题，例如计算文件夹大小、删除整棵树等。

4. 层序遍历

层序遍历是按照树的层级，从上到下、从左到右访问：

第一层：A
第二层：B、C
第三层：D、E、F

最终结果：

A → B → C → D → E → F

层序遍历通常使用队列实现：

void LevelOrder(const BiTree &T) {
    if (T == nullptr) {
        return;
    }

    std::queue<BiTree> Q;   //创建一个队列
    Q.push(T);

    while (!Q.empty()) {    
        //队列不为空就一直循环，节点进入队列的同时将节点的左右孩子入列
        if (Q.front()->lchild != nullptr) {
            Q.push(Q.front()->lchild);
        }

        if (Q.front()->rchild != nullptr) {
            Q.push(Q.front()->rchild);
        }

        std::cout << Q.front()->data << " ";
        Q.pop();
    }
}

注意：无论是前序、中序还是后序，通常都是先左子树，后右子树，变化的只是根节点的位置。

完整代码:

#include <iostream>
#include <queue>

using ElemType = char;

struct BiTNode {
    struct BiTNode* lchild;
    struct BiTNode* rchild;
    ElemType data;
};

using BiTree = BiTNode*;

BiTNode* createNode(ElemType data) {
    BiTNode* node = new BiTNode;
    node->data = data;
    node->lchild = nullptr;
    node->rchild = nullptr;
    return node;
}

void preOrder(const BiTree &T) {
    //前置遍历
    if (T != nullptr) {
        std::cout << T->data << " ";
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

void inOrder(const BiTree &T) {
    //中置遍历
    if (T != nullptr) {
        inOrder(T->lchild);
        std::cout << T->data << " ";
        inOrder(T->rchild);
    }
}

void PostOrder(const BiTree &T) {
    //后置遍历
    if (T != nullptr) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        std::cout << T->data << " ";
    }
}

void LevelOrder(const BiTree &T) {
    //层级遍历
    if (T == nullptr) {
        return;
    }

    std::queue<BiTree> Q;   //创建一个队列
    Q.push(T);

    while (!Q.empty()) {    
        //队列不为空就一直循环，节点进入队列的同时将节点的左右孩子入列
        if (Q.front()->lchild != nullptr) {
            Q.push(Q.front()->lchild);
        }

        if (Q.front()->rchild != nullptr) {
            Q.push(Q.front()->rchild);
        }

        std::cout << Q.front()->data << " ";
        Q.pop();
    }
}

void destroyTree(BiTree node) {
    //后置遍历释放内存，先释放左子树，后右子树，最后释放根节点
    if (node != nullptr) {
        destroyTree(node->lchild); 
        destroyTree(node->rchild); 
        delete node;               
    }
}

int main() {
    //           A
    //         /   \
    //        B     C
    //       / \   / \
    //      D   E F   G

    BiTNode* A = createNode('A');
    BiTNode* B = createNode('B');
    BiTNode* C = createNode('C');
    BiTNode* D = createNode('D');
    BiTNode* E = createNode('E');
    BiTNode* F = createNode('F');
    BiTNode* G = createNode('G');

    A->lchild = B;  A->rchild = C; 
    B->lchild = D;  B->rchild = E; 
    C->lchild = F;  C->rchild = G; 

    std::cout << "前置遍历: ";
    preOrder(A);
    std::cout << std::endl;

    std::cout << "中置遍历: ";
    inOrder(A);
    std::cout << std::endl;

    std::cout << "后置遍历: ";
    PostOrder(A);
    std::cout << std::endl;

    std::cout << "层级遍历: ";
    LevelOrder(A);
    std::cout << std::endl;

    destroyTree(A);
    return 0;
}

输出结果：

前置遍历: A B D E C F G 
中置遍历: D B E A F C G 
后置遍历: D E B F G C A 
层级遍历: A B C D E F G

最近睡眠相当不规律啊，再这样下去真要进入凉爽的夏夜了 _(┐「ε:)_

牢广