Chapter 10. 트리(Tree)

Def) 트리(Tree)

  계층적인 구조를 나타내는 자료구조.
  보통 Root가 위, Branch와 Leaf이 아래로 자라는 형태로 표현.

Def) 노드(Node, Vertex)
  트리의 데이터를 저장하는 원소 단위. 정점.

Def) 엣지(Edge, Link)

  노드와 노드를 연결하는 선. 간선
  트리의 엣지는 부모-자식 계층 관계만을 나타냄.
  즉, 엣지의 위에 있는 것이 부모, 아래가 자식.
  노드의 개수가 N이면 항상 N - 1개의 엣지가 존재
  즉, 두 개의 노드를 연결하는 엣지는 항상 유일함.

Note) 트리 관련 용어
  트리를 제대로 이해하기 위해선, 관련 용어 숙지가 필수.

루트(Root)	트리의 최상단 노드
부모 - 자식 관계(Parent - Child)	엣지로 연결되어 있는 두 노드의 상대적 관계 루트의 경우, 부모 노드가 없음. 자식 노드는 임의의 개수를 가질 수 있음.
리프(Leaf, Terminal/External Node)	자식 노드가 없는 노드
내부 노드(Internal Node)	자식 노드가 한 개 이상 있는 노드
형제 관계(Sibling)	부모가 같은 노드들
조상 - 후손 관계(Ancestor - Descendant)	자신을 기준으로 엣지의 위에 있는 모든 노드를 조상 노드, 아래에 있는 모든 노드를 자식 노드
차수(Degree)	자식 노드의 갯수
레벨(Level)	루트의 층으로부터 얼마나 먼가
높이(Height)	루트부터 시작해서 가장 먼 리프까지의 레벨 즉, 가장 큰 레벨값 + 1
서브트리(Subtree)	특정 노드 기준, 해당 노드의 후손들로만 이루어진 트리 부트리, 부분트리

 

Def) Binary Tree
  모든 노드가 최대 두 개의 자식을 갖는 트리
  다시 말해, 모든 노드의 차수가 2 이하인 트리
  또는, 모든 노드가 2개의 서브트리를 가지고 있는 트리
  이때 서브트리는 빈 트리 일 수 있음.

  각각의 자식 노드는 부모의 왼쪽 자식(Left Child) 또는
  오른쪽 자식(Right Child)으로 지정됨.

Note) Binary Tree에서 자식의 순서
  이진 트리는 자식의 순서를 구분하기 때문에,
  자식의 순서가 서로 뒤바뀐 트리는 서로 다른 이진 트리임.

Def) 정 이진 트리(Proper Binary Tree, Full Binary Tree)
  모든 노드가 0개 또는 2개의 자식 노드를 갖는 이진 트리
  즉, 리프를 제외한 노드들은 모두  자식이 2개인 이진 트리

Def) 포화 이진 트리(Perfect Binary Tree)
  모든 레벨에서 노드가 모두 채워져 있는 이진 트리
  높이가 h이면 노드 개수가 2*h - 1

Def) 완전 이진 트리(Complete Binary Tree)
  마지막 레벨을 제외한 모든 레벨에는 노드가 완전히 채워져 있고,
  마지막 레벨에는 노드가 왼쪽부터 채워져 있는 이진 트리.

Def) 균형 이진 트리(Balanced Binary Tree)
  모든 노드의 서브 트리 간의 높이 차이가 1 이하

Def) 편향 트리(Skewed Tree)
  리프를 제외한 모든 노트가 하나의 자식 노드만 갖는 트리
  여러 가지 알고리즘 적용 시, 비효율적인 트리의 일례.
  따라서, 균형 이진 트리로 변환하는 경우가 많음.

Note) 이진 트리 구현 방법
  - 배열을 이용한 방법
    보통의 경우에는 비효율적임.
    그러나 완전 이진 트리의 경우, 효율적으로 표현 가능.

  - 연결 리스트
    저장할 데이터와 왼쪽 자식과 오른쪽 자식 노드를 가리키는
    포인터 2개를 갖는 구조체를 사용.

Ex) 이진 트리 구현

#include <iostream>

using namespace std;

class Node {
public:
    int		m_nData;
    Node*	m_pLeft;
    Node*	m_pRight;

    Node(int _nData)
        : m_nData(m_nData)
        , m_pLeft(nullptr)
        , m_pRight(nullptr)
    {}

};

int main(void)
{
    Node* pRootNode = new Node('A');
    pRootNode->m_pLeft = new Node('B');
    pRootNode->m_pRight = new Node('C');
    pRootNode->m_pLeft->m_pLeft = new Node('D');
    pRootNode->m_pLeft->m_pRight = new Node('E');
    pRootNode->m_pRight->m_pLeft = new Node('F');
    
    // free() has not been called intentionally.

    return 0;
}

 

Def) 트리 순회(Tree Traversal)
  정해진 순서에 의해 트리의 모든 노드를 (한 번씩) 방문하는 작업.

Note) 전형적인 트리 순회 방법
  현재 노드를 전/중/후에 방문 함에 따라 이름이 다르게 불림.

전위 순회(Preorder Traversal)	깊이 우선 탐색(Depth First Traversal)
중위 순회(Inorder Traversal)
후위 순회(Postorder Traversal)
레벨 순서 순회(Levelorder Traversal)	너비 우선 탐색(Breadth First Traversal)

 

Def) 전위 순회(Preorder Traversal)

  현재 노드(상위 노드) -> 왼쪽 서브트리 -> 오른쪽 서브트리

 

Def) 중위 순회(Inorder Traversal)

  왼쪽 서브트리 -> 현재 노드(상위 노드) -> 오른쪽 서브트리

 

Def) 전위 순회(Preorder Traversal)

  현재 노드(상위 노드) -> 왼쪽 서브트리 -> 오른쪽 서브트리

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <assert.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALID_INDEX = -1,
    MAX_COUNT = 10001
};

typedef struct Node {
    int		        nData;
    struct Node*    pLeft;
    struct Node*    pRight;
} Node_t;

void preorder(Node* _pNode);
void inorder(Node* _pNode);
void postorder(Node* _pNode);

int main(void)
{
    size_t i, len;
    Node_t tree[MAX_COUNT] = { 0, };
    char input[MAX_COUNT] = { 0, };

    scanf("%s", input);
    len = strlen(input);
    for (i = 1; i <= len; ++i)
    {
        tree[i].nData = input[i - 1];
        tree[i].pLeft = NULL;
        tree[i].pRight = NULL;
    }

    for (i = 2; i <= len; ++i)
    {
        if (i % 2 == 0)
        {
            tree[i / 2].pLeft = &tree[i];
        }
        else
        {
            tree[i / 2].pRight = &tree[i];
        }
    }

    preorder(&tree[1]);
    printf("\n");
    inorder(&tree[1]);
    printf("\n");
    postorder(&tree[1]);

    return 0;
}

...

 

Note) LCA와 노드 간의 거리

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <assert.h>

enum {
    ...
};

typedef struct Node {
    ...
} Node_t;

void preorder(Node* _pNode);
void inorder(Node* _pNode);
void postorder(Node* _pNode);

int LCA(int _nNode1, int _nNode2)
{
    int res1 = _nNode1 / 2;
    int res2 = _nNode2 / 2;

    if (res1 == 0 || (_nNode1 < _nNode2 && 3 <= _nNode2 - _nNode1))
        res1 = _nNode1;
    if (res2 == 0 || (_nNode2 < _nNode1 && 3 <= _nNode1 - _nNode2))
        res2 = _nNode2;

    return res1 == res2 ? res1 : LCA(res1, res2);
}

int distance(int a, int b)
{
    if (a == b)
        return 0;
    if (a > b)
        return distance(a / 2, b) + 1;
    if (a < b)
        return distance(a, b / 2) + 1;
}

int main(void)
{
    size_t i, len;
    Node_t tree[MAX_COUNT] = { 0, };
    char input[MAX_COUNT] = { 0, };

    scanf("%s", input);
    len = strlen(input);
    for (i = 1; i <= len; ++i)
    {
        tree[i].nData = input[i - 1];
        tree[i].pLeft = NULL;
        tree[i].pRight = NULL;
    }

    for (i = 2; i <= len; ++i)
    {
        if (i % 2 == 0)
        {
            tree[i / 2].pLeft = &tree[i];
        }
        else
        {
            tree[i / 2].pRight = &tree[i];
        }
    }

    preorder(&tree[1]);
    printf("\n");
    inorder(&tree[1]);
    printf("\n");
    postorder(&tree[1]);

    printf("\n");
    printf("3번 노드와 4번 노드의 LCA:    %d\n", LCA(3, 4));
    printf("3번 노드와 4번 노드 간의 거리: %d\n", distance(3, 4));

    return 0;
}

...

 

Def) 레벨 순서 순회(Levelorder Traversal)

  낮은 레벨에 있는 노드를 모두 방문한 후,
  큰 레벨로 이동하여 방문을 반복
  위 세 가지 순회와 다르게, 서로 연결되어 있지 않은 노드를 순회함.
  큐를 사용하여 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <assert.h>

enum {
    ...
};

typedef struct Node {
    ...
} Node_t;

void preorder(Node* _pNode);
void inorder(Node* _pNode);
void postorder(Node* _pNode);
int LCA(int _nNode1, int _nNode2);
int distance(int a, int b);

typedef struct queue {
    struct Node* nArray[MAX_COUNT];
    size_t       uCount;
    size_t       uFront;
    size_t       uRear;
} queue_t;

void enqueue(queue_t* _pQueue, Node_t* _pNode);
int isEmpty(queue_t* _pQueue);
Node_t* dequeue(queue_t* _pQueue);
Node_t* front(queue_t* _pQueue);
Node_t* rear(queue_t* _pQueue);
void print(queue_t* _pQueue);

void levelorder(Node_t* _pNode)
{
    queue_t q = {0,};
    enqueue(&q, _pNode);

    while (FALSE == isEmpty(&q))
    {
        Node_t* pCurrentNode = front(&q);
        dequeue(&q);

        printf("%c ", pCurrentNode->nData);
        if (pCurrentNode->pLeft) enqueue(&q, pCurrentNode->pLeft);
        if (pCurrentNode->pRight) enqueue(&q, pCurrentNode->pRight);
    }
}

int main(void)
{
    size_t i, len;
    Node_t tree[MAX_COUNT] = { 0, };
    char input[MAX_COUNT] = { 0, };

    scanf("%s", input);
    len = strlen(input);
    for (i = 1; i <= len; ++i)
    {
        tree[i].nData = input[i - 1];
        tree[i].pLeft = NULL;
        tree[i].pRight = NULL;
    }

    for (i = 2; i <= len; ++i)
    {
        if (i % 2 == 0)
        {
            tree[i / 2].pLeft = &tree[i];
        }
        else
        {
            tree[i / 2].pRight = &tree[i];
        }
    }

    preorder(&tree[1]);
    printf("\n");
    inorder(&tree[1]);
    printf("\n");
    postorder(&tree[1]);

    printf("\n");
    printf("3번 노드와 4번 노드의 LCA:    %d\n", LCA(3, 4));
    printf("3번 노드와 4번 노드 간의 거리: %d\n", distance(3, 4));

    levelorder(&tree[1]);

    return 0;
}

...

 

Note) 만약 동적할당을 통해서 트리를 구성한다면?
  free()를 해주어야 함. 이 경우 후위 순회 함수를 토대로 쉽게 짤 수 있음.

 

 

BST 구현 With 동적 할당

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALID_INDEX = -1,
    MAX_COUNT = 10001
};

typedef struct Node {
    int		        nData;
    struct Node*    pLeft;
    struct Node*    pRight;
} Node_t;

void preorder(Node_t* _pNode);
void inorder(Node_t* _pNode);
void postorder(Node_t* _pNode);
int LCA(int _nNodeData1, int _nNodeData2);
int distance(int _nNodeData1, int _nNodeData2);

void insertRecursively(Node_t* _pCurrentNode, int _nData);

void insertBST(Node_t* _pRootNode, int _nData)
{
    // 루트 노드가 없으면 삽입을 아에 멈춰야함.
    // 루트 노드의 자손 노드들은 존재 하지 않을 경우 그 자리에 삽입됨.
    // 따라서 삽입용 재귀 함수가 따로 필요함.
    assert(NULL != _pRootNode);

    insertRecursively(_pRootNode, _nData);
}

void insertRecursively(Node_t* _pCurrentNode, int _nData)
{
    if (_nData < _pCurrentNode->nData)
    {
        if (NULL == _pCurrentNode->pLeft)
        {
            _pCurrentNode->pLeft = (Node_t*)malloc(sizeof(Node_t));
            _pCurrentNode->pLeft->nData = _nData;
            _pCurrentNode->pLeft->pLeft = NULL;
            _pCurrentNode->pLeft->pRight = NULL;
        }
        else
        {
            insertRecursively(_pCurrentNode->pLeft, _nData);
        }
    }
    else
    {
        if (NULL == _pCurrentNode->pRight)
        {
            _pCurrentNode->pRight = (Node_t*)malloc(sizeof(Node_t));
            _pCurrentNode->pRight->nData = _nData;
            _pCurrentNode->pRight->pLeft = NULL;
            _pCurrentNode->pRight->pRight = NULL;
        }
        else
        {
            insertRecursively(_pCurrentNode->pRight, _nData);
        }
    }
}

int main(void)
{
    size_t i, uLen;
    int nInput;
    Node_t* pRoot = (Node_t*)malloc(sizeof(Node_t));
    pRoot->nData = 1;
    pRoot->pLeft = NULL;
    pRoot->pRight = NULL;

    scanf("%zu", &uLen);
    for (i = 0; i < uLen; ++i)
    {
        scanf("%d", &nInput);
        insertBST(pRoot, nInput);
    }

    inorder(pRoot);

    return 0;
}

void preorder(Node* _pNode)
{
    if (NULL != _pNode)
    {
        printf("%d ", _pNode->nData);
        preorder(_pNode->pLeft);
        preorder(_pNode->pRight);
    }
}
void inorder(Node* _pNode)
{
    if (NULL != _pNode)
    {
        inorder(_pNode->pLeft);
        printf("%d ", _pNode->nData);
        inorder(_pNode->pRight);
    }

}
void postorder(Node* _pNode)
{
    if (NULL != _pNode)
    {
        postorder(_pNode->pLeft);
        postorder(_pNode->pRight);
        printf("%d ", _pNode->nData);
    }
}
int LCA(int _nData1, int _nData2)
{
    int nRes1 = _nData1 / 2;
    int nRes2 = _nData2 / 2;

    if (nRes1 == 0 || (_nData1 < _nData2 && 3 <= _nData2 - _nData1))
    {
        nRes1 = _nData1;
    }
    if (nRes2 == 0 || (_nData2 < _nData1 && 3 <= _nData1 - _nData2))
    {
        nRes2 = _nData2;
    }

    return nRes1 == nRes2 ? nRes1 : LCA(nRes1, nRes2);
}
int distance(int _nData1, int _nData2)
{
    if (_nData1 == _nData2)
    {
        return 0;
    }
    if (_nData1 < _nData2)
    {
        return distance(_nData1, _nData2 / 2) + 1;
    }
    else
    {
        return distance(_nData1 / 2, _nData2) + 1;
    }

}