tree

変化しない2分木の表現

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

目次

2分木の表現

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

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

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

ノードの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していく.

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 + 1);
    if (NODES{node].left != NIL) setDepth(NODES[node].left, depth + 1);
};

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

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

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

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

1
2
3
4
5
6
7
8
9
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ケースがありえる.

  1. 親がいない場合(ルート)⇢ NIL
  2. 自分が左の子の場合 ⇢ 親の右の子
  3. 自分が右の子の場合 ⇢ 親の左の子
1
2
3
4
5
6
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つの巡回順序がある.

  1. 先行順序(pre-order)
  2. 中間順序(in-order
  3. 後行順序(post-order)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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 << " ";
}