変化しない木の表現

Calendar Clock iconCalendar Clock icon

tree

# 目次

# 木の表現

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

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

２分木のノードは以下のように表現できる.
ノードの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];
};

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

ルートから再帰的に深さを計算していく.
右の子は兄弟なので深さは変わらない.
左の子は子なので深さを+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;
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);

シュン

Github Circle icon

リモートフリーランス。ウェブサービス、スマホアプリエンジニア。
東アジアを拠点に世界を移動しながら活動してます！

お仕事のご依頼・お問い合わせはこちら

コメント