[資料結構] 由 二叉樹 “前中序/中後序 “周遊所思所想

有一段時間沒學習資料結構了,趁着開學前把樹,圖相關的知識搞一遍,下學期就主攻算法了

我希望按自己的了解記錄這個過程, 也算是督促自己

一.為什麼不能是前後序❓ 

可以唯一确定一棵二叉樹的周遊序列組合

• 已知前序和中序的周遊序列
• 已知中序和後序的周遊序列

❓為什麼已知已知前序和後序的周遊序列無法唯一确定一棵二叉樹呢?

➡因為即使可以确定層級關系,也無法得知哪個是左子樹哪個是右子樹

👇例如:       已知前序序列是ABC        後序序列是CBA

兩個任取一個都可以看出A是根節點,由後序周遊可知B是A的孩子,C是B的孩子,但左右子樹不唯一

該例中可能的情況有四種,

二.人工推導

前中序

 例一:已知👉 前序周遊序列 ABCDEF ,中序周遊序列 CBAEDF ,求後續周遊的結果

首先要清楚前中後周遊的規則,在此不再贅述

其次體會他們各自的特點及互相之間的微妙聯系

• (前序周遊結果中各個"區域"的第一個必是該區域的根)
• (後序周遊結果中各個"區域"的最後一個必是該區域的根)

在這道題中,由前序周遊可知A為整棵樹的根節點,👉再看中序周遊裡面A的左子樹(下劃線部分)有CBAEDF, 再由前序周遊的BC順序可知B是C的父親,且C是B的左孩子(确定了父節點B後,中序周遊中的排列順序可以展現出左右子樹的關系), DEF同理,這棵二叉樹長這樣👇

後序周遊結果為CBEFDA

中後序(與前中序大體相似)

 例二:已知👉 中序周遊序列 ABCDEFG,後序周遊序列 BDCAFGE,求前序周遊的結果

 與上面的例子大相徑庭,由後序周遊的特點,E為整棵樹的根,👉再看中序周遊裡面E的左子樹(下劃線部分)有ABCDEFG, 再由後序周遊的"BDCA"順序可知A是這棵子樹的根(即E的左孩子),"BCD"為A的右子孫,由後序周遊的"BDC"順序可知C為這棵子樹的根(即A的右孩子),在前序周遊中''A(BCD)EFG'',是以B,C分别為C的左右孩子,E的右子樹同理,樹長這樣👇

前序周遊結果為EACBDGF

三.代碼實作

以​​HDU 1710 Binary Tree Traversals​​為例

#include <stdio.h>

const int N = 1010;
int pre[N], in[N], post[N];  //先序、中序、後序
int k;
struct node{
    int value;
    node *l, *r;
    node(int value = 0, node *l = NULL, node *r = NULL):value(value), l(l), r(r){}
};

void buildtree(int l, int r, int &t, node* &root) { //建樹
    int flag = -1;
    for(int i = l; i <= r; i++) //先序的第一個是根，找到對應的中序的位置
        if(in[i] == pre[t]){
            flag = i; 
            break;
        }
    if(flag == -1) return;       //結束
    root = new node(in[flag]);   //建立結點
    t++;
    if(flag > l)  buildtree(l, flag - 1, t, root ->l);
    if(flag < r)  buildtree(flag + 1, r, t, root ->r);
}

void preorder (node *root){       //求先序序列
    if(root != NULL){
        post[k++] = root ->value;  //輸出
        preorder (root ->l);
        preorder (root ->r);
    }
}

void inorder (node *root){        //求中序序列
    if(root != NULL){
        inorder (root ->l);
        post[k++] = root ->value;  //輸出
        inorder (root ->r);
    }
}

void postorder (node *root){      //求後序序列
    if(root != NULL){
        postorder (root ->l);
        postorder (root ->r);
        post[k++] = root ->value;  //輸出
    }
}

void remove_tree(node *root){      //釋放空間
    if(root == NULL) return;
    remove_tree(root->l);
    remove_tree(root->r);
    delete root;
}

int main(){
    int n;
    while(~scanf("%d", &n)){
        for(int i=1;i<=n;i++) scanf("%d", &pre[i]);
        for(int j=1;j<=n;j++) scanf("%d", &in[j]);
        node *root;
        int t = 1;
        buildtree(1, n, t, root);
        k = 0;           //記錄結點個數
        postorder(root);
        for(int i=0;i<k;i++) printf("%d%c",post[i],i==k-1?'\n':' ');
          //作為驗證，這裡可以用preorder()和inorder()檢查先序和中序周遊
        remove_tree(root);
    }
    return 0;
}