[자료구조] 6. 트리(Tree)

트리

트리는 계층 구조를 가진 모델입니다. 트리는 노드로 이루어져 있으며 이들 노드 간에는 부모-자식 관계가 존재합니다.

트리 예시

트리가 트리라고 불리는 이유는 마치 나무의 가지가 뻗어나가는것과 같은 형태를 보이기 때문입니다. 다만 나무가 위로 뻗어나는것과 달리 트리는 위의 부모노드에서 아래의 자식노드로 뻗어나가는 특징을 가지고 있습니다. 그렇기에 각 트리의 노드는 하나의 부모만을 가지지만, 자식으로는 여러 노드를 가질 수 있습니다.

용어

루트 노드(Root): 부모가 없는 노드로 트리에 하나만 존재한다. 예시에서는 1.

Internal node: 적어도 하나의 자식을 가지는 노드. 예시에서는 1, 2, 3, 5.

External node: 자식을 가지지 않는 노드. 예시에서는 4, 6, 7.

Ancestors of node: 자신~루트까지에 포함되는 노드들. 자기 자신을 포함한다. 즉 예시에서 7의 조상은 7, 5, 2, 1.

노드의 깊이(Depth of a node): 자기부터 루트까지의 경로간의 간선의 개수. 예시에서 7의 깊이는 3.

노드의 높이(Height of a node): 노드를 루트로 하는 트리(서브트리)에 포함된 노드의 깊이중 가장 큰것. 예시에서 가장 깊은 노드7의 깊이는 3으로, 트리의 높이도 3.

서브트리(Subtree): 트리의 자식트리. 트리는 재귀적이기 때문에 트리의 자식 부분을 분리해도 트리의 형태를 가진다.

순회

리스트를 탐색한다면 기본적으로 일차원적으로 순서대로 탐색하는것을 떠올릴 수 있습니다. 그러나 트리는 여러 계층으로 나뉘는 자료구조이기에 트리를 탐색할때는 여러 방법론을 생각해볼 필요가 있습니다. 이에 2가지의 순회 방법을 소개합니다.

이때 아래 전위 순회와 후위 순회는 모두 DFS의 성격을 가집니다.

전위 순회(Pre-order traversal)

자기 자신을 먼저 방문하고 자식 노드를 방문하는 방식입니다.

즉 위의 트리 예시를 기준으로 1 -> 2 -> 5 -> 7 -> 3 -> 6 -> 4 순으로 방문합니다.

후위 순회(Post-order traversal)

자식 노드를 모두 방문한 후 자신을 방문하는 방식입니다.

즉 위의 트리 예시를 기준으로 7 -> 5 -> 2 -> 6 -> 3 -> 4 -> 1 순으로 방문합니다.

활용

트리는 이진 트리의 기반이되며 힙, 이진탐색트리 등의 심화적인 자료구조의 기반이 됩니다.

구현

C++로 구현한 트리의 예시 코드입니다.

노드별로 자식 노드를 저장하기 위한 벡터와, 트리 자체에도 트리에 속하는 모든 노드를 저장하기 위한 벡터가 존재하는 방식입니다.

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int data;
    Node *parent;
    vector<Node *> childList;
    Node(int data, Node *parent) {
        this->data = data;
        this->parent = parent;
    }
};

class Tree {
  private:
    Node *root;
    vector<Node *> nodeList;
    int _find(int data, vector<Node *> list) {
        for (int i = 0; i < list.size(); i++)
            if (list[i]->data == data)
                return i;
        return -1;
    }

  public:
    Tree(int data) {
        root = new Node(data, NULL);
        nodeList.push_back(root);
    }
    ~Tree() {
        for (int i = 0; i < nodeList.size(); i++) {
            delete nodeList[i];
        }
    }
    bool insertNode(int parData, int data) {
        if (_find(data, nodeList) != -1)
            return false;

        int idx = _find(parData, nodeList);
        if (idx == -1)
            return false;

        Node *parNode = nodeList[idx];
        Node *newNode = new Node(data, parNode);
        parNode->childList.push_back(newNode);
        nodeList.push_back(newNode);
        return true;
    }
    bool deleteNode(int data) {
        int idx = _find(data, nodeList);
        if (idx == -1)
            return false;

        Node *delNode = nodeList[idx];
        if (delNode == root)
            return false;

        Node *parNode = delNode->parent;
        for (int i = 0; i < delNode->childList.size(); i++) {
            parNode->childList.push_back(delNode->childList[i]);
            delNode->childList[i]->parent = parNode;
        }

        vector<Node *> &child = parNode->childList;
        child.erase(child.begin() + _find(data, child));
        nodeList.erase(nodeList.begin() + idx);
        delete delNode;

        return true;
    }
    bool printParent(int data) {
        int idx = _find(data, nodeList);
        if (idx <= 0)
            return false;

        Node *curNode = nodeList[idx];
        cout << curNode->parent->data << endl;

        return true;
    }
    bool printChildren(int data) {
        int idx = _find(data, nodeList);
        if (idx == -1)
            return false;

        vector<Node *> &child = nodeList[idx]->childList;
        if (child.empty())
            return false;

        cout << child[0]->data;
        for (int i = 1; i < child.size(); i++) {
            cout << " " << child[i]->data;
        }
        cout << endl;
        return true;
    }
};