Tree, Binary Tree, Tree traversal

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