2.実施木

メモリプールと接続リストを使用して、各ノードIDが自然数のツリーを実現します.
入力した親と子の接続情報は最大10,000個と仮定します.

[接続リストメモリプールの割り当て]

#define MAX_POOL 10000

int memPoolCnt;

struct ListNode {
int id;
	ListNode* prev;
} listPool[MAX_POOL];// 메모리 풀 할당

最悪の場合、1つのノードに9999個までのサブノードがあるため、接続リストノードに上記のメモリプールが割り当てられます.

[ツリー構造]

#define MAX_NODE 10000

struct TreeNode {
int parent;
	ListNode* child;// 가장 최근에 추가된 자식 노드를 가리키는 포인터
} treeNode[MAX_NODE];

ツリー内の各ノード情報を含むTreeNode構造.
現在実装されているツリーには、親と子の情報のみが格納されますが、必要に応じて構造体に他の変数を宣言することもできます.

[init関数]

void init() {
	memPoolCnt = 0;
for (registerint i = 0; i < MAX_NODE; i++) {// tree 정보 초기화
		treeNode[i].parent = -1;
		treeNode[i].child =nullptr;
	}
}

ツリー情報を初期化するための関数です.

[ノードを挿入]

int parent, child;
cin >> parent >> child;// 부모-자식 연결정보 입력받음

treeNode[child].parent = parent;// child 노드에서 부모 ID 저장

ListNode* node = &listPool[memPoolCnt++];// 메모리 풀로부터 공간 할당받음
node ->id = child;
node ->prev = treeNode[parent].child;// parent 노드의 child 리스트에 연결
treeNode[parent].child = node;// parent 노드의 마지막 child 갱신

[参照ルート]

int findRoot(int n) {
while (treeNode[n].parent != -1)
		n = treeNode[n].parent;
return n;
}

特定のノード上のRoot(最上位ノード)を検索する方法.
親ノード-1の前に(つまり、自分がトップレベルの親であることを見つける前に)、親に乗ることができます.

[ブラウズツリー]

void traverse(int cur) {
	cout << cur << " ";
for (ListNode* l = treeNode[cur].child; l !=nullptr; l = l->prev)
		traverse(l->id);
}

再帰呼び出しを使用すればよい.
このメソッドを使用してツリーを実装する必要はありません.自分のスタイルに合ったツリーを構築し、問題の要求に応じて適用する練習をします.