二叉树的遍历 ¶

二叉树遍历 | 知乎@柠檬沙棘1996

遍历是二叉树各种操作的基础，求二叉树的深度、求叶结点的个数等都需要基于遍历实现。

从二叉树的递归定义可知，遍历一棵二叉树需要确定对根结点 \(N\)、左子树 \(L\) 和右子树 \(R\) 的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有前序遍历、中序遍历和后序遍历三种，其中的序指的是根结点在何时被访问。

先序遍历 ¶

若二叉树为空，则什么也不做；否则，

访问根结点 \(N\)
先序遍历左子树 \(L\)
先序遍历右子树 \(R\)

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *left, *right;
} BiTNode, *BiTree;

void preOrder(BiTree T) {
    if (T != NULL) {
        visit(T);           // 访问根结点
        preOrder(T->left);  // 先序遍历左子树
        preOrder(T->right); // 先序遍历右子树
    }
}

中序遍历 ¶

若二叉树为空，则什么也不做；否则，

中序遍历左子树 \(L\)
访问根结点 \(N\)
中序遍历右子树 \(R\)

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *left, *right;
} BiTNode, *BiTree;

void inOrder(BiTree T) {
    if (T != NULL) {
        inOrder(T->left);  // 中序遍历左子树
        visit(T);          // 访问根结点
        inOrder(T->right); // 中序遍历右子树
    }
}

后序遍历 ¶

若二叉树为空，则什么也不做；否则，

后序遍历左子树 \(L\)
后序遍历右子树 \(R\)
访问根结点 \(N\)

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *left, *right;
} BiTNode, *BiTree;

void postOrder(BiTree T) {
    if (T != NULL) {
        postOrder(T->left);  // 后序遍历左子树
        postOrder(T->right); // 后序遍历右子树
        visit(T);            // 访问根结点
    }
}

层次遍历 ¶

故名思议，层次遍历就是按照层次顺序依次访问二叉树中的每个结点。

进行层次遍历时，需要借助一个队列来实现，具体思想如下：

初始化一个空队列，根结点入队
若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
重复步骤2，直至队列为空

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *left, *right;
} BiTNode, *BiTree;

void levelOrder(BiTree T) {
    InitQueue(Q);                // 初始化队列
    EnQueue(Q, T);               // 将根结点入队
    while (!IsEmpty(Q)) {
        DeQueue(Q, T);           // 队首结点出队
        visit(T);                // 访问该结点
        if (T->left != NULL) {
            EnQueue(Q, T->left); // 将左孩子入队
        }
        if (T->right != NULL) {
            EnQueue(Q, T->right); // 将右孩子入队
        }
    }
}