ALDS1_7_B BinaryTree(2分木)を参考にしてと2分木表現を学ぶ

AIZU ONLINE JUDGEのALDS1_7_B BinaryTree
の問題を参考に、2分木の表現方法を学びます。

問題文

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

• uの節点番号
• uの親
• uの兄弟
• uの子の数
• uの深さ
• uの高さ
• 節点の種類（根、内部節点または葉）

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

入力例などは以下を参考にしてください。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_B&lang=jp

2分木を表現する構造体の定義

2分木を表現するための構造体の定義をします。
木を表現するためには、節点が必要になりますが、
2分木では節点は左右の子のみとルートを示す親を持てば
木全体を表現することができることがわかると思います。

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

2分木の深さをセットする

2分木の深さを求めるために、木のrootから子を探索し
left、right共にNILになるまで、再起的にチェックします。

// 深さを設定する
void setDepth(int u,int d){
    // 親の節点が葉のケース
    if(u == NIL) return;
    gDepth[u] = d;
    // 左右の子にもセットする
    setDepth(gNode[u].left, d + 1);
    setDepth(gNode[u].right, d + 1);
}

兄弟のノードを求める

兄弟のノードを求めるには、
単純に親がいるかをチェックし、親の左の子・右の子を調べます
子が自身のノードである可能性があるので、そのケースを除きます。

int getSibling(int u){
    // rootの場合
    if(gNode[u].parent == NIL)return NIL;
    // 自身が右の子だった場合
    if(gNode[gNode[u].parent].left != u && gNode[gNode[u].parent].left != NIL){
        return gNode[gNode[u].parent].left;
    }
    // 自身が左の子だった場合
    if(gNode[gNode[u].parent].right != u && gNode[gNode[u].parent].right != NIL){
        return gNode[gNode[u].parent].right;
    }
    // 親が一つしか子を持たない状態
    return NIL;
}

2分木の高さを求める

この場合の高さは、あるノードの末尾の子から自分との差分になります。
自分から左右の子が存在するかどうか再帰的にチェックしていき、深い方の子と自分との差分を返します。

// 高さの設定をする
int setHeight(int u){
    int h1,h2;
    h1 = h2 = 0;
    if(gNode[u].left != NIL){
        h1 = setHeight(gNode[u].left) + 1;
    }
    if(gNode[u].right != NIL){
        h2 = setHeight(gNode[u].right) + 1;
    }
    return gHeight[u] = (h1 > h2) ? h1 : h2;
}

最後にc++で書かれた全体のソースを載せます。

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

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

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

// 兄弟を返す
int getSibling(int u){
    // rootの場合
    if(gNode[u].parent == NIL)return NIL;
    // 自身が右の子だった場合
    if(gNode[gNode[u].parent].left != u && gNode[gNode[u].parent].left != NIL){
        return gNode[gNode[u].parent].left;
    }
    // 自身が左の子だった場合
    if(gNode[gNode[u].parent].right != u && gNode[gNode[u].parent].right != NIL){
        return gNode[gNode[u].parent].right;
    }
    // 親が一つしか子を持たない状態
    return NIL;
}

void print(int node){
    cout << "node " << node << ": ";
    cout << "parent = " << gNode[node].parent << ", ";
    cout << "sibling = " << getSibling(node) << ", ";
    
    int deg = 0;
    if(gNode[node].left != NIL) deg++;
    if(gNode[node].right != NIL) deg++;
    cout << "degree = " << deg << ", ";
    cout << "depth = " << gDepth[node] << ", ";
    cout << "height = " << gHeight[node] << ", ";
    
    if(gNode[node].parent == NIL){
        cout << "root\n";
    }else if(gNode[node].left == NIL && gNode[node].right == NIL){
        cout << "leaf\n";
    }else{
        cout << "internal node\n";
    }
}

// 深さを設定する
void setDepth(int u,int d){
    // 親の節点が葉のケース
    if(u == NIL) return;
    gDepth[u] = d;
    // 左右の子にもセットする
    setDepth(gNode[u].left, d + 1);
    setDepth(gNode[u].right, d + 1);
}

// 高さの設定をする
int setHeight(int u){
    int h1,h2;
    h1 = h2 = 0;
    if(gNode[u].left != NIL){
        h1 = setHeight(gNode[u].left) + 1;
    }
    if(gNode[u].right != NIL){
        h2 = setHeight(gNode[u].right) + 1;
    }
    return gHeight[u] = (h1 > h2) ? h1 : h2;
}

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;
        }
    }
    
    // 根からはじめて深さを代入する
    setDepth(root, 0);
    setHeight(root);
    
    for(int i = 0;i < n;++i){
        print(i);
    }
    return 0;
}

参考ソース
https://book.mynavi.jp/ec/products/detail/id=35408