木の巡回とは

木の操作には木の巡回と呼ばれる探索方法があります。
その探索方法を学びます。

例として以下の2分木を定義します。

       0
  1      4
2 3   5 8        
       6 7

この2分木を例として、木の巡回の出力例を見ていきましょう。

木の先行順巡回(Preorder Tree Walk)

根節点、左部分木、右部分木の順で節点の番号を出力します。

出力例
0 1 2 3 4 5 6 7 8

木の中間順巡回(Inorder Tree Walk)

左部分木、根節点、右部分木の順で節点の番号を出力します。

出力例
2 1 3 0 6 5 7 4 8

木の後行順巡回(Postorder Tree Walk)

左部分木、右部分木、根節点の順で節点の番号を出力します。

出力例
2 3 1 6 7 5 8 4 0

では、AIDU ONLINE JUDGEのALDS1_7_Cの木巡回の問題例に、
プログラムをチェックしましょう。

// 先行順巡回
void preParse(int u){
    if(u == NIL)return;
    printf(" %d",u);
    preParse(gNode[u].left);
    preParse(gNode[u].right);
}

// 中間順巡回
void inParse(int u){
    if(u == NIL)return;
    inParse(gNode[u].left);
    printf(" %d",u);
    inParse(gNode[u].right);
}

// 後行順巡回
void postParse(int u){
    if(u == NIL) return;
    postParse(gNode[u].left);
    postParse(gNode[u].right);
    printf(" %d",u);
}

出力する位置を変えることによって、
各々の出力形式で出力しています。

では、全体のソースです。

#include <stdio.h>
#include <iostream>
using namespace std;
// node最大量
#define MAX 100000
#define NIL -1

struct Node {
    int parent;
    int left;
    int right;
};

// 配列で保持する
Node gNode[MAX];

// 先行順巡回
void preParse(int u){
    if(u == NIL)return;
    printf(" %d",u);
    preParse(gNode[u].left);
    preParse(gNode[u].right);
}

// 中間順巡回
void inParse(int u){
    if(u == NIL)return;
    inParse(gNode[u].left);
    printf(" %d",u);
    inParse(gNode[u].right);
}

// 後行順巡回
void postParse(int u){
    if(u == NIL) return;
    postParse(gNode[u].left);
    postParse(gNode[u].right);
    printf(" %d",u);
}

int main(){
    int left,right,v,n,root = 0;
    cin >> n;
    // 初期化
    for(int i = 0;i < n;++i){
        gNode[i].parent = gNode[i].left = gNode[i].right = NIL;
    }
    
    for(int i = 0;i < n;++i){
        cin >> v >> left >> right;
        gNode[v].left = left;
        gNode[v].right = right;
        // 親の設定
        if(left != NIL){
            gNode[left].parent = v;
        }
        if(right != NIL){
            gNode[right].parent = v;
        }
    }

    // rootを探す
    for(int i = 0;i < n;++i){
        if(gNode[i].parent == NIL){
            root = i;
        }
    }
    
    cout << "Preorder\n";
    preParse(root);
    cout << "\n";
    cout << "Inorder\n";
    inParse(root);
    cout << "\n";
    cout << "Postorder\n";
    postParse(root);
    cout << "\n";
    
    return 0;
}