Tree (재귀함수 이용)

트리도 Linked List와 마찬가지로 구현하였다.

다만 트리의 삭제는 위치를 변경해줘야하므로 구현하기 힘들어 입력과 출력만 구현하였다.

struct Tree
{
    int value;
    Tree* pLeft;
    Tree* pRight;
};

구조체는 LinkedList와 마찬가지로 생성.

다만 트리이므로 왼쪽과 오른쪽에 하나씩 이어지므로 포인터가 2개 필요하다.

1. 입력

void Add(Tree* pNode, Tree* pNew)
{
    if (pNode->value > pNew->value)
    {
        if (pNode->pLeft != NULL)
            Add(pNode->pLeft, pNew);
        else
            pNode->pLeft = pNew;
    }
    else
    {
        if (pNode->pRight != NULL)
            Add(pNode->pRight, pNew);
        else
            pNode->pRight = pNew;
    }
}

입력 이전에 데이터를 추가하는 함수를 하나 만들었다.

노드부터 시작해 새로운값이 크면 오른쪽, 작으면 왼쪽으로 추가하되, 

비어있다면 바로 그자리에 넣고 값이 있다면 계속 타고가면서 비교하여 들어갈 자리에 넣는다.

if (menu == 1)
{
    int input = 0;
    cout << "입력할 값은? : ";
    cin >> input;
 
    Tree* pNewData = new Tree;
    pNewData->value = input;
    pNewData->pLeft = NULL;
    pNewData->pRight = NULL;
 
    if (head == NULL)
    {
        head = pNewData;
    }
    else
    {
        Add(head, pNewData);
    }
 
    cout << "값이 입력되었습니다. \n\n";
}

입력은 LinkedList와 마찬가지로 새로운 데이터를 만들어 노드(=head)가 비어있으면 새로운값을 노드로.

아니면 함수를 이용해 쭉 타고가면서 들어갈 자리에 입력된다.

2. 출력

void print(Tree* pData)
{
    if (pData->pLeft)
        print(pData->pLeft);
    cout << pData->value << " ";
    if (pData->pRight)
        print(pData->pRight);
}

출력도 재귀함수를 이용해 출력하는 함수를 하나 만들었다.

왼쪽이 존재하면 왼쪽으로 들어가고, 없으면 자기자신 출력, 이후 오른쪽이 존재하면 들어간다.

이렇게 반복하면 트리의 구조상 순서대로 잘 출력될 것이다.

else if (menu == 2)
{
    print(head);
    cout << "\n\n";
}

그래서 출력은 함수 한번 불러주면 끝