Tree (based vector) 실습

※ vector 개념

- vector<자료형> myVector;  : 선헌한다

- myVector.push_back(new data);  : 새로운 값을 vector에 추가한다

- myVector.size(); : vector의 자료개수를 반환한다

- myVector[i]; : vector의 i번째 자료를 반환한다

- myVector.begin() : vector의 시작위치를 반환한다

- myVector.erase(myVector.begin()+i);  : i번째 자료를 제거한다

 

 

1. class Node

- int data : 값을 저장

- Node* par : 부모 노드를 가리키는 포인터

- vector<Node*> child_vector : 자식들의 노드를 저장하는 벡터

 

2. Node : setParent(Node* parent)

- 부모 노드를 설정한다

- this->par = parent로 설정한다

 

3. Node : insertChild(Node* child)

- 자식 노드를 추가한다

- this->child_vector.push_back(chile) 로 추가한다

 

4. Node : delChild(Node* child)

- 자식 노드 중에서 해당하는 Node를 삭제한다

- for i=0부터 child_vector.size() 전까지 반복하며 child를 찾는다

- 만약 child_vector[i] == child 인 경우

- child_vector.erase(child_vector.begin()+i) 명령어를 통해 i번째에 해당되는 노드를 제거한다

 

 

5. class Tree

- Node* root : 최상단 노드를 저장한다

- vector<Node*> tree : 트리의 모든노드를 저장한다

 

6. Tree : void insertNode(par, data)

- par에 해당되는 Node의 자식에 노드를 새로 추가한다

- for i=0부터 size()까지 반복하며 증가시킨다

- 만약 tree[i]->data 값이 par와 동일하다면 i번째 노드가 parent 노드이다

- 새로운 노드 v를 생성하여 data 값을 넣는다

- v의 parent를 tree[i]로 지정한다

- tree[i]의 insertChild(v)로 자식노드에 추가한다

- tree.push_back(v)로 tree 전체 벡터 또한 추가한다

 

7. Tree : delNode(int data)

- data에 해당되는 노드를 삭제한다

- for i=0부터 size()까지 i를 증감시킨다

- tree[i]->data 가 data와 일치하는 경우 tree[i]가 해당 노드이다

- 만약 root 노드인 경우 실행하지 않고 반환한다

- tree[i] 노드를 nownode로 임시 저장한다

- tree[i]의 부모노드를 parent로 임시 저장한다

- for(Node*& child : nownode->child_vector) 통해 child_vector의 모든 노드들을 반복하며 접근한다

- parent->insertChild(child)를 통해 삭제 될 노드의 자식들을 삭제될 노드의 부모노드의 자식으로 옮긴다

- parent->delChild(nownode)를 통해 해당 노드를 삭제한다

- tree.erase(tree.begin()+i)를 통해 tree 전체 vector 에서도 해당 노드를 삭제한다

- delete nownode를 통해 임시저장한 노드도 삭제한다

 

8. Tree : printChild(int data) : 자식들 출력

- data에 해당되는 노드의 자식들의 값을 출력한다

- for i=0부터 size()까지 반복문을 돌리며 i를 증감시킨다

- tree[i]->data == data 인 경우 tree[i]가 해당 노드이다

- 만약 tree[i]의 자식이 없는경우 0을 출력 후 반환한다

- for j=0부터 tree[i]->child_vector.size() 까지 증감시킨다

- 각각 tree[i]->child_vector[j]->data를 출력한다

- 출력이 종료된 후 반환한다

 

9. Tree : printSib(int data) : 같은 level 노드 출력

- data에 해당되는 노드의 부모의 자식을을 출력한다

- for i=0부터 size()까지 반복하여 증감시킨다

- tree[i]->data == data인 경우 tree[i]가 해당 노드이다

- 만약 tree[i]->parent가 NULL인 root 노드인경우 data 출력후 반환한다

- parent로 tree[i]->parent를 임시저장한다

- for j=0부터 parent->child_vector.size()까지 증감시킨다

- 각각 parent->child_vector[j]->data를 출격한다

- 출력이 종료된 후 반환한다