8장 - 트리

지금껏 살펴본 자료구조들은 선형 자료구조였다.

파일 디렉토리처럼 계층적인 자료를 나타낼 때는 트리라는 자료구조를 사용한다.

트리는 노드라는 데이터 단위들이 수직으로 연결되어 있는 형태다.

 

트리 용어 정리

노드, 루트, 서브트리, 간선, 부모노드, 자식노드, 단말노드,레벨는 기본적으로 알고 있을 것이다.

차수(Degree)란 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다.

트리의 차수는 차수 중 최대값이다.

트리의 높이는 트리의 최대 레벨을 의미한다. 레벨 h는 log2(n+1)보다 크고 n보다 작다.

차수가 동적이면 표현하기 복잡하니 노드들의 차수가 모두 2인 트리인 이진트리만 다루도록 하자.

(이진트리의 단말 노드도 차수가 2이다.)

 

이진트리란?

1. 공집합이거나

2. 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한집합으로 정의된다.

서브트리들은 모두 이진트리여야한다.

 

이진트리는 이렇게 재귀적으로 정의된다. 말로 설명하기 위해 Bottom up 방식으로 생각해보자.

이진트리의 단말노드(Leaf)는 이진트리다.

단말 노드의 자식은 공집합이므로 단말 노드의 서브트리는 이진트리이다.(1번)따라서 단말 노드 또한 이진트리이다.

등비급수의 합을 생각해보면 레벨 h인 이진트리의 최대 노드 개수는 log2(n+1)임을 알 수 있다.

최대는 일렬로 늘어선 경우이므로 n이다. 일렬로 늘어섰는데 왜 이진트리냐 하면 1번때문이다.

 

이진트리의 종류

포화 이진트리 (Full Binary Tree) : 레벨 h인 트리에서 모든 노드들이 꽉 찬 이진트리이다. 노드의 개수는 2^h-1이다.

완전 이진트리(Complete Binary Tree) : 용어가 포화랑 좀 헷갈릴만한데, 완전 이진트리란 레벨 h에서 h-1까지는 포화이고 마지막 레벨에선 노드들이 왼쪽부터 차있는 이진 트리다. 노드 개수가 n개인 완전 이진트리는 유일하므로 써먹기 좋다.

포화이진트리는 완전이진트리이기도 하다.

 

이진트리의 배열 표현

이진트리 i의 부모는 i/2, 왼쪽 자식은 2i, 오른쪽 자식은 2i+1이다.

왜 그런지는 이진트리의 성질과 관련하여 생각해보면 된다.

 

이진트리의 링크 표현

데이터와 자신과 연결된 다른 데이터를 가리키는 포인터를 가지는 객체를 트리의 구성 단위로 생각한다.

이 구성 단위를 노드라고 한다.

노드 클래스는 다음과 같다. 중위순회(Inorder)를 노드 클래스 내에서 구현했다.

순회 하면서 노드에 맞는 동작을 Action이라는 인터페이스를 상속받는 객체로 감쌌다.

class BinaryNode{
private:
    int _data;
    BinaryNode * _Lnode;
    BinaryNode * _Rnode;
    Action * _action;
public:
    BinaryNode(int data, BinaryNode * Lnode = nullptr, BinaryNode * Rnode = nullptr)
    :_data(data), _Lnode(Lnode), _Rnode(Rnode){
    }
    int getData () const {
        return _data;
    }
    BinaryNode * getLnode() const {
        return _Lnode;
    }
    BinaryNode * getRnode() const {
        return _Rnode;
    }
    void setAction(Action * action){
        _action = action;
    }
    Action * getAction() const {
        return _action;
    }
    bool isLeaf(){
        return (_Lnode == nullptr) && (_Rnode == nullptr);
    }

    void inorder(){
        if(_Lnode != nullptr){
            _Lnode -> inorder();
        }
        if(_action != nullptr){
            _action -> execute(_data);
        }
        if(_Rnode != nullptr){
            _Rnode -> inorder();
        }
    }
    void SetActionPostorder(Action * action){
        if(_Lnode != nullptr){
            _Lnode -> SetActionPostorder(action);
        }
        if(_Rnode != nullptr){
            _Rnode -> SetActionPostorder(action);
        }
        _action = action;
    }

};

 

Action과 이를 상속받는 PrintAction은 다음과 같다.

class Action{
public:
    virtual ~Action(){}
    virtual void execute(int x){}
    virtual void execute(Action * pre_action, Action * post_action){}

};


class PrintAction : public Action{
public:
    virtual void execute(int x){
        std::cout << x << std::endl;
    }
};

class PrintTwiceAction : public Action{
public:
    virtual void execute(int x){
        std::cout << x*2 << std::endl;
    }
};

 

Root 를 저장하는 BinaryTree 클래스는 다음과 같다.

setTreeAction은 트리 내 노드들의 액션을 세팅한다. 액션을 바꿔주는 역할을 한다.

class BinaryTree{
private:
    BinaryNode * _root;
public:
    BinaryTree(BinaryNode * root)
    :_root(root){
    }
    void setTreeAction(Action * action){
        _root -> SetActionPostorder(action);
    }
    void inorder(){
        _root-> inorder();
    }
};

마지막으로 main 함수는 다음과 같다.

int main(){
    using namespace std;

    
    BinaryNode b3(3);
    BinaryNode b2(2);
    BinaryNode b1(1, &b2, &b3);

    PrintAction * pa = new PrintAction();
    PrintTwiceAction * pa2 = new PrintTwiceAction();

    BinaryTree bt(&b1);
    bt.setTreeAction(pa2);
    bt.inorder();

    delete pa;
    delete pa2;

    return 0;
}