[DATASTRUCTURE] Binary Tree & Binary Search Tree

+) 출처 : https://blog.weirdx.io/post/3656

이진 트리

이진 트리(binary tree)는 한 노드가 최대 2개의 자식 노드를 가지는 트리를 말하며 첫 번째 노드는 부모(parent), 자식 노드는 왼쪽(left), 오른쪽(right)라고 불립니다.

• 루트 이진 트리(rooted binary tree)는 모든 노드의 자식이 최대 2개인 루트를 가진 트리입니다.
• 포화 이진 트리(full binary tree)는 모든 노드가 2개의 자식 노드를 가지며 모든 레벨이 꽉 찬 트리입니다.
• 완전 이진 트리(complete binary tree)는 포화 이진 트리같이 모든 레벨이 꽉 찬 트리는 아니지만 모든 노드가 2개의 자식 노드를 가지는 트리입니다.

+) 출처 : http://3dmpengines.tistory.com/423

순회를 판단하는 기준 : Root를 언제 방문하는가!

1. 전위 순회 (Root -> Left -> Right)

2. 중위 순회 (Left -> Root -> Right)

3. 후위 순회 (Left -> Right -> Root)

출처: http://anster.tistory.com/153 [Old Lisper]

이진 탐색 트리 

1. 각 노드에 값이 존재 
2. 값이 중복된 노드가 없음 
3. 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값들을 지닌 노드로 구성 
4. 반대로 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값들을 지닌 노드로 구성 
5. 좌우의 서브트리는 다시 각각 이진 탐색트리여야 함 


이진 탐색트리는 평균적으로 원소의 탐색, 삽입, 삭제에 있어서 O(logn) 의 성능을 보장합니다. 

최악의 경우에는, 그러니까 한쪽으로만 치우친 트리에서는 O(n) 의 성능이 나옵니다. 재

미있는 사실은, 힙소트처럼, 이진탐색트리도 정렬 알고리즘으로 사용할 수 있다는 점인데요.

이 경우 평균적으로는 O(nlogn) 의 성능을, 최악의 경우에는 O(n^2) 의 성능을 보입니다. 

=> binary search tree를 이용 : 삽입,삭제,전위,중위,후위 순회를 구현

tree.h

#pragma once #include <iostream> #include <fstream> using namespace std; #define Array_Binary_Tree_Count 200 #define NO_DATA -1 #define ROOT_INDEX 0 #define ROOT_UNAVAILABLE 0 #define ROOT_AVAILABLE 1 #define IS_ROOT_UNAVAILABLE Root_Flag == ROOT_UNAVAILABLE int Binary_Tree[Array_Binary_Tree_Count]; int Root_Flag = ROOT_UNAVAILABLE; void Initialize(); int Parent_Index(int index); int Left_Child_Index(int index); int Right_Child_Index(int index); int Parent_Data(int index); int Left_Child_Data(int index); int Right_Child_Data(int index); void Command(); void Show_Search(int Present_Index); void Insert(int Data); int Search(int Data); void Delete(int Data); void Change_Child_In_Delete(int Delete_Index, int Change_Index); void Preorder(int Present_Index); void Postorder(int Present_Index); void Inorder(int Present_Index);

function.h

#pragma once #include "tree.h" int Square(int Data) { int result = 1; for (int i = 0; i < Data; i++) result *= 2; return result; } void Show_Tree() { int Square_Count = 0, Tree_Count = 0; for (int i = 0; i < Array_Binary_Tree_Count; i++) { cout << Binary_Tree[i] << " "; Tree_Count++; if (Tree_Count == Square(Square_Count)) { Square_Count++; Tree_Count = 0; cout << "\n"; } } } void Initialize() { for (int i = 0; i < Array_Binary_Tree_Count; i++) { Binary_Tree[i] = NO_DATA; } fstream fcin_input; fcin_input.open("input.txt"); while (!fcin_input.eof()) { int Data; fcin_input >> Data; Insert(Data); } } int Parent_Index(int index) { return(index - 1) / 2; } int Left_Child_Index(int index) { return (2 * index) + 1; } int Right_Child_Index(int index) { return (2 * index) + 2; } int Parent_Data(int index) { return Binary_Tree[Parent_Index(index)]; } int Left_Child_Data(int index) { return Binary_Tree[Left_Child_Index(index)]; } int Right_Child_Data(int index) { return Binary_Tree[Right_Child_Index(index)]; } void Command() { Initialize(); int Command, Data; while (1) { cout << "1. 삽입 2. 삭제 3. 탐색 4. Sorting 5. Show\n"; cin >> Command; switch (Command) { case 1: cout << "입력할 Data를 입력하세요 \n"; cin >> Data; Insert(Data); Show_Tree(); system("pause"); system("cls"); break; case 2: cout << "삭제할 Data를 입력하세요 \n"; cin >> Data; Delete(Data); Show_Tree(); system("pause"); system("cls"); break; case 3: cout << "찾을 Data를 입력하세요 \n"; cin >> Data; Show_Search(Search(Data)); Show_Tree(); system("pause"); system("cls"); break; case 4: cout << "1. Inorder Traversal 2. Preorder Traversal 3. Postorder Traversal\n"; cin >> Data; if (Data == 1) Inorder(ROOT_INDEX); if (Data == 2) Preorder(ROOT_INDEX); if (Data == 3) Postorder(ROOT_INDEX); cout << "\n"; system("pause"); system("cls"); break; case 5: Show_Tree(); system("pause"); system("cls"); break; } } } void Show_Search(int Present_Index) { cout << "Present_Data : " << Binary_Tree[Present_Index] << endl; cout << "Parent_Data : " << Parent_Data(Present_Index) << endl; cout << "Left_Child_Data : " << Left_Child_Data(Present_Index) << endl; cout << "Right_Child_Data : " << Right_Child_Data(Present_Index) << endl; } void Insert(int Data) { int Present_Index = ROOT_INDEX; if (IS_ROOT_UNAVAILABLE) { Binary_Tree[ROOT_INDEX] = Data; Root_Flag = ROOT_AVAILABLE; } else { while (1) { if (Binary_Tree[Present_Index] == NO_DATA) { Binary_Tree[Present_Index] = Data; break; } if (Binary_Tree[Present_Index] < Data) { Present_Index = Right_Child_Index(Present_Index); continue; } if (Binary_Tree[Present_Index] > Data) { Present_Index = Left_Child_Index(Present_Index); continue; } if (Binary_Tree[Present_Index] == Data) { cout << Data << "를 삽입할 수 없음 \n"; cout << "같은 데이터가 index : " << Present_Index << " 에 존재합니다.\n"; break; } } } } int Search(int Data) { int Present_Index = ROOT_INDEX; int While_Count = 0; while (1) { While_Count++; if (While_Count > Array_Binary_Tree_Count) break; if (Binary_Tree[Present_Index] == Data) { return Present_Index; } else { if (Binary_Tree[Present_Index] > Data) { Present_Index = Left_Child_Index(Present_Index); continue; } if (Binary_Tree[Present_Index] < Data) { Present_Index = Right_Child_Index(Present_Index); continue; } } } } void Delete(int Data) { int Present_Index = Search(Data); int Data_Left_Child = Left_Child_Data(Present_Index); int Data_Right_Child = Right_Child_Data(Present_Index); if (Data_Left_Child == NO_DATA && Data_Right_Child == NO_DATA) { Binary_Tree[Present_Index] = NO_DATA; } else if (Data_Left_Child != NO_DATA && Data_Right_Child != NO_DATA) { int Before_Left_Index = 0; int Left_Index = Right_Child_Index(Present_Index); Before_Left_Index = Left_Index; while (Binary_Tree[Left_Index] != NO_DATA) { Before_Left_Index = Left_Index; Left_Index = Left_Child_Index(Left_Index); } Binary_Tree[Present_Index] = Binary_Tree[Before_Left_Index]; if (Left_Child_Data(Before_Left_Index) != NO_DATA || Right_Child_Data(Before_Left_Index) != NO_DATA) { Change_Child_In_Delete(Before_Left_Index, Right_Child_Index(Before_Left_Index)); } else { Binary_Tree[Present_Index] = Binary_Tree[Before_Left_Index]; Binary_Tree[Before_Left_Index] = NO_DATA; } } else { if (Data_Left_Child != NO_DATA) { Binary_Tree[Present_Index] = NO_DATA; Change_Child_In_Delete(Present_Index, Left_Child_Index(Present_Index)); } else { Binary_Tree[Present_Index] = NO_DATA; Change_Child_In_Delete(Present_Index, Right_Child_Index(Present_Index)); } } } void Change_Child_In_Delete(int Delete_Index, int Change_Index) { if (Binary_Tree[Change_Index] != NO_DATA) { Binary_Tree[Delete_Index] = Binary_Tree[Change_Index]; Binary_Tree[Left_Child_Index(Delete_Index)] = Binary_Tree[Left_Child_Index(Change_Index)]; Binary_Tree[Right_Child_Index(Delete_Index)] = Binary_Tree[Right_Child_Index(Change_Index)]; Change_Child_In_Delete(Left_Child_Index(Delete_Index), Left_Child_Index(Change_Index)); Change_Child_In_Delete(Right_Child_Index(Delete_Index), Right_Child_Index(Change_Index)); } } void Preorder(int Present_Index) { if (Binary_Tree[Present_Index] != NO_DATA) { cout << Binary_Tree[Present_Index] << " "; Preorder(Left_Child_Index(Present_Index)); Preorder(Right_Child_Index(Present_Index)); } } void Postorder(int Present_Index) { if (Binary_Tree[Present_Index] != NO_DATA) { Postorder(Left_Child_Index(Present_Index)); Postorder(Right_Child_Index(Present_Index)); cout << Binary_Tree[Present_Index] << " "; } } void Inorder(int Present_Index) { if (Binary_Tree[Present_Index] != NO_DATA) { Inorder(Left_Child_Index(Present_Index)); cout << Binary_Tree[Present_Index] << " "; Inorder(Right_Child_Index(Present_Index)); } }

Binary_Tree.cpp

#include "function.h" int main() { Command(); }