二叉树 | 遍历 (链表实现)

遍历

二叉树的遍历即通过一定顺序访问二叉树的所有结点。

• 先序遍历 ： 根 左 右
• 中序遍历 ： 左 根 右
• 后序遍历 ： 左 右 根
• 层次遍历

前三种通常递归实现（DFS），层次遍历通过BFS实现。
先、中、后指：根结点在遍历中的位置。
无论递归遍历中哪一种，左子树一定先于右子树遍历。

递归遍历

• 先序、中序、后序差别仅仅是访问根结点的时机。

void xxxxOrder(Node *root) {
    // 递归边界
    if(root == NULL) return;
    // 先序：访问根结点root……
    // 递归左、右子树
    xxxxOrder(root->lchild);
    // 中序：访问根结点root……
    xxxxOrder(root->rchild);
    // 后序：访问根结点root……
}

根据中序、先序/后序/层序遍历还原二叉树（递归）

（所有元素不相同时）

• 中序遍历序列中，只要知道了根结点，就能够划分左右子树。
• 如何知道根结点：先序/后序/层序中的一种。
• 递归边界：序列长度 <= 0
• 先序/后序/层序组合，不能还原出二叉树。

层序遍历

二叉树的广度正体现在层次上，BFS搜索即可（用queue实现）。
若需要计算每个结点的层次，在struct Node中加int layer字段。

• ⚠️queue中存的是Node*，直接存Node修改不了原node（node->layer），而只修改了副本。
• 孩子入队前先判空，不空则把孩子的 layer 置为当前结点 layer + 1，再入队。

例

• 给定中序、后序序列，求层序遍历序列
  ⚠️递归传递的信息为：构成当前子树的中序、后序序列的下标范围
  ⚠️新结点Node* root = new Node 分配空间
  ⚠️将递归调用返回的Node* 赋给root->lchild, root->rchild才能把树连起来！！！
  1020 Tree Traversals (25 分)

#include <cstdio>
#include <queue>

using namespace std;
int nn, in_order[32], post_order[32];
struct Node {
    int data;
    Node *lchild, *rchild;
};

Node *create(int in_st, int in_ed, int post_st, int post_ed) {
    if (in_st > in_ed || post_st > post_ed)
        return NULL;
    int root_data = post_order[post_ed];
    int root_pos = -1;
    for (int i = in_st; i <= in_ed; ++i) {
        if (in_order[i] == root_data) {
            root_pos = i;
            break;
        }
    }
    int ltree_size = root_pos - in_st;
    /*
     * 注意：
     *   1    新结点Node* root = new Node 分配空间
     *   2    将递归调用返回的Node* 赋给root->lchild, root->rchild
     *         才能把树连起来！！！
     */
    Node *root = new Node;
    root->data = root_data;
    root->lchild = create(in_st, root_pos - 1, post_st, post_st + ltree_size - 1);
    root->rchild = create(root_pos + 1, in_ed, post_st + ltree_size, post_ed - 1);
    return root;
}

void BFS(Node *root) {
    int cnt = 0;
    queue<Node *> mq;
    mq.push(root);
    while (!mq.empty()) {
        Node *curr = mq.front();
        mq.pop();
        printf("%d", curr->data);
        cnt++;
        if (cnt < nn) printf(" ");
        if (curr->lchild != NULL) {
            mq.push(curr->lchild);
        }
        if (curr->rchild != NULL) {
            mq.push(curr->rchild);
        }
    }
}

int main() {
    scanf("%d", &nn);
    for (int i = 0; i < nn; ++i)
        scanf("%d", &post_order[i]);
    for (int i = 0; i < nn; ++i)
        scanf("%d", &in_order[i]);
    Node *root = create(0, nn - 1, 0, nn - 1);
    BFS(root);
    return 0;
}

• 1086 Tree Traversals Again (25 分)
  给定中序、先序序列，求后序遍历序列

#include <cstdio>
#include <stack>
#include <cstring>

using namespace std;
struct Node {
    int data;
    Node *lchild, *rchild;
};
int nn, in_order[32], pre_order[32];

Node *create_btree(int in_st, int in_ed, int pre_st, int pre_ed) {
    if (in_st > in_ed || pre_st > pre_ed)
        return NULL;
    Node *root = new Node;
    int root_data;
    root_data = root->data = pre_order[pre_st];
    int div = -1;
    for (int i = in_st; i <= in_ed; ++i) {
        if (in_order[i] == root_data) {
            div = i;
            break;
        }
    }
    int rchild_size = in_ed - div;
    root->lchild = create_btree(in_st, div - 1, pre_st + 1, pre_ed - rchild_size);
    root->rchild = create_btree(div + 1, in_ed, pre_ed - rchild_size + 1, pre_ed);
    return root;
}

void post_order_traverse(Node *root) {
    if (root == NULL) return;
    if (root->lchild != NULL) {
        post_order_traverse(root->lchild);
    }
    if (root->rchild != NULL) {
        post_order_traverse(root->rchild);
    }
    printf("%d", root->data);
    if (--nn) printf(" ");
}

int main() {
    stack<int> seq;
    int curr, ii = 0, pi = 0;
    scanf("%d", &nn);
    char op[5];
    for (int i = 0; i < 2 * nn; ++i) {
        scanf("%s", op);
        if (strlen(op) == 4) {
            scanf("%d", &curr);
            seq.push(curr);
            pre_order[pi] = curr;
            pi++;
        } else {
            in_order[ii] = seq.top();
            seq.pop();
            ii++;
        }
    }
    Node *root = create_btree(0, nn - 1, 0, nn - 1);
    post_order_traverse(root);
    return 0;
}