[자료구조] 트리

트리

트리는 스택, 큐 등의 선형적인 자료구조가 아니라, 계층적인 구조의 자료구조이다. 컴퓨터의 폴더 구조, 가계도, 회사의 조직도 등 계층적인 관계들을 표현한 자료구조이다.

이 외에도 인공지능에서 사용되는 결정 트리도 트리라고 할 수 있겠다. 트리는 위의 그림과 같이, 1개 이상의 노드로 이루어져 있다.

트리 용어

노드(Node) : 트리를 구성하는 요소들로 그림에서 A, B, C, D, E, F, G, H, I 를 말한다.
루트(Root) 노드 : 트리에서 가장 높은 곳에 있는 노드. 위 그림에서 A가 루트 노드이다.
서브 트리(Subtree) : 루트 노드에서 갈라져 나온 트리.
간선(Edge) : 루트와 서브트리 사이에 연결된 선.
부모 노드(Parent node) : 자식 노드와 직접 연결된 상위 노드. D의 부모 노드는 B, C의 부모 노드는 A이다.
자식 노드(Child node) : 부모 노드와는 반대. D는 B의 자식 노드이다.
단말 노드(Leaf node 또는 Terminal node) : 자식 노드가 없는 노드.
비단말 노드(Nonterminal node) : 단말 노드가 아닌 노드.
차수(Defree) : 한 노드가 가지고 있는 자식 노드의 수. A의 차수는 2이고, C의 차수는 3이다.
트리의 차수 : 트리에서 가장 큰 차수. C의 차수가 3으로 가장 크므로 트리의 차수는 3이다.
레벨(Level) : 트리의 층. 루트의 레벨부터 하나씩 증가해 나간다.
높이(Height) : 트리의 최고 레벨. 층이 총 4층으로 트리의 높이는 4이다.

이진 트리(Binary Tree)

자식 노드의 수가 항상 2개 이하인 트리를 이진 트리라고 한다. 모든 노드는 차수가 2를 넘을 수 없으며, 서브 트리들도 모두 이진 트리여야한다. 이때, 서브 트리가 공집합이어도 된다.

이진 트리는 다음과 같은 성질을 가진다.

노드가 \(n\)개인 이진 트리의 간선의 수는 \(n-1\)개이다.
노드가 \(n\)개인 이진 트리의 높이는 최소 \(log_2(n+1)\), 최대 n이다.
높이가 \(h\)인 이진 트리는 최소 \(h\)개, 최대 \(2^{h}-1\)개의 노드를 가진다.

특히, 높이가 \(k\)이면서 노드가 \(2^{k}-1\)개로 가득 차 있는 트리를 보고 포화 이진 트리(Perfect binary tree)라고 한다. 포화 이진 트리는 정 이진 트리 이면서 완전 이진 트리이기도 하다. 정 이진 트리(Full binary tree)는 모든 노드가 자식 노드를 0개 또는 2개만 가지고 있는 트리이다. 완전 이진 트리(Complete binary tree)는 \(k-1\)레벨 까지는 모든 노드가 채워져 있고, \(k\)레벨 에서는 왼쪽부터 순서대로 노드가 채워져 있는 트리이다.

순회

트리의 각 노드를 한 번씩 방문해서 데이터를 처리하는 것을 순회라고 한다. 트리를 출력하려면 이 또한 순회가 필요하다. 노드를 방문할 때 루트와 왼쪽 서브트리, 오른쪽 서브트리를 방문하는 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나뉜다.

전위 순회(Preorder) : 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
중위 순회(Inorder) : 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
후위 순회(Postorder) : 왼쪽 서브트리 → 오른쪽 서브트리 → 루트

다른 방법으로 레벨 순회(Level order)가 있는데, 레벨 순회는 각 노드를 레벨 순서대로 검사하는 방법이다. 동일 레벨에서는 좌에서 우로 방문하게 된다. 이 과정에서 큐를 이용한다. 처음 큐에는 루트 노드를 삽입하고, 큐에서 노드를 꺼낼 때마다 자식 노드들을 큐에 삽입하면 된다.

[배열] 이진 트리 구현

배열 구현은 완전 이진 트리의 순서대로 노드를 저장하면 된다. 한 노드의 인덱스를 알면 부모, 왼쪽 자식, 오른쪽 자식의 인덱스를 바로 알 수 있다.

한 노드의 인덱스가 n일 때,
노드 n의 부모 노드의 인덱스 = n / 2
노드 n의 왼쪽 자식 노드 = 2n
노드 n의 오른쪽 자식 노드 = 2n + 1

#include <iostream>
#include <cstdlib>

using namespace std;

const int MAX_NODE = 16;

class Array_Tree {
    int tree[MAX_NODE];
    int tsize;
    
    int parent(int i) { return tree[ i / 2 ]; }
    int left(int i) { return tree[i * 2]; }
    int right(int i) { return tree[i * 2 + 1]; }
    
public:
    Array_Tree() { init(); }
    ~Array_Tree() {}
    void init() { tsize = 0; }
    void is_empty() { return tsize == 0; }
    void is_full() { return tsize == MAX_NODE - 1; }
    
    // 노드 삽입
    void insert(int item) {
        if (is_full()) {
            cout << "트리 포화 상태" << endl;
            exit(1);
        }
        tsize++;
        tree[tsize] = item;
    }
    
    /* 삭제, 탐색 */
    
    // 전위 순회
    void preorder(int n = 1) {
        if (is_empty()) {
            cout << "트리 공백 상태" << endl;
            exit(1);
        }
        
        if (n <= tsize) {
            cout << tree[n] << " ";
            preorder(2 * n);
            preorder(2 * n + 1);
        }
    }
    
