# 目次

# 2分木の表現

各ノードの子の数が２以下であるような木を２分木という.

各ノードを１つの構造体に直接対応させて以下のように表現できる.

左の子: 自分の子のうち一番左の子
右の子: 自分の右の兄弟
親: 自分の親

ノードのIDは配列上のインデックスを表し、ノードが存在しないことは-1で表現する.

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define NIL -1
#define MAX_NODES 100

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

Node NODES[MAX_NODES];

# 木の走査

すべてのノードが配列上に存在するのでただ配列を走査するだけで良い.

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

int NUM_NODES = 100;

for (int i=0; i<NUM_NODES; i++) {
    NODES[i];
};

# 各ノードの深さを計算する

ノードの深さとは、ルートからの辺の数のこと.

ルートから再帰的に深さを計算していく.
子を１つ経るたびに深さを＋１していく.

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

int DEPTH[MAX_NODES];
void setDepth(int node, int depth) {
    DEPTH[node] = depth;
    if (NODES[node].right != NIL) setDepth(NODES[node].right, depth + 1);
    if (NODES{node].left != NIL) setDepth(NODES[node].left, depth + 1);
};

int ROOT_NODE = 0;
setDepth(ROOT_NODE, 0);

# 各ノードの高さを計算する

ノードの高さとは、自分の子孫の葉からの辺の数の最大値.

自分の子左右両方の高さを計算して、高い方を高さとする.
これをルートから葉まで再帰的に計算する.
子を１つ経るごとに高さを＋１していく.

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

int HEIGHT[MAX_NODES];

int height(int n) {
    int left = 0; int right = 0;
    if (NODES[n].left != NIL) left = 1 + height(NODES[n].left);
    if (NODES[n].right != NIL) right = 1 + height(NODES[n].right);
    HEIGHT[n] = (left > right) ? left : right;
    return HEIGHT[n];
}

# 各ノードの兄弟ノードを計算する

兄弟ノードとは、同じ親をもつノード同士のこと.

以下の3ケースがありえる.

親がいない場合（ルート）⇢ NIL
自分が左の子の場合 ⇢ 親の右の子
自分が右の子の場合 ⇢ 親の左の子

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

int sibling(int n) {
  if (NODES[n].parent == NIL) return NIL;
  int p = NODES[n].parent;
  if (NODES[p].left == n) return NODES[p].right;
  return NODES[p].left;
}

# ノードを木の順番に従って巡回する

3つの巡回順序がある.

先行順序(pre-order)
中間順序(in-order
後行順序(post-order)

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

void inorder(int node) {
  if (NODES[node].left != NIL) inorder(NODES[node].left);
  cout << node << " ";
  if (NODES[node].right != NIL) inorder(NODES[node].right);
}

void preorder(int node) {
  cout << node << " ";
  if (NODES[node].left != NIL) preorder(NODES[node].left);
  if (NODES[node].right != NIL) preorder(NODES[node].right);
}

void postorder(int node) {
  if (NODES[node].left != NIL) postorder(NODES[node].left);
  if (NODES[node].right != NIL) postorder(NODES[node].right);
  cout << node << " ";
}

変化しない２分木の表現