ALDS1_7根付き木の解法と根付き木についてc++で学ぶ

AIZU Online judgeの根付き木の解法メモです。
サンプルのコードがわかりにくかったので、読み解いてみました。

問題は以下になります。

与えられた根付き木 T の各節点 u
について、以下の情報を出力するプログラムを作成してください。

• uの節点番号
• uの親の節点番号
• uの深さ
• uの節点の種類（根、内部節点または葉）
• uの子のリスト

ここでは、与えられる木は n 個の節点を持ち、それぞれ 0 から n－1 の番号が割り当てられているものとします。

入力

入力の最初の行に、節点の個数 n が与えられます。続く n行目に、各節点の情報が次の形式で１行に与えられます。

id
k c1 c2 ... ck

idは節点の番号、k は次数を表します。
c1 c2 ...ck は 1 番目の子の節点番号、... k 番目の子の節点番号を示します。

出力方式

次の形式で節点の情報を出力してください。節点の情報はその番号が小さい順に出力してください。

node id: parent = p , depth = d, type, [c1...ck]

pは親の番号を示します。ただし、親を持たない場合は -1 とします。
dは節点の深さを示します。

typeは根、内部節点、葉をそれぞれあらわす root、internal node、leaf の文字列のいずれかです。
ただし、根が葉や内部節点の条件に該当する場合は root とします。

c1...ck は子のリストです。
順序木とみなし入力された順に出力してください。
カンマ空白区切りに注意してください。
出力例にて出力形式を確認してください。

入力例

13
0 3 1 4 10
1 2 2 3
2 0
3 0
4 3 5 6 7
5 0
6 0
7 2 8 9
8 0
9 0
10 2 11 12
11 0
12 0

出力

node 0: parent = -1, depth = 0, root, [1, 4, 10]
node 1: parent = 0, depth = 1, internal node, [2, 3]
node 2: parent = 1, depth = 2, leaf, []
node 3: parent = 1, depth = 2, leaf, []
node 4: parent = 0, depth = 1, internal node, [5, 6, 7]
node 5: parent = 4, depth = 2, leaf, []
node 6: parent = 4, depth = 2, leaf, []
node 7: parent = 4, depth = 2, internal node, [8, 9]
node 8: parent = 7, depth = 3, leaf, []
node 9: parent = 7, depth = 3, leaf, []
node 10: parent = 0, depth = 1, internal node, [11, 12]
node 11: parent = 10, depth = 2, leaf, []
node 12: parent = 10, depth = 2, leaf, []

問題は以上です。

根付き木とは

根(root)を持つ木構造のことを根付き木といいます。
根は親を持たない唯一の節点のことをいいます。

では、問題を解いていきます。
まず、木の接点となるnodeの定義をします。

// node最大量
#define MAX 100005
#define NIL -1

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

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

構造体としてNodeを定義して
子がないことなどを示すためNILを定義しました。
NILはobjective-cなどにも定義されています。

leftは子という意味合いでrightは同じ階層の兄弟のような意味合いです。

続いて出力関数を定義します。

void print(int node){
    cout << "node " << node << ": ";
    cout << "parent = " << gNode[node].parent << ", ";
    cout << "depth = " << gDepth[node] << ", ";
    
    if(gNode[node].parent == NIL) cout << "root, ";
    else if(gNode[node].left == NIL)cout << "leaf, ";
    else cout << "internal node, ";
    
    cout << "[";
    
    for(int i = 0,left = gNode[node].left;left != NIL;++i,left = gNode[left].right){
        if(i) cout << ", ";
        cout << left;
    }
    cout << "]" << endl;
}

わかりにくいところは、left(左の木)を出力する箇所だと思います。
順番としてまず、対象のnodeのleftを出力します。
続いて、出力したleft nodeに飛び、そのleft(nodeと表現できる)のrightをのleftを出力
これを繰り返します。

続いて深さを求めて、global変数gDepthに代入する関数です。

// 再帰的に深さを求める
void rec(int node ,int parent){
    gDepth[node] = parent;
    if(gNode[node].right != NIL){
        // 右の兄弟に同じ深さを設定
        rec(gNode[node].right,parent);
    }
    if(gNode[node].left != NIL){
        // 最も左の子に自分の深さ+1を設定
        rec(gNode[node].left,parent + 1);
    }
}

道具が揃ったので、main関数を書きます。

int main(){
    int nodeNum,nodeIndex,node,left,root,n;
    cin >> n;
    // 1.初期化
    for(int i = 0;i < n;++i){
        gNode[i].parent = gNode[i].left = gNode[i].right = NIL;
    }
    // 2.nodeに代入していく
    for(int i = 0;i < n;++i){
        cin >> nodeIndex >> nodeNum;
        for(int j = 0;j < nodeNum;++j){
            cin >> node;
            // 初期値はleft
            if(j == 0){
                gNode[nodeIndex].left = node;
            }
            else{
                gNode[left].right = node;
            }
            left = node;
            gNode[node].parent = nodeIndex;
        }
    }
    
    // 3.rootを探す
    for(int i = 0;i < n;++i){
        if(gNode[i].parent == NIL){
            root = i;
        }
    }
    
    // 根からはじめて深さを代入する
    rec(root,0);
    
    // 4.nodeのindexごとに出力する
    for(int i = 0;i < n;++i){
        print(i);
    }
    return 0;
}

1.初期化
まずは、NILで初期化します。

2.gNodeに入力された情報を埋め込みます。
初期値は必ずleftに2つめ以降はrightに入れていきます。
nodeの親は変わりません。

3.で根をさがしてそのindexを代入しています。

4.最後にprint関数を使い、nodeのindex順に出力します。

以上です。

こちらを参考にしています。