Node.h
|
#include<vector> #include<iostream> #pragma once using namespace std;
class Node { private: /* * data: 노드의 값 * level: 트리의 깊이, 처음 트리의 깊이는 1이다 * degree: 노드의 차수 * childNodes: 노드의 자식 노드로 동적 배열로 저장된다 * 이 프로그램에서는 level과 degree는 구현되어있지 않다 */ char data; int level; int degree = 0; vector<Node*> childNodes;
public:
/* * 데이터에 키값을 가진 노드를 생성한다 * level은 기본 1이라 설정한다 */ Node(char key) { data = key; level = 1; } /* * 데이터 설정 */ void setData(char ch) { data = ch; } /* * 데이터 조회 */ char getData() { return data; } /* * 차수 설정 */ void setDegree(int key) { degree = key; } /* * 차수 조회 */ int getDegree() { return degree; } /* * 레벨 설정 */ void setLevel(int key) { level = key; } /* * 레벨 조회 */ int getLevel() { return level; }
/* * 차일드 노드 추가 * 차수는 차일드 노드의 크기로 받는다 */ void addChildNode(Node* node) { childNodes.push_back(node); setDegree(childNodes.size()); cout << "childNodes length: " << childNodes.size() << " Degree: " << getDegree() << endl; }
/* * 차일드 노드 목록 조회 */ vector<Node*> getChildNodes() { return childNodes; } /* * 트리 출력 */ bool printTree(Node* node, int num) { /* * num: 루트 노드의 데이터를 출력하기위해 멘 처음을 실행되는지 확인하기 위한 변수 */ if (num == 0) { cout << getData(); num++; } vector<Node*> childNodes = node->getChildNodes();
/* * 노드에 차일드 노드가 있으면 출력하고 없으면 다른 노드로 간다 */ if (childNodes.size() == 0) return false; if (childNodes.size() > 0) { cout << "( "; for (int i = 0; i < childNodes.size(); i++) { cout << childNodes[i]->getData() << ", "; printTree(childNodes[i], num); } } cout << ") "; return false;
} /* * 차일드 노드 제거 * 노드들을 재귀탐색하며 데이터의 값이 키값과 일치하는지 확인후 제거한다 * 만약 제거할 노드가 서브트리를 같고있을 경우 제거할수 없다는 문구를 출력한다 */ void removeChild(Node* node, char key) { vector<Node*> v = node->getChildNodes();
for (int i = 0; i < v.size(); i++) {
if (v[i]->getData() == key) {
if (v[i]->getDegree() != 0) { cout << "can't erase " << v[i]->getData(); } else { free(v[i]); v.erase(v.begin() + i); node->childNodes = v; } } else { removeChild(v[i], key); } } }
/* * node로 부터 시작하여 해당 Key에 해당하는 데이터 값을 가진 노드를 재귀적으로 찾아 반환한다. */ Node* getNode(Node* node, char key) { vector<Node*> v = node->getChildNodes(); if (v.size() == 0) { return NULL; }
for (int i = 0; i < v.size(); i++) { if (v[i]->getData() == key) { return v[i]; } else { Node* tn = getNode(v[i], key); if (NULL != tn) return tn; } } return NULL; } /* * 차일드 노드들을 출력한다 */ void printChildNodes() { cout << getData() << " : ("; for (int i = 0; i < childNodes.size(); i++) { cout << childNodes[i]->getData() << ", "; } cout << ")"; } }; |
Tree.cpp
|
#include <iostream> #include <vector> #include "Node.h"
using namespace std;
int main() { /* * root노드를 값 A로 생성 */ Node* root = new Node('A');
/* * 서브트리로 B, C, D 추가 */ root->addChildNode(new Node('B')); root->addChildNode(new Node('C')); root->addChildNode(new Node('D'));
/* * A의 자식노드를 출력 */ root->printChildNodes();
cout << endl << endl;
/* * 노드 B를 찾아서 서브트리 E, F 추가 * 노드 B를 찾아서 트리 B를 출력 */ root->getNode(root, 'B')->addChildNode(new Node('E')); root->getNode(root, 'B')->addChildNode(new Node('F')); root->getNode(root, 'B')->printChildNodes(); cout << endl << endl;
/* * 노드 C를 찾아서 서브트리 G 추가 * 노드 C를 찾아서 트리 C를 출력 */ root->getNode(root, 'C')->addChildNode(new Node('G')); root->getNode(root, 'C')->printChildNodes(); cout << endl << endl;
/* * 노드 D를 찾아서 서브트리 H, I, J를 추가 * 노드 D를 찾아서 트리 D를 출력 */ root->getNode(root, 'D')->addChildNode(new Node('H')); root->getNode(root, 'D')->addChildNode(new Node('I')); root->getNode(root, 'D')->addChildNode(new Node('J')); root->getNode(root, 'D')->printChildNodes();
cout << endl << endl; /* * 노드 E를 찾아서 서브트리 K, L 추가 * 노드 E를 찾아서 트리 E를 출력 */ root->getNode(root, 'E')->addChildNode(new Node('L')); root->getNode(root, 'E')->addChildNode(new Node('K')); root->getNode(root, 'E')->printChildNodes(); cout << endl << endl;
/* * 노드 H를 찾아서 서브트리 M 추가 * 노드 H를 찾아서 트리 H를 출력 */ root->getNode(root, 'H')->addChildNode(new Node('M')); root->getNode(root, 'H')->printChildNodes(); cout << endl << endl;
/* * 루트(root)노드인 A의 노드들 나열. */ root->printTree(root, 0); cout << endl;
/* * 트리에서 G 노드를 찾아 제거 */ root->removeChild(root, 'G'); cout << endl;
root->printTree(root, 0); } |
by 송현고등학교 3학년 김준석
트리를 구현하는 여러가지 방식들 중 자식 노드(들)을/를 List 자료구조를 이용하여 구현한 것이다.
자세한 설명은 주석 참조.