Binary Tree & Traversal [c++]

선형 자료구조 : queue, stack, array 등

비선형 자료구조 : binary tree 등

 

이진트리는 트리 자료구조를 활용해 데이터 탐색 속도 증진을 위해 사용하는 구조이다.

완전 이진트리인 경우 힙정렬(Heap sort)를 이용해 배열을 사용해도 괜찮았지만,

완전 이진트리가 아닌 경우에는 데이터의 낭비를 줄이기 위

해 포인터를 사용하는 것이 좋음.

 

이진트리에 사용되는 자료구조에 따라 각 탐색, 삽입, 삭제의 시간 복잡도는 아래와 같다.

 

 

이진트리에서 데이터를 참색하는 방법은 크게 3가지가 있다.

 

Ⅰ. 전위순회(Preorder Traversal)

(1) 자기 자신을 처리

(2) 왼쪽 자식을 처리

(3) 오른쪽 자식을 처리

 

Ⅱ. 중위순회(Inorder Traversal)

(1) 왼쪽 자식을 처리

(2) 자기 자신을 처리

(3) 오른쪽 자식을 처리

 

- cf) 이진탐색트리(Binary Search Tree)에서 중위 순회를 하면 데이터 값이 오름차순으로 정렬됨

BST란

1. 이진트리이면서

2. 각 노드에 하나의 키를 저장하고

3. 각 노드 V에 대해서 V의 왼쪽 서브트리에 있는 key들은 V.key 보다 작거나 같고

 오른쪽 서브트리에 있는 key들은 V.key 보다 크거나 같다. 

 

Ⅲ. 후위순회(Postorder Traversal)

(1) 왼쪽 자식을 처리

(2) 오른쪽쪽 자식을 처리

(3) 자기 자신을 처리

- cf) 컴퓨터가 연산을 하기 좋은 방식

 

ex)

 

임시 이진 트리

전위 순회 : 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15

중위 순회 : 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15

후위 순회 : 8 9 4 10 11 5 2 12 13 6 14 15 7 3 1

 

#include <iostream>
#include <stdlib.h>

using namespace std;

typedef struct node* pointer;
typedef struct node {
int data;
pointer left, right;
} node;

void preorder(pointer ptr) {
if(ptr) { // ptr이 NULL이 아니라면
cout << ptr->data << ' ';
preorder(ptr->left);
preorder(ptr->right);
}
}

void inorder(pointer ptr) {
if (ptr) { // ptr이 NULL이 아니라면
preorder(ptr->left);
cout << ptr->data << ' ';
preorder(ptr->right);
}
}

void postorder(pointer ptr) {
if (ptr) { // ptr이 NULL이 아니라면
preorder(ptr->left);
preorder(ptr->right);
cout << ptr->data << ' ';
}
}


int main() {
const int n = 4;

node nodes[n+1];
for (int i = 1; i < n + 1; i++) {  // 각 노드에 data값 입력 및 child 초기화
nodes[i].data = i;
nodes[i].left = NULL;
nodes[i].right = NULL;
}

for (int i = 1; i < n + 1; i++) {
if (i % 2 == 0) {
nodes[i / 2].left = &nodes[i];
}
else {
nodes[i / 2].right = &nodes[i];
}
}

preorder(&nodes[1]);

return 0;
}