[자료구조] 트리 (tree)

트리

트리는 한 개 이상의 노드로 이루어진, 나무를 거꾸로 엎어놓은 듯한 모양의 비선형 자료구조다.

 

---

 

🎄 트리의 종류

트리의 종류는 여러 가지가 있을 수 있다.

그중에서 가장 일반적인 트리로 일반 트리와 이진트리가 있다.

 

 

🎆 일반 트리

https://www.javatpoint.com/tree

일반 트리는 위 사진과 같이 생겼다.

일반 트리에서 노드는 0개부터 최대 N개의 노드를 가질 수 있다. (N은 제한이 없다)

 

 

 

🎆 이진트리

https://www.javatpoint.com/tree

이진트리는 위 사진과 같이 생겼다.

이진트리에서 이진은 0과 1을 나타내고, 부모 노드가 자식 노드를 최대 2개까지만 가질 수 있다.

 

 

---

구현 (C++)

• insert()
• search()
• print()

 

---

 

클래스 생성

class BSTNode
{
public:
    int Key;
    BSTNode *Left;
    BSTNode *Right;
    BSTNode *Parent;
};

 

 

Insert 함수

BSTNode *Insert(BSTNode *node, int key)
{
    if (node == NULL)
    {
        node = new BSTNode;
        node->Key = key;
        node->Left = NULL;
        node->Right = NULL;
        node->Parent = NULL;
    }
    else if (node->Key < key)
    {
        node->Right = Insert(node->Right, key);
        node->Right->Parent = node;
    }
    else
    {
        node->Left = Insert(node->Left, key);
        node->Left->Parent = node;
    }

    return node;
}

 

search 함수

BSTNode *Search(BSTNode *node, int key)
{
    if (node == NULL)
        return NULL;
    else if (node->Key == key)
        return node;
    else if (node->Key < key)
        return Search(node->Right, key);
    else
        return Search(node->Left, key);
}

 

---

 

 

PrintInorder (중위 순회로 출력)

void PrintInorder(BSTNode *root)
{
    if (root != NULL)
    {
        PrintInorder(root->Left);
        cout << root->Key << " ";
        PrintInorder(root->Right);
    }
}

 

 

search 함수

bool search(BSTNode *root, int key)
{
    BSTNode *result = Search(root, key);

    return result == NULL ? false : true;
}

 

 

 

---

 

📌 전체 코드

#include <iostream>
using namespace std;

class BSTNode
{
public:
    int Key;
    BSTNode *Left;
    BSTNode *Right;
    BSTNode *Parent;
};

BSTNode *Insert(BSTNode *node, int key)
{
    if (node == NULL)
    {
        node = new BSTNode;
        node->Key = key;
        node->Left = NULL;
        node->Right = NULL;
        node->Parent = NULL;
    }
    else if (node->Key < key)
    {
        node->Right = Insert(node->Right, key);
        node->Right->Parent = node;
    }
    else
    {
        node->Left = Insert(node->Left, key);
        node->Left->Parent = node;
    }

    return node;
}

BSTNode *Search(BSTNode *node, int key)
{
    if (node == NULL)
        return NULL;
    else if (node->Key == key)
        return node;
    else if (node->Key < key)
        return Search(node->Right, key);
    else
        return Search(node->Left, key);
}

void PrintInorder(BSTNode *root)
{
    if (root != NULL)
    {
        PrintInorder(root->Left);
        cout << root->Key << " ";
        PrintInorder(root->Right);
    }
}

bool search(BSTNode *root, int key)
{
    BSTNode *result = Search(root, key);

    return result == NULL ? false : true;
}

int main()
{
    BSTNode *root = NULL;

    root = Insert(root, 15);
    root = Insert(root, 10);
    root = Insert(root, 20);
    root = Insert(root, 25);
    root = Insert(root, 8);
    root = Insert(root, 12);

    PrintInorder(root);

    cout << "\n트리에 15가 있는지 찾아봅니다.\n";

    if (search(root, 15))
        cout << "15가 트리에 존재합니다.";
    else
        cout << "15는 트리에 존재하지 않습니다.";
}

 

 

 

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!