#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];
///////////////////////////////////////
extern void init_hash(void);
extern int getid_hash(char *name);
///////////////////////////////////////
extern void init_table(void);
extern int getid_table(char *name);
///////////////////////////////////////
int main(void)
{
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
init_table(); //get ID 용 초기화
init_hash();
arr_idx = 0; //사용할 힙 배열 초기화
for (int i = 0; i < MAX_NODE; i++) //tree 정보 초기화
{
child_info[i] = nullptr;
parent_info[i] = -1;
}
NODE *p;
char pname[7], cname[7];
int parent, child;
int test_case;
cin >> test_case;
//tree 정보 추가
for (int T = 0; T < test_case; T++)
{
cin >> pname >> cname; //부모 - 자식간의 연결정보
parent = getid_hash(pname);
child = getid_hash(cname);
cout << "Parent " << pname << "( " << parent << ") child " << cname << " ( " << 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);
}
}
댓글