    // 중위 순회
    void inorder(int n = 1) {
        if (is_empty()) {
            cout << "트리 공백 상태" << endl;
            exit(1);
        }
        
        if (n <= tsize) {
            inorder(2 * n);
            cout << tree[n] << " ";
            inorder(2 * n + 1);
        }
    }
    
    // 후위 순회
    void postorder(int n = 1) {
        if (is_empty()) {
            cout << "트리 공백 상태" << endl;
            exit(1);
        }
        
        if (n <= tsize) {
            postorder(2 * n);
            postorder(2 * n + 1);
            cout << tree[n] << " ";
        }
    }
    
    // 레벨 순회
    void levelorder(int n = 1) {
        if (is_empty()) {
            cout << "트리 공백 상태" << endl;
            exit(1);
        }
        
        for (int i = n; i <= tsize; i++) {
            cout << tree[i] << " ";
        }
    }
    
    // 노드의 수
    int count() { return tsize; }
    
    // 단말 노드의 수
    int count_leaf(int n = 1) { 
        if (tsize <= 1) {
            return 0;
        }
        
        return tsize - 1;
    }
    
    // 트리의 높이
    int count_height() { return (int)ceil(log2(tsize + 1)); }
};

[연결리스트] 이진 트리 구현

아래와 같이 노드 구조체를 선언 해주자.

struct Node {
    int data;
    Node* left; // 왼쪽 자식 노드
    Node* right; // 오른쪽 자식 노드
};

Node 포인터 n이 있다면 n->left는 n의 왼쪽 자식 노드, n->right는 n의 오른쪽 자식 노드가 된다.

#include <iostream>
#include <queue>

using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

class Linked_Tree {
    Node* root;

public:
    Linked_Tree() { root = NULL; } // init()과 동일
    ~Linked_Tree() {}
    bool is_empty() { return root == NULL; }
    void set_root(int item, Node* l, Node* r) { root = create_tree(item, l, r); }
    Node* get_root() { return root; }

    // 노드 삽입
    Node* create_tree(int item, Node* l, Node* r) {
        Node* node = new Node;

        node->data = item;
        node->left = l;
        node->right = r;

        return node;
    }

    // 전위 순회
    void preorder(Node* n) {
        if (n != NULL) {
            cout << n->data << " ";
            preorder(n->left);
            preorder(n->right);
        }
    }

    // 중위 순회
    void inorder(Node* n) {
        if (n != NULL) {
            inorder(n->left);
            cout << n->data << " ";
            inorder(n->right);
        }
    }

    // 후위 순회
    void postorder(Node* n) {
        if (n != NULL) {
            postorder(n->left);
            postorder(n->right);
            cout << n->data << " ";
        }
    }

    // 레벨 순회
    void levelorder(Node* root) {
        Node* n;
        queue<Node*> q;

        if (root != NULL) {
            q.push(root);
            while (!q.empty()) {
                n = q.front();
                q.pop();
                if (n != NULL) {
                    cout << n->data << " ";
                    q.push(n->left);
                    q.push(n->right);
                }
            }
        }
    }

    // 노드의 수
    int count(Node* n) {
        if (n == NULL) {
            return 0;
        }
        else {
            return 1 + count(n->left) + count(n->right); //루트 노드 1개 더해줌
        }
    }
    
    // 단말 노드의 수
    int count_leaf(Node* n) {
        if (n == NULL) {
            return 0;
        }

        if (n->left == NULL && n->right == NULL) {
            return 1;
        }
        else {
            return count(n->left) + count(n->right);
        }
    }

    // 트리의 높이
    int count_height(Node* n) {
        int left, right;

        if (n == NULL) {
            return 0;
        }

        left = count_height(n->left);
        right = count_height(n->right);
        return (left > right) ? left + 1 : right + 1;
    }
};

[+] C++ STL에서 큐를 지원합니다. 저는 이 큐를 사용했지만, 본인이 만든 큐를 이용하셔도 무방합니다.

[+] 이진 탐색 트리

https://ggjjdiary.tistory.com/41

[알고리즘] 이진 탐색 트리

컴퓨터에서 탐색은 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 뜻한다. 레코드는 하나 이상의 필드(field)로 구성된다. 예를 들어, 한 학생의 정보를 구조체로 저장한다면, 구조체

ggjjdiary.tistory.com

[Reference]

http://www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9788970509419&orderClick=LAG&Kc=

자료구조 - 교보문고

컴퓨터로 어떤 문제를 해결하기 위해 필요한 자료들을 효율적으로 관리하고 구조화시키기 위한 학문 '자료구조'. 이 책은 자료구조를 보다 명확하게 배울 수 있도록 구성되어 있다. 각 장에서는

www.kyobobook.co.kr

728x90

저작자표시 비영리 변경금지

'알고리즘(Algorithm) > Data Structure' 카테고리의 다른 글

[자료구조] 그래프 (0)	2022.04.04
[자료구조] 우선순위 큐와 힙 (0)	2022.03.15
[자료구조] 큐 (0)	2022.03.04
[자료구조] 스택 (0)	2022.03.02

꼼지락 IT 공부방

[자료구조] 트리

트리

'알고리즘(Algorithm) > Data Structure' 카테고리의 다른 글

티스토리툴바

[자료구조] 트리

트리

'알고리즘(Algorithm) > Data Structure' 카테고리의 다른 글

'알고리즘(Algorithm)/Data Structure' Related Articles

티스토리툴바