C++/Fundamentals of Data Structures in C++(Horowitz)

C++ Fundamentals of Data Structures(C++ 자료구조론) 5.1 Tree(트리)

꾸준함. 2017. 8. 26. 12:00

/*

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절에서 이진트리의 내용을 자세히 다루니 그 때 좀 더 발전된 코드를 작성해보겠습니다!

반응형