陰キャﾊﾟｿｶﾀｵﾀｸ向けクリスマスツリーを標準出力する

![EUH_eMWUwAAgsV4.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/343837/29dc7328-e1aa-464c-f5e4-ee7b458de2ed.jpeg)


こんにちは、日本陰キャ協会 代表補佐(自称)の[xryuseix](https://twitter.com/ryusei_ishika)です。これは「[日本陰キャ協会 Advent Calendar 2022](https://qiita.com/advent-calendar/2022/thar1k_y0u_kirara)」 6日目の記事になります。

**ところで陰キャの皆さん、クリスマスツリーって見たことありますか？？**

いや心の目でとかじゃなくて、画面上じゃなくて、マジなちゃんとしたやつです(🎄←これ)

まあどうせ見たことないと思うので、今回は陰キャﾊﾟｿｶﾀｵﾀｸ向けクリスマスツリーである**二分木**を作っていこうと思います。今回説明するのは二分木の作り方ではなく、きれいに二分木を表示する方法です。

## 用意するもの

* 陰キャオタク1頭
* 強く生きるための精神
* クリスマスの**貴重な貴重な**時間

## 完成図

```txt
           /  中野四葉
       /  エミリア
           \  御坂美琴
   /  中野三玖
       \  中野五月
レム
       / 四宮かぐや
   \  中野二乃
       \  めぐみん
```

(ちなみにこれ何に使えるの?って話をすると、グラフのprintデバッグをしたい時とかにこれをスニペットに登録しとくと便利だったりします。僕は競プロで使ってました。)

## 実装

まずはグラフへの愛と想像力を豊かにしましょう。今回サンプルとして作る二分木はこのようなものです。

```mermaid
graph LR
  88[88]-->2[2]
  2[2]-->6[6]
  6[6]-->24[24]
  6[6]-->54[54]
  2[2]-->8[8]
  88[88]-->4[4]
  4[4]-->10[10]
  4[4]-->11[11]
```

今回は二分木ですが、動的配列とか使うと面倒なので適当な一次元配列で実装していきます。僕はオタクくんに厳しいギャルなのでいちいちソースコードの説明はしません。コメント見てください。

```cpp
int arr_size = 10;
int v[] = {-1, 88, 2, 4, 6, 8, 10, 11, 24, 54}; // 適当な一次元配列

void dfs(int pos, int depth) {
    if ((pos << 1 | 0) < arr_size) { // 枝の上側の処理を再起的に行う
        dfs(pos << 1 | 0, depth + 1);
    }

    printf("%s", string(depth * 3, ' ').c_str()); // 深さ*3個スペース入れて出力を整える
    printf("%3d\n", v[pos]);

    if ((pos << 1 | 1) < arr_size) { // 枝の下側の処理
        dfs(pos << 1 | 1, depth + 1);
    }
}

int main() { dfs(1, 0); }
```

C++の14か17くらいで動かしてください。実行するとこのようになります。

```txt
          24
        6
          54
     2
        8
 88
       10
     4
       11
```

なんかもう少し辺とか入れたいですね。入れるの面倒ですが、斜めの棒だけならコスパよく入ります(他もちょっといじってます)。

```cpp
int arr_size = 10;
int v[] = {-1, 88, 2, 4, 6, 8, 10, 11, 24, 54};

void dfs(int pos = 1, int depth = 0, bool is_right_child = false) {
    if ((pos << 1 | 0) < arr_size) {
        dfs(pos << 1 | 0, depth + 1, true);
    }

    if (depth > 0) {
        printf("%s", string(depth * 3 - 1, ' ').c_str());
        printf("%c", is_right_child ? '/' : '\\');
    }
    printf("%3d\n", v[pos]);

    if ((pos << 1 | 1) < arr_size) {
        dfs(pos << 1 | 1, depth + 1, false);
    }
}

int main() { dfs(); }
```

うーーん、ヨシ！w

なんかクリスマスツリーです。僕もあんまりクリスマスツリーを見に行く機会がないのでが、うろ覚えのクリスマスツリーはこんな感じでした。間違いありません。

```txt
        / 24
     /  6
        \ 54
  /  2
     \  8
 88
     / 10
  \  4
     \ 11
```

そういえばクリスマスツリーには飾りがついていたような気がします。みなさんご存知の通り、数字は飾りではないのでどうにかします。

そういえば美少女アニメキャラってなんか光ってるような気もするし、これを飾りにしましょう。日本陰キャ協会 代表さんは[まんがタイムきらら](http://www.dokidokivisual.com/)が好きそうですが、ここは敢えてきららのキャラは表示しません🤓

一応日本語に対応したり表示が崩れないようにいい感じにします。

```cpp
int arr_size = 10;
// ここから拾ってきたんだけど偏りないか...?
// ヴァイオレット・エヴァーガーデンは長いのでやめた
// https://ranking.net/rankings/best-kawaii-female-anime-characters
string v[] = {"",         "レム",       "中野三玖", "中野二乃", "エミリア",
              "中野五月", "四宮かぐや", "めぐみん", "中野四葉", "御坂美琴"};

// u8len関数（UTF8の文字数をカウントする関数）
// https://qiita.com/t-yama-3/items/7cba573b4cf23322dfc8 をもとに変更
int u8len(string str) {
    int count = 0;  // 文字数のカウント用
    for (int i = 0; i < str.size(); i++) {
        if ((str[i] & 0xc0) != 0x80) count++;
    }
    return count;
}

void dfs(int pos = 1, int depth = 0, bool is_right_child = false) {
    if ((pos << 1 | 0) < arr_size) {
        dfs(pos << 1 | 0, depth + 1, true);
    }

    if (depth > 0) {
        printf("%s", string(depth * 4 - 1, ' ').c_str());
        printf("%c", is_right_child ? '/' : '\\');
        printf("%s", string(6 - u8len(v[pos]), ' ').c_str());
    }
    printf("%s\n", v[pos].c_str());

    if ((pos << 1 | 1) < arr_size) {
        dfs(pos << 1 | 1, depth + 1, false);
    }
}

int main() { dfs(); }
```

ヨシ！w

```txt
           /  中野四葉
       /  エミリア
           \  御坂美琴
   /  中野三玖
       \  中野五月
レム
       / 四宮かぐや
   \  中野二乃
       \  めぐみん
```

## おわりに

そういえば今年はpaiza アドベントカレンダー2022にも参加しています。

https://adventar.org/calendars/8068

paizaはプログラミング学習コンテンツを展開しているのですが、この記事もっとちゃんと書けばpaizaの記事にピッタリだったような気もしなくもないですが、世の中の陰キャくんを助けるためにこのまま公開しようと思います。

### 🎉ハッピーオタクリマス🎄

みんな生きて帰ってこいよ👋