/*
18.12.04
트리 사용법 자연수 아이디를 가지는 트리
S/W referemce 배열을 이용한 트리만 있어 전혀 참조가 불가능함
링크드 리스트를 이용하는 트리에 대해 말씀
아이디를 배열의 인덱스로 이용하여 트리정볼르 구성하려고 함
부모 정보를 저장할 배열
child 정보를 저장할 링크드 리스트임
트리 데이터에서
최상위 노드를 찾는 방법 배열에서 부모가 있는 어떤 노드던지 찾아서
부모를 따라 올라가면 됨
Node를 traversing 하려면 재귀 호출을 이용해서
간단하게 풀이가 가능함
1이하의 모든 node trraversing
traversing_tree(1)
재귀 호출을 이용하는 경우 코드는 간단하지만, 깊이 우선 탐색 되므로
넓이 우선 탐색을 하려면 큐에 저장하는 방법을 사용해야 함
*/
#include <iostream>
using namespace std;
void traversing_tree(int node);
#define MAX_NODE 11
int arr_idx = 0;
struct NODE {
int id; //id 번호
NODE * prev; //싱글 리스트를 위해 추가.
} a[20000];
NODE *myalloc(void)
{
return &a[arr_idx++];
}
int parent_info[MAX_NODE];
NODE *child_info[MAX_NODE];
int main(void)
{
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
arr_idx = 0; //사용할 힙 배열 초기화
for (int i = 0; i < MAX_NODE; i++) //tree 정보 초기화
{
child_info[i] = nullptr;
parent_info[i] = -1;
}
NODE *p;
int parent, child;
int test_case;
cin >> test_case;
//tree 정보 추가
for (int T = 0; T < test_case; T++)
{
cin >> parent >> child; //부모 - 자식간의 연결정보
cout << "Parent " << parent << " child " << child << endl << endl;
parent_info[child] = parent; //부모 정보를 child에 저장
p = myalloc(); //저장할 공간을 alloc 합니다.
p->id = child;
p->prev = child_info[parent]; //parent 의 linked list 에 child 정보를 저장합니다.
child_info[parent] = p;
//추가된 모든 노드 확인
cout << "Tree info" << endl;
for (int tNode = 0; tNode < MAX_NODE; tNode++)
{
cout << "( " << tNode << " )'s parent = " << parent_info[tNode] << " child = ";
for (NODE * pp = child_info[tNode]; pp != nullptr; pp = pp->prev)
{
cout << " " << pp->id;
}
cout << endl;
}
cout << endl << endl;
}
//루트 노드 찾기...
int node;
for (node = MAX_NODE - 1; node >= 0; node--) //부모가 있는 노드 아무거나 검색 (1이 루트라, 일부러 뒤에서 검색)
if (parent_info[node] != -1) break;
cout << "Found any node " << node << endl;
do {
cout << "check " << node << " parent " << parent_info[node] << endl;
node = parent_info[node];
} while (parent_info[node] != -1);
cout << "FOUND ROOT NODE : " << node << endl;
//ROOT 이하의 모든 node traversing
traversing_tree(node);
}
void traversing_tree(int node)
{
cout << node << " ";
for (NODE * pp = child_info[node]; pp != nullptr; pp = pp->prev)
{
traversing_tree(pp->id);
}
}
댓글