03 二叉树的遍历

03-二叉树的遍历¶

常用的遍历方法有：

void PreOrderTraversal(BinTree BT)：先序——根、左子树、右子树；
void InOrderTraversal(BinTree BT)：中序——左子树、根、右子树；
void PostOrderTraversal(BinTree BT)：后序——左子树、右子树、根；
void LevelOrderTraversal(BinTree BT)：层次遍历/层序遍历，从上到下、从左到右。

先中后序递归遍历¶

先序遍历¶

遍历过程为：

访问根节点
先序遍历其左子树
先序遍历其右子树

#include <iostream>

/* 先序遍历 */
void preOrderTraversal(BiTree BT) {
    if (BT != nullptr) {
        std::cout << BT->data << " "; // 访问根结点
        preOrderTraversal(BT->left);  // 遍历左子树
        preOrderTraversal(BT->right); // 遍历右子树
    }
}

中序遍历¶

遍历过程为：

中序遍历其左子树
访问根节点
中序遍历其右子树

#include <iostream>

/* 中序遍历 */
void inOrderTraversal(BiTree BT) {
    if (BT != nullptr) {
        inOrderTraversal(BT->left);   // 遍历左子树
        std::cout << BT->data << " "; // 访问根结点
        inOrderTraversal(BT->right);  // 遍历右子树
    }
}

后序遍历¶

遍历过程为：

后序遍历其左子树
后序遍历其右子树
访问根节点

#include <iostream>

/* 后序遍历 */
void postOrderTraversal(BiTree BT) {
    if (BT != nullptr) {
        postOrderTraversal(BT->left);  // 遍历左子树
        postOrderTraversal(BT->right); // 遍历右子树
        std::cout << BT->data << " ";  // 访问根结点
    }
}

遍历技巧¶

前序、中序和后序遍历都属于深度优先遍历（depth-first traversal），也称深度优先搜索（depth-first search, DFS），它体现了一种“先走到尽头，再回溯继续”的遍历方式。

下图展示了对二叉树进行深度优先遍历的工作原理。深度优先遍历就像是绕着整棵二叉树的外围“走”一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历。

先中后序非递归遍历¶

使用堆栈。

中序遍历¶

遇到一个结点，就把它压栈，并去遍历它的左子树
当左子树遍历结束以后，从栈顶弹出这个结点并访问它的值
然后按照其右指针去中序遍历该节点右子树

#include <iostream>
#include <stack>

void inOrderTraversal(BiTree BT) {
    BiTree T = BT;
    std::stack<BiTree> s;
    while (T != nullptr || !s.empty()) {
        while (T != nullptr) { /* 一直向左并把沿途结点压入堆栈 */
            s.push(T);
            T = T->left; // 切换至左子树根结点
        }
        if (!s.empty()) {
            T = s.top(); // 结点弹出堆栈
            s.pop();
            std::cout << T->data << " "; // 打印结点
            T = T->right;                // 转向右子树
        }
    }
}

先序遍历¶

#include <iostream>
#include <stack>

void preOrderTraversal(BiTree BT) {
    BiTree T = BT;
    std::stack<BiTree> s;
    while (T != nullptr || !s.empty()) {
        while (T != nullptr) {           /* 一直向左遍历 */
            s.push(T);                   // 将当前结点压栈
            std::cout << T->data << " "; // 访问当前结点
            T = T->left;                 // 移动到左子结点
        }
        if (!s.empty()) {
            T = s.top();  // 获取栈顶结点
            s.pop();      // 弹出栈顶结点
            T = T->right; // 转向右子树
        }
    }
}

后序遍历¶

#include <iostream>
#include <stack>

void postOrderTraversal(BiTree BT) {
    BiTree T = BT;
    BiTree lastVisited = nullptr; // 记录上一个访问的结点
    std::stack<BiTree> s;

    while (T != nullptr || !s.empty()) {
        while (T != nullptr) { /* 一直向左并将沿途结点压入堆栈 */
            s.push(T);
            T = T->left; // 切换至左子树
        }

        T = s.top(); // 查看栈顶元素，但不弹出

        /* 如果右子树为空，或者右子树已被访问 */
        if (T->right == nullptr || T->right == lastVisited) {
            s.pop();                     // 弹出栈顶元素
            std::cout << T->data << " "; // 访问根结点
            lastVisited = T;             // 更新上一个访问的结点
            T = nullptr;                 // 重置T，避免再次向左遍历
        } else {
            /* 转向右子树继续遍历 */
            T = T->right;
        }
    }
}

层序遍历¶

二叉树遍历的核心问题：二维结构的线性化

从结点访问其左、右子结点。问题就在于访问左子结点后，怎么再访问右子结点？
- 需要一个存储结构保存暂时不访问的结点：队列

队列实现¶

遍历从根结点开始，首先根结点入队，然后开始执行循环：

结点出队
访问该节点
其左右儿子顺序入队

#include <iostream>
#include <queue>

void levelOrderTraversal(BiTree BT) {
    if (BT == nullptr) /* 如果树为空，直接返回 */
        return;
    BiTree T = BT;
    std::queue<BiTree> q;
    q.push(T);                       // 将根结点入队
    while (!q.empty()) {             /* 队列不为空时继续遍历 */
        T = q.front();               // 获取队首结点
        q.pop();                     // 队首结点出队
        std::cout << T->data << " "; // 访问当前结点
        if (T->left != nullptr)
            q.push(T->left); // 左子结点入队
        if (T->right != nullptr)
            q.push(T->right); // 右子结点入队
    }
}

注意如果指针为 nullptr ，不要添加至队列中，否则会导致访问空指针的问题。

队列换成堆栈的效果¶

/* 直接把队列换成栈 */
void traversal(BiTree BT) {
    if (BT == nullptr) /* 如果树为空，直接返回 */
        return;
    BiTree T = BT;
    std::stack<BiTree> q;
    q.push(T);                       // 将根结点入队
    while (!q.empty()) {             /* 队列不为空时继续遍历 */
        T = q.top();                 // 获取队首结点
        q.pop();                     // 队首结点出队
        std::cout << T->data << " "; // 访问当前结点
        if (T->left != nullptr)
            q.push(T->left); // 左子结点入队
        if (T->right != nullptr)
            q.push(T->right); // 右子结点入队
    }
}

实现的效果类似于先序遍历，顺序是根节点->右子树->左子树

因此可以通过交换左、右子结点的入队顺序来将其变成先序遍历。

遍历的应用¶

二元运算表达式树及其遍历¶

三种遍历可以得到三种不同的访问结果：

先序遍历得到前缀表达式：++a*bc*+*defg
中序遍历得到中缀表达式：a+b*c+d*e+f*g
后序遍历得到后缀表达式：abc*+de*f+g*+

两种遍历序列确定二叉树¶

必须要有中序遍历才行！！！

只知道先序与后序遍历结果，能确定根节点但是不能确定左右子树的分界在哪里，这样无法得到结果。如先序遍历为 \(AB\)，后序遍历为 \(BA\)，可以知道根节点是 \(A\)，但是 \(B\) 究竟在左子树还是右子树这一点无法确定。

先序和中序¶

根据先序遍历序列第一个结点确定根结点
根据根结点在中序遍历序列中分割出左右两个子序列
对左子树和右子树分别递归使用相同的方法继续分解

中序和后序¶

原理类似先序和中序