C言語で根付き木を実装してみた

# はじめに
こんにちは、kuwaです。

本記事では、C言語による **根付き木(Rooted Trees)** のサンプルコードを紹介します。

> ⚠️ 本記事は個人的な学習メモとして作成したものであり、内容に誤りが含まれている可能性があります。参考にされる際はご注意ください。

---

## 根付き木

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

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

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

---


## 入出力仕様

### 入力

入力の最初の行に、節点の個数 `n` が与えられます。続く `n` 行には、各節点の情報が次の形式で 1 行に与えられます。
```
id k c1 c2 ... ck
```

- `id` は節点の番号  
- `k` は子の数（次数）  
- `c1` 〜 `ck` は子の節点番号（順序付き）  

### 出力

次の形式で節点の情報を出力してください。節点の情報は節点番号が小さい順に出力します。
```
node id: parent = p, depth = d, type, [c1, c2, ..., ck]node id: parent = p, depth = d, type, [c1, c2, ..., ck]
```


- `p` は親の番号（親が存在しない場合は `-1`）  
- `d` は節点の深さ  
- `type` は `root`（根）、`internal node`（内部節点）、`leaf`（葉）のいずれか  
- `c1`〜`ck` は子のリスト（入力と同じ順序で出力）  

---

## 制約

- `1 ≤ n ≤ 100,000`  
- 節点の深さは `20` を超えない  
- 任意の 2 つの節点間には必ず経路が存在する（連結な木）


---

## 入出力例

#### 入力例 1
```
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
```
#### 入力例 1 に対する出力
```
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, []
```

#### 入力例 2
```
4
1 3 3 2 0
0 0
3 0
2 0
```
#### 入力例 2 に対する出力
```
0
```


## サンプルコード



```c
#include<stdio.h>

// 次数＝子の数

#define MAX 100005
#define NIL -1

struct Node {
    int parent;
    int left_child;
    int right_bro;
};

struct Node T[MAX];

int get_depth(int id) {
    int depth = 0;
    while (T[id].parent != NIL) {//接点の親がNILでない限り
        id = T[id].parent;
    
        depth ++;
    }
    return depth;
}




// n
// id(接点番号) k(子の次数) c_1 c_2 ... c_k
// id k c_0 c_1 ... c_{k-1}


void print_child(int id) {
    int i, c;
    printf("[");
    for (i=0, c=T[id].left_child; c!=NIL; i++, c=T[c].right_bro) {
        if (i) {printf(", ");}// i=0のとき（先頭の子のとき）は「，」を表示しない
        printf("%d", c);
    }
    printf("]\n");
}


void print(int id) {
    printf("node %d: ", id);
    printf("parent = %d, ", T[id].parent);
    printf("depth = %d, ", get_depth(id));
    if (T[id].parent == NIL) {
        printf("root, ");
    } else if (T[id].left_child == NIL) {
        printf("leaf, ");
    } else {
        printf("internal node, ");
    }
    print_child(id);
}



int main(void) {
    int i, n, id, k, j, c;
    int pre_c = NIL;
    scanf("%d", &n);

    // 初期化
    for (i=0; i<n; i++) {
        T[i].parent = T[i].left_child = T[i].right_bro = NIL;
    }

    // 多分あってる
    for (i=0; i<n; i++) {
        scanf("%d", &id);
        scanf("%d", &k); // K:子の次数
        for (j=0; j<k; j++) { 
            scanf("%d", &c); //c_j
            if (j==0) {// 一つ目の子がleft_child
                T[id].left_child = c;
            } else {
                T[pre_c].right_bro = c;
            }
            T[c].parent = id;
            pre_c = c;
        }
    }    

    for (i=0; i<n; i++) {
        print(i);
    }
    return 0;
}
```
### 参考文献

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.