반응형

1. 트리란?


트리 개념

http://www.crocus.co.kr/331

http://www.crocus.co.kr/332



트리의 정의


1. 들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다. 이를 루트(root) 노드라고 부른다. 

2. 루트 노드를 제외한 모든 노드는 반드시 단 하나의 들어오는 간선이 존재한다. 

3. 루트에서 다른 노드로 가는 경로는 반드시 가능하며, 유일하다. 이는 루트를 제외한 모든 노드에 성립해야 한다. 

https://www.acmicpc.net/problem/6416



이진 트리 개념

http://www.crocus.co.kr/339




배열을 이용한 이진 트리

http://www.crocus.co.kr/552


사실 트리는 포인터로 잘 구현하지 않고 vector라는 표준 템플릿 라이브러리(STL: Standard Template Library)를 이용하면 쉽게 제작 할 수 있다.


이는 추후에 vector를 배우고 좀 더 생각해보자.


우선 포인터를 이용한 간단한 이진 트리를 및 이진 트리 순회를 만들어보자.




이진 트리 순회

http://www.crocus.co.kr/348





2. 이진 트리 소스 코드( + 순회)



위의 그림에서 전위 순회가 어떻게 동작하는지 생각해보자.




전위순회(Preorder Traversal)


0출력 후 왼쪽 자식으로 간다 -> 1출력 후 왼쪽 자식으로 간다 -> 3출력 후 왼쪽 자식으로 간다 ->


3의 왼쪽 자식이 없으니 return -> 3의 오른쪽 자식이 없으니 return -> 1의 오른쪽 자식으로 간다 ->


4출력 후 왼쪽 자식으로 간다 -> 4의 왼쪽 자식이 없으니 return -> 4의 오른쪽 자식으로 간다 ->


4의 오른쪽 자식이 없으니 return -> 이제 0의 오른쪽 자식으로 간다 -> 2출력 후 왼쪽 자식으로 간다 ->


5출력 후 왼쪽 자식으로 간다-> 5의 왼쪽 자식이 없으니 return -> 5의 오른쪽 자식으로 간다 -> 6출력 후 왼쪽 자식으로 간다 ->


6의 왼쪽 자식이 없으니 return -> 6의 오른쪽 자식이 없으니 return -> 2의 오른쪽 자식이 없으니 return




(( 아래 코드에서 함수 오버로딩 알고가기 ))


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <cstdio>
 
using namespace std;
 
class NODE {
    friend class TREE;
private:
    int data;
    NODE *left;
    NODE *right;
};
 
class TREE {
private:
    NODE *root;
public:
    TREE() {
        root = new NODE;
        root->data = 0;
        root->left = root->right = NULL;
    }
    ~TREE() {}
    void make_node(NODE *node, int val) {
        node->data = val;
        node->left = node->right = NULL;
    }
    void make_left(NODE *child) {
        root->left = child;
    }
    void make_left(NODE *parent, NODE *child) {
        parent->left = child;
    }
    void make_right(NODE *parent, NODE *child) {
        parent->right = child;
    }
    void make_right(NODE *child) {
        root->right = child;
    }
 
    NODE* getRoot() {
        return root;
    }
    void preorder(NODE *pos) {
        if (pos == NULL)
            return;
 
        cout << pos->data << " ";
        preorder(pos->left);
        preorder(pos->right);
    }
 
    void inorder(NODE *pos) {
        if (pos == NULL)
            return;
 
        inorder(pos->left);
        cout << pos->data << " ";
        inorder(pos->right);
    }
 
    void postorder(NODE *pos) {
        if (pos == NULL)
            return;
 
        postorder(pos->left);
        postorder(pos->right);
        cout << pos->data << " ";
    }
};
 
int main() 
{
    TREE tree;
 
    NODE *node1 = new NODE;
    tree.make_node(node1, 1);
    NODE *node2 = new NODE;
    tree.make_node(node2, 2);
    NODE *node3 = new NODE;
    tree.make_node(node3, 3);
    NODE *node4 = new NODE;
    tree.make_node(node4, 4);
    NODE *node5 = new NODE;
    tree.make_node(node5, 5);
    NODE *node6 = new NODE;
    tree.make_node(node6, 6);
 
    tree.make_left(node1);
    tree.make_right(node2);
    tree.make_left(node1, node3);
    tree.make_right(node1, node4);
    tree.make_left(node2, node5);
    tree.make_right(node5, node6);
 
    cout << "Preorder :: ";
    tree.preorder(tree.getRoot());
    cout << endl;
    cout << "Inorder :: ";
    tree.inorder(tree.getRoot());
    cout << endl;
    cout << "Postorder :: ";
    tree.postorder(tree.getRoot());
    cout << endl;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus






반응형

'Tutoring > Data Structure' 카테고리의 다른 글

튜터링 연습문제 1주차  (0) 2018.03.21
hash  (0) 2018.03.04
heap  (0) 2018.03.04
Stack, Queue, Deque  (0) 2018.03.01
Double Linked List  (0) 2018.02.28