[자료구조] Trees

Trees : 컴퓨터 과학에서 계층구조를 나타내는 추상적인 모델, 노드간의 상속관계를 나타냄

 * Ancestors(조상)와 Descendant(후손)는 자기자신을 포함해서 기술을 하기도 하고 아니기도 함

• Root : 부모가 없는 노드 ( 최상위 노드)
• Internal Node : 자식이 하나라도 있는 노드
• External Node : 자식이 없는 노드 (leaps)
• 노드의 깊이 : 자기 자신을 제외한 조상들의 갯수
• 트리의 높이 : 임의의 노드의 깊이 최대값 
• 노드의 높이 : 해당 노드가 root인 subtree의 높이

 

• Generic method
  • int size()
  • bool empty()

 

• Accessor method : 접근 함수
  • positon root() : root의 위치 주소 반환
  • list<position>positions(): 각 node의 주소 list로 저장

 

• Position-based method : 위치 기반 함수
  • position parent() : 해당노드의 부모의 주소 반환
  • list<position>children() : 자식들 (순서를 지켜서)선형적으로 저장

 

• Query method
  • bool isRoot() : 노드가 root인지 판단
  • bool isExternal() : 노드가 external node인지 판단

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class node{
public:
    int data;
    node* par;
    vector<node*> child;
    node(int e, node* nod){
        data = e;
        par = nod;
    }
};
class tree{
public:
    node* root;
    vector<node*> nodelist;
    tree(int data){
        root = new node(data, nullptr);
        root->data = data;
        nodelist.push_back(root);
    }
    int find(int x,vector<node*>&list){
        for(int i=0;i<list.size();i++){
            if(x==list[i]->data){
                return i;
            }
        }
        return -1;
    }
    void Parent(int x){
        int idx = find(x,nodelist);
        if(idx==-1||nodelist[idx]==root){cout<<-1<<endl;}
        else{
            cout<<nodelist[idx]->par->data<<endl;
        }
    }
    void Insert(int x, int y){
        int idx = find(x,nodelist);
        if(idx==-1){cout<<-1<<endl;}
        else{
            node* X = nodelist[idx];
            node* Y = new node(y,X);
            X->child.push_back(Y);
            nodelist.push_back(Y);
        }
    }
    void Delete(int x){
        int idx = find(x,nodelist);
        if(idx==-1){cout<<-1<<endl;}
        else{
            node* delNode = nodelist[idx];
            if(delNode == root){
                return;
            }
            node* parNode = delNode->par;
            for(int i=0; i<delNode->child.size();i++){
                parNode->child.push_back(delNode->child[i]);
                delNode->child[i]->par = parNode;
            }
            int xI = find(delNode->data,parNode->child);
            parNode->child.erase(xI + parNode->child.begin());
            nodelist.erase(idx+nodelist.begin());
        }
    }
    void child(int x){
        int idx = find(x,nodelist);
        if(idx==-1){cout<<-1<<endl;}
        else{
            node* X = nodelist[idx];
            if(X->child.size()==0){cout<<-1<<endl; return;}
            for(int i=0; i<X->child.size();i++){
                cout<<X->child[i]->data<<" ";
            }cout<<endl;
        }
    }
    void maxChild(int x){
        int idx = find(x,nodelist);
        if(idx==-1){cout<<-1<<endl;}
        else{
            node* X = nodelist[idx];
            if(X->child.size()==0){cout<<-1<<endl; return;}
            int Max = 0;
            for(int i=0; i<X->child.size();i++){
                if(Max<X->child[i]->data){
                    Max = X->child[i]->data;
                }
            }cout<<Max<<endl;
        }
    }
};
int main(){
    int t;
    cin>>t;
    tree* T = new tree(1);
    while(t--){
        string cmd;
        cin>>cmd;
        if(cmd == "insert"){
            int x,y;
            cin>>x>>y;
            T->Insert(x,y);
        }else if(cmd=="delete"){
            int x;
            cin>>x;
            T->Delete(x);
        }else if(cmd=="parent"){
            int x;
            cin>>x;
            T->Parent(x);
        }else if(cmd=="child"){
            int x;
            cin>>x;
            T->child(x);
        }else if(cmd=="maxChild"){
            int x;
            cin>>x;
            T->maxChild(x);
        }
    }
}

 

이진트리(Binary trees) : 자식의 수가 최대2인 트리 left child, right child라고 함

정 이진 트리(proper binary tree) : 자식의 수가 무조건 2인 이진트리

완전 이진 트리(complete binary tree) :
            부모 → 왼쪽자식 → 오른쪽자식 순으로 저장되는 이진트리, 마지막 레벨을 제외하고는 모든 레벨이 가득 채워져 있어야한다.

포화 이진 트리(Perfect binary tree) : 모든 외부노드의 레벨이 동일하고, 모든 내부노드의 자식이 2인 이진트리

 

Traversal (순회) : root 부터 각 노드를 차례로 탐색

• 전위 순회 : 부모노드부터 탐색 후 자식노드 탐색
• 후위 순회 : 자식노드부터 탐색 후 부모노드 탐색
• 중위 순회 : 왼쪽 자식 탐색 -> 부모 노드 탐색 -> 자식 노드 탐색

void preOrder(Node* curNode) {//전위 순회
        int n = curNode->childList.size();
        if (curNode == root) {
            cout << "0 ";
        }
        else {
            cout << curNode->depth << " ";
        }
        for (int i = 0; i < n; i++) {
             preOrder(curNode->childList[i]);
        }
    }