[자료구조] 트리 (Tree)
트리 TREE
트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고,
서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 트리에서 최상위 노드를 루트 노드(root node 뿌리 노드[*])라고 한다.
또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다.
자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드[*])라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.
트리 (Tree)
트리 구조란 계층적인 구조를 가지는 자료형태를 말합니다.
노드로 구성된 자료구조이며, 회사의 조직구조 , 계층적인 데이터 저장 등에 사용됩니다.
위에 그림의 경우 루트 노드(트리 구조에서 최상위에 존재하는 노드)는 A이며, 내부 노드(아래로 다른 노드가 연결되어 있는 노드)는 B, C ,D ,E ,H 입니다.
나머지 단말 노드(아래로 다른 노드가 연결되어 있지 않는 노드)는 K,L ,F ,G ,M ,I J 입니다.
트리의 레벨(깊이 , 루트 노드로 부터의 단계)은 4입니다.
일반적으로 트리 구조의 경우 하나의 노드가 여러개의 자식 노드를 가질 수 있습니다.
이진 트리 (Binary Tree)
최대 2개의 자식을 가지는 트리구조를 이진트리라고 합니다.
완전 이진 트리 (Complete Binary Tree)
노드가 위에서 아래로 왼쪽에서 오른쪽 순서대로 모두 채워진 상태를 말합니다.
즉 각 레벨당 비어있는 왼쪽과 오른쪽 노드가 비어있지 않은 상태의 트리구조를 말합니다.
포화 이진 트리 (Full Binary Tree)
모든 레벨이 꽉 차있는 상태를 말합니다.
즉, 노드를 추가하려면 레벨이 증가가 필요한 상태를 말합니다.
[코드 구현]
#include <iostream>
using namespace std;
class Node
{
public :
int data;
Node* left;
Node* right;
Node()
: data(-1), left(nullptr), right(nullptr) {}
};
class Tree
{
private :
Node* root;
Node* FindNode(int _data)
{
Node* node = root;
while (node != nullptr)
{
if (node->data < _data)
{
node = node->left;
}
else if (node->data > _data)
{
node = node->right;
}
else
{
break;
}
}
return node;
}
public :
Tree() : root(nullptr) {}
void Insert(int _data)
{
Node* node = new Node();
node->data = _data;
if (root != nullptr)
{
Node* target = root;
bool Isinsert = false;
while (!Isinsert)
{
if (target->data > _data) // 데이터가 크면 왼쪽으로 정렬
{
if (target->left != nullptr)
{
target = target->left;
}
else
{
target->left = node;
Isinsert = true;
}
}
else if (target->data < _data) // 데이터가 작으면 오른쪽으로 정렬
{
if (target->right != nullptr)
{
target = target->right;
}
else
{
target->right = node;
Isinsert = true;
}
}
else // 예외처리 (ex. 같은 숫자의 경우)
{
Isinsert = true;
cout << "Insert Fail !" << endl;
delete node;
node = nullptr;
}
}
}
else // root 가 비어있을 경우
{
root = node;
}
}
void Delete(int _data)
{
Node* node = root;
Node* parentNode = nullptr;
while (node != nullptr)
{
if (node->data > _data) // 데이터가 작으면 왼쪽으로 찾는다.
{
parentNode = node;
node = node->left;
}
else if (node->data < _data) // 데이터가 크면 오른쪽으로 찾는다.
{
parentNode = node;
node = node->right;
}
else // 찾았을 경우 (같은 숫자 확인)
{
//노드를 삭제한 후 삭제한 노드의 자식중 하나가 들어갈 위치를 결정
Node** target = nullptr;
if (node != root) // root일 경우 삭제하지 않는다.
{
// 삭제할 노드가 부모 노드의 왼쪽인지 오른쪽인지를 확인한다.
if (parentNode->data > _data)
{
target = &(parentNode->left);
}
else
{
target = &(parentNode->right);
}
}
else
{
target = &(root);
}
//삭제할 노드의 자식들 처리부분
if (node->left == nullptr && node->right == nullptr)
{
(*target) = nullptr;
}
else if (node->left != nullptr && node->right == nullptr)
{
(*target) = node->left;
}
else if (node->left == nullptr && node->right != nullptr)
{
(*target) = node->right;
}
else
{
(*target) = node->left;
Node* childNode = node->left;
while (childNode->right != nullptr)
{
childNode = childNode->right;
}
childNode->right = node->right;
}
//실제로 삭제
delete node;
node = nullptr;
}
}
}
void Print()
{
cout << "Tree Print------------------------" << endl;
Print(root);
cout << "\n----------------------------------\n" << endl;
}
void Print(Node* node)
{
if (node)
{
Print(node->left);
cout << node->data << " ";
Print(node->right);
}
}
};
int main()
{
Tree tree;
tree.Insert(10);
tree.Insert(5);
tree.Insert(20);
tree.Insert(6);
tree.Insert(15);
tree.Print();
tree.Delete(5);
tree.Print();
// -- 결과
//Tree Print------------------------
//5 6 10 15 20
//----------------------------------
//Tree Print------------------------
//6 10 15 20
//----------------------------------
return 0;
}