c++ / Binary Tree, Traversal

Tree란..?

---

트리는 자료구조의 한 종류이며, 트리의 각 요소를 노드라고 부른다.각 노드는 데이터를 저장하며 다음 노드를 연결한다.

---

트리 용어들

 

루트 노드(root node) : 부모가 없는 노드. 트리는 하나의 루트 노드만을 가진다.
단말 노드(leaf node) : 자식이 없는 노드이다.
내부(internal) 노드 : 리프 노드가 아닌 노드.
링크(link) : 노드를 연결하는 선 (edge, branch 라고도 부름).
형제(sibling) : 같은 부모를 가지는 노드.
노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수.
노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수.
노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수(degree) : 부(하위) 트리 갯수/간선수 (degree) = 각 노드가 지닌 가지의 수
트리의 차수(degree of tree) : 트리의 최대 차수
트리의 높이(height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이

---

Binary Tree, Traversal

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

pair<char, char> node[26];

void Preorder(char now) 
{
    if (now == '.')
        return;

    cout << now;
    Preorder(node[now - 'A'].first);
    Preorder(node[now - 'A'].second);
}

void Inorder(char now) 
{
    if (now == '.')
        return;

    Inorder(node[now - 'A'].first);
    cout << now;
    Inorder(node[now - 'A'].second);
}

void Postorder(char now) 
{
    if (now == '.')
        return;

    Postorder(node[now - 'A'].first);
    Postorder(node[now - 'A'].second);
    cout << now;
}

int main() 
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) 
    {
        char parent, left, right;
        cin >> parent >> left >> right;

        node[parent - 'A'].first = left;
        node[parent - 'A'].second = right;
    }
    Preorder('A');
    cout << "\n";
    Inorder('A');
    cout << "\n";
    Postorder('A');
}

 

Binary Tree

이진 트리에서 각 노드는 최대 2개의 자식을 가진다.
각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지가 지정된다.

Traversal


PreOrder (전위탐색) : root - left child - right child
InOrder (중위탐색): left child - root - right child
PostOrder (후위탐색): left child - right child - root

ex) 위 코드에서 

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .
를 입력하게 되면 

PreOrder: ABDCEFG
InOrder: DBAECFG
PostOrder: DBEGFCA

순회의 방법에 따라 위와같이 결과가 나온다

끝