tree

変化しない木の表現

変化しない木の表現
Feb. 2, 2020, 1:51 p.m.

目次

木の表現

ノードの子の数に制限がない場合でも、すべてのノードが左右2つの子を持ちうる2分木として表現できる.

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

2分木のノードは以下のように表現できる.
ノードのIDは配列上のインデックスを表し、ノードが存在しないことは-1で表現する.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#define NIL -1
#define MAX_NODES 100

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

Node NODES[MAX_NODES];

木の走査

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

1
2
3
4
5
int NUM_NODES = 100;

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

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

ルートから再帰的に深さを計算していく.
右の子は兄弟なので深さは変わらない.
左の子は子なので深さを+1する.

1
2
3
4
5
6
7
8
9
int DEPTH[MAX_NODES];
void setDepth(int node, int depth) {
    DEPTH[node] = depth;
    if (NODES[node].right != NIL) setDepth(NODES[node].right, depth);
    if (NODES{node].left != NIL) setDepth(NODES[node].left, depth + 1);
};

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