[Data Structures] 챕터7. 트리

선형 vs 비선형 자료구조(Linear/ Non-Linear)

---

선형 자료구조

• 데이터 모두가 연결된 상태로 구현한다(직선으로 표현할 수 있다)
• 리스트(List), 스택(Stack), 큐(Queue)
• 위 자료구조를 배열 또는 연결노드로 구현할 수 있다.

 

비선형 자료구조

• 데이터 모두가 연결되지 않은 상태이다(직선으로 표현할 수 없다)
• 트리(Tree), 그래프(Graph)

 

이진 트리 소개

---

양방향 연결 리스트와 이진 트리 모두 Left와 Right 노드 포인터를 사용하지만 이진 트리는 자식-부모 관계를 다룬다.

 

• Root Node : 트리의 시작점으로 부모가 없다.
• Terminal{Leaf} Node(단말노드): 자식이 없는 노드
• Edge : 노드와 노드의 연결을 가리킨다.
• Degree(차수) : 자식의 개수
• Tree의 차수 : Tree 내에 있는 가장 큰 차수를 가진 노드
• Sub Tree : 모든 노드는 어떤 Sub Tree의 Root이다 (구현할 때 중요)

 

• Level : 루트 레벨을 0 또는 1로 본다.
• Height(높이) : 최고 레벨
• Depth(깊이) : 

 

• Full Binary Tree(포화 이진 트리) : 단말 노드 외 모든 노드의 자식이 꽉 차있는 트리
• Complete Binary Tree(완전 이진 트리) : 단말 노드가 속한 레벨 외에는 모두 꽉 차있고 해당 단말노드의 반대방향은 모두 포화 상태인 트리

(왼) 완전이진트리O (오) 완전이진트리X

 

완전이진트리

 

이진트리 구현

---

using Node = BinaryTree<int>::Node;

Node* n1 = new Node{ 1, nullptr, nullptr }; // 물결괄호 초기값 나열 (생성자 아님)
Node* n2 = new Node{ 2, n1, nullptr };
Node* n3 = new Node{ 3, nullptr, nullptr };
Node* n4 = new Node{ 4, nullptr, nullptr };
Node* n5 = new Node{ 5, nullptr, n4 };
Node* n6 = new Node{ 6, n2, n5 };

n1->right = n3; // <- 연결관계 변경

/*          6
*         /   \
*        2     5
*       /       \
*      1         4
*       \
*        3
*/

BinaryTree<int> tree(n6); // <- n6의 주소를 root node로

 

트리 순회(Tree Traversal methods)

PreOrder

• 현재 노드를 먼저 처리한다.
• 해당 노드에서 작업을 마친 후 왼쪽 자식>오른쪽 자식 순으로 순회

PostOrder

• 현재 노드를 나중에 처리한다.
• 왼쪽 자식>오른쪽 자식으로 순회한 이후 해당 노드에서 작업

InOrder

• 왼쪽 자식을 순회한 이후 자신을 처리한다
• 자신을 처리한 이후 오른쪽 자식을 순회한다.

Level Order

• 높은 레벨부터 처리한다
• 재귀호출 X

PreOrder, PostOrder, InOrder를 Iterative를 활용하여 구현해보자(Queue와 Stack을 활용)

 

Template Intellisense 활용하기

 

 

구현하기

Sum

내풀이

int Sum(Node* node)
{
    int total = node->item;
    if (node->left)
        total += Sum(node->left);

    if (node->right)
        total += Sum(node->right);

    return total;
}

 

추천풀이

int Sum(Node* node)
{
    if (!node) return 0;
    return node->item + Sum(node->left) + Sum(node->right);
}

 

Height

내풀이

int Height(Node* node)
{
    if (node->left || node->right)
    {
        int bigger = 0;
        if (node->left)
            bigger = Height(node->left) + 1;

        if (node->right)
        {
            int right = Height(node->right) + 1;
            bigger = bigger < right ? right : bigger;
        }

        return bigger;
    }

    return 1; // TODO:
}

int Height(Node* node)
{
    if(!node) return 0; // exit condition for recursive call
                        // Because node is null character, return 0
                        // Set -1 if base level is 0
    return std::max(Height(node->left), Height(node->right)) + 1;
}

 

Level Order

void LevelOrder()
{
    Queue<Node*> q;
    Node* current = root_;
    while (current)
    {
        Visit(current);

        if(current->left) q.Enqueue(current->left);
        if(current->right) q.Enqueue(current->right);
        if (q.IsEmpty()) break;

        current = q.Front();
        q.Dequeue();
    }
}

 

IterPreOrder

void IterPreorder()
{
    if (!root_) return;

    Stack<Node*> s;
    s.Push(root_);

    while (!s.IsEmpty())
    {
        Node* current = s.Top();
        s.Pop();

        Visit(current);
        if(current->right)
            s.Push(current->right);
        if (current->left)
            s.Push(current->left);
    }
}

 

IterInOrder

void IterInorder()
{
    if (!root_) return;

    Stack<Node*> s;

    Node* current = root_;
    while (current || !s.IsEmpty())
    {
        while (current) // 1) Creating temporary value is not needed
        {
            s.Push(current);
            current = current->left;
        }

        current = s.Top(); // 2) since a new value is always assigned anyway
        s.Pop();

        Visit(current);
        current = current->right; // assign nullptr if right is empty
    }
}

 

IterPostOrder

void IterPostorder()
{
    if (!root_) return;

    Stack<Node*> s1, s2;

    s1.Push(root_); // Reversed version of IterPreOrder
    while (!s1.IsEmpty())
    {
        Node* current = s1.Top();
        s1.Pop();
        s2.Push(current);

        // Stack Left first. It save right first at s2
        // So reversed version correctly poping out left first.
        if(current->left) s1.Push(current->left);
        if(current->right) s1.Push(current->right);
    }


    while (!s2.IsEmpty())
    {
        Visit(s2.Top());
        s2.Pop();
    }
}

 

수식 계산 트리

---

구현하기

Evaluate

내구현

int Evaluate(Node* node)
{		
    Stack<Node*> s1, s2;
    s1.Push(node);
    while (!s1.IsEmpty())
    {
        Node* current = s1.Top();
        s1.Pop();

        s2.Push(current);

        if(current->left)  s1.Push(current->left);
        if(current->right) s1.Push(current->right);
    }

    Stack<char> save;
    int total = 0;
    while (!s2.IsEmpty())
    {
        char c = s2.Top()->item;
        s2.Pop();

        if ('0' <= c && c <= '9')
            save.Push(c);
        else
        {
            int second = save.Top() - '0';
            save.Pop();

            int first = save.Top() - '0';
            save.Pop();

            if (c == '+') save.Push((first + second) +'0');
            if (c == '-') save.Push((first - second) +'0');
            if (c == '*') save.Push((first * second) +'0');
            if (c == '/') save.Push((first / second) +'0');
        }
    }

    total = save.Top() - '0';
    return total;
}

 

추천구현

int Evaluate(Node* node)
{
    if (!node) return 0;

    if(node->item == '+') return Evaluate(node->left) + Evaluate(node->right);
    if(node->item == '-') return Evaluate(node->left) - Evaluate(node->right);
    if(node->item == '*') return Evaluate(node->left) * Evaluate(node->right);
    if(node->item == '/') return Evaluate(node->left) / Evaluate(node->right);

    return node->item - '0';
}

 

Infix

void Infix(Node* node) {
    if (!node) return;

    if(!IsDigit(node->item)) std::cout << "(";
    Infix(node->left);
    std::cout << node->item;
    Infix(node->right);
    if (!IsDigit(node->item)) std::cout << ")";
}

 

Postfix

void Postfix(Node* node) {
    Stack<Node*> s1, s2;
    s1.Push(node);
    while (!s1.IsEmpty())
    {
        Node* current = s1.Top();
        s1.Pop();

        s2.Push(current);

        if (current->left)  s1.Push(current->left);
        if (current->right) s1.Push(current->right);
    }

    int total = 0;
    while (!s2.IsEmpty())
    {
        Visit(s2.Top());
        s2.Pop();
    }
}

 

ExpressionTree

ExpressionTree(const char* infix)
{
    // Infix -> Postfix (예제 재사용)
    Queue<char> q;
    for (int i = 0; infix[i] != '\0'; i++)
        q.Enqueue(infix[i]);
    cout << "  Infix: ";
    q.Print();
    Queue<char> postfix;
    InfixToPostfix(q, postfix);
    cout << "Postfix: ";
    postfix.Print();

    // Postfix -> Expression tree
    Stack<Node*> s, chars; // use another stack
    while (!postfix.IsEmpty())
    {
        char c = postfix.Front();
        postfix.Dequeue();

        Node* newNode = new Node{ c };
        if (c >= '0' && c <= '9')
            chars.Push(newNode);
        else
        {
            Node* second = chars.Top();
            chars.Pop();
            Node* first = chars.Top();
            chars.Pop();

            newNode->left = first;
            newNode->right = second;

            chars.Push(newNode);
        }
    }

    assert(chars.Size() == 1);
    root_ = chars.Top();
}

 

쓰레드

---

Leaf 노드는 자식이 없다. 이를 활용하여 스택을 사용하지 않고 Iterative In Order를 구현할 수 있다.

Leaf 노드가 다음 노드를 가리키는 링크를 가지고 있을 때 쓰레드(thread)라고 부른다. 이를 구분하기 위한 값을 노드에 추가하였다.

struct Node
{
    T data = T();
    Node* left = nullptr; // Left child
    Node* right = nullptr; // Right child
    int right_thread = 0; // <- right 링크가 쓰레드인지 구분
};

 

Node* Next(Node* node)
{
    Node* next = node->right;

    if (!next) return nullptr; // 종료
    if (next && node->right_thread) return next; // 오른쪽 링크가 쓰레드라면 바로 반환

    while (next->left) next = next->left; // Inorder 예시라서 가장 마지막 left로 이동

    return next; // (left가 없었다면 right 반환) left가 있었다면 가장 마지막 left 반환
}

void Inorder(Node* node)
{
    while (node->left) node = node->left; // Inorder라서 가장 마지막 left로 이동

    do
    {
        cout << node->data << " "; // Visit
        node = Next(node); // 다음 노드를 찾는다
    } while (node);

    cout << endl;
}