/*
5.1절에 나온 내용을 토대로 매우 허술한 트리를 작성해보았습니다
*/
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
class Tree;
class TreeNode
{
private:
TreeNode *left; //왼쪽
int data;
TreeNode *right; //오른쪽
public:
TreeNode(int temp) :left(NULL), data(temp), right(NULL)
{
}
int Data()
{
return data;
}
friend class Tree;
};
class Tree
{
public:
Tree()
{
}
void Insert(TreeNode **root, int temp)
{
if (*root == 0)
*root = new TreeNode(temp); //루트가 비었다면 루트부터 채우고
else
{
if (temp < (*root)->data) //root의 데이터보다 작으면 왼쪽
{
Insert(&(*root)->left, temp);
}
else if (temp > (*root)->data)
{
Insert(&(*root)->right, temp);
}
else
{
cout << "같은 데이터는 입력 불가능" << endl;
return;
}
}
}
void Search(TreeNode **root, int temp)
{
if ((*root) == NULL)
{
return;
}
if ((*root)->data==temp)
{
cout << temp << "는 존재합니다" << endl;
return;
}
else //왼쪽 오른쪽 다 찾아본다
{
Search(&(*root)->left, temp);
Search(&(*root)->right, temp);
}
}
void InorderTraversal(TreeNode *root)
{
if (root != NULL)
{
InorderTraversal(root->left);
cout << root->data << "->";
InorderTraversal(root->right);
}
}
};
int main(void)
{
TreeNode *root=NULL;
Tree intTree;
srand((unsigned)time(NULL));
for (int i = 0; i < 10; i++)
{
int data = (int)(rand() % 100 + 1);
intTree.Insert(&root, data);
cout << data << "입력" << endl;
}
cout << "트리 출력(루트 노드 " << root->Data() << ")" << endl;
intTree.InorderTraversal(root);
cout << endl;
cout << "트리에 5라는 데이터가 있는가?(존재하지 않는다면 빈칸)" << endl;
intTree.Search(&root, 5);
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*이진트리를 허접하게 구현해보았습니다.(삭제 함수는 다음 절에 추가 예정)
*5.2절에서 이진트리의 내용을 자세히 다루니 그 때 좀 더 발전된 코드를 작성해보겠습니다!