[자료구조] 4-1. 이진트리(Binary Tree)

 

🔗공부하며 참고한 자료

https://happysalmon.tistory.com/85?category=911360

(C++) 자료구조 - 이진트리(Binary Tree) - 링크드리스트(Linked List)

 

---

 

💡 트리(Tree)란? 💡

1. 그래프의 한 종류
   • 스택(stack)과 큐(Queue)와는 다른 비선형적 자료구조
   • 계층적 관계를 표현하는 자료구조
2. 어떤 노드들의 집합으로 노드들은 각 서로 다른 자식을 가지며, 이 때 각 노드는 재사용되지 않는 구조이다.
3. 관련 용어
   
   • 노드(Node), 버택스(Vertex) : 트리의 구성요소
   • 간선(Edge), 링크(Link) : 노드와 노드를 연결하는 선
   • 루트 노드(Root Node) : 트리 구조에서 최상위에 있는 노드
   • 부모 노드(Parent Node) : 특정 노드와 연결되어 있는 윗 노드
   • 자식 노드(Child Node) : 특정 노드와 연결되어 있는 아래 노드
   • 형제 노드(Sibling Node) : 같은 부모를 둔 노드
   • 단말 노드(Terminal Node) : 아래로 다른 노드가 연결되어 있지 않은 노드
   • 비단말 노드(Nonterminal Node) : 연결되어 있는 노드
   • 레벨(Level) : 각 계층을 숫자를 표현
   • 높이(Height) : 트리 구조의 계층 길이

 

💡 이진 트리(Binary Tree)란? 💡

  : 모든 트리가 0개 혹은 최대 2개의 자식(왼쪽, 오른쪽) 노드를 갖는 트리이다.

쭉 읽으면 되는 선형구조와는 다르게 트리구조는 순회 방법에 따라서 데이터를 읽는 순서가 다르다.

루트 노드를 처음, 중간, 끝 중에서 언제 방문하는지에 따라서 3가지로 구분할 수 있다.

 

 

1. 전위 순회

        : 루트 노드를 가장 처음 방문하는 순회

            부모 ㄱ, 왼쪽 ㄴ, 오른쪽 ㄷ 일때 ㄱ → ㄴ → ㄷ 순으로 반복된다

 

2. 중위 순회

        : 루트 노드를 중간으로 방문하는 순회

            부모 ㄱ, 왼쪽 ㄴ, 오른쪽 ㄷ 일때 ㄴ → ㄱ → ㄷ 순으로 반복된다

 

3. 후위 순회

        : 루트 노드를 마지막으로 방문하는 순회

            부모 ㄱ, 왼쪽 ㄴ, 오른쪽 ㄷ 일때 ㄴ → ㄷ → ㄱ 순으로 반복된다

 

---

 

💖이진트리 by Linked List 💖

 

+)  배열을 이용하여 이진트리를 구현하지 않는 이유

            : 왼쪽, 오른쪽 자식 노드를 추가할 수 있는 이진 트리를 배열로 구현하면 메모리 공간의 낭비가 大

 

위의 그림과 같이 단 3개의 데이터를 저장하는데 최소 7개의 배열을 선언해야한다.

         => 따라서 주로 힙(Heap)을 구현할 때 사용함 - 완전 이진 트리(Complete Binary Tree)

 

 

 

💻 BinaryTreeLinkedList.h

#pragma once
struct Node{
 
    int data;
    Node* left;        // 왼쪽 자식 노드
    Node* right;    // 오른쪽 자식 노드
};
 
class BinaryTreeLinkedList {
 
public:
 
    BinaryTreeLinkedList();
    ~BinaryTreeLinkedList();
 
    Node* CreateNode();
    bool GetData(Node* node, int& data);    // 값 반환
    bool SetData(Node* node, int data);        // 값 지정
 
    bool GetLeftNode(Node* parent, Node** node);    // 노드의 왼쪽 자식 노드 반환
    bool GetRightNode(Node* parent, Node** node);    // 노드의 오른쪽 자식 노드 반환
 
    bool SetLeftNode(Node* parent, Node* child);    // 노드의 왼쪽 자식 노드 지정
    bool SetRightNode(Node* parent, Node* child);    // 노드의 오른쪽 자식 노드 지정
 
    void PreorderPrint(Node* node);            // 전위 순회
    void InorderPrint(Node* node);            // 중위 순회
    void PostorderPrint(Node* node);        // 후위 순회
 
    void RemoveNode(Node* node);            // 노드 제거
};

💻 5. Binary Tree.cpp

#include "BinaryTreeLinkedList.h"
#include <iostream>
 
BinaryTreeLinkedList::BinaryTreeLinkedList()
{
    printf("생성자\n");
}
 
BinaryTreeLinkedList::~BinaryTreeLinkedList()
{
    printf("소멸자\n");
}
 
Node* BinaryTreeLinkedList::CreateNode()
{
    Node* newNode = new Node;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
 
bool BinaryTreeLinkedList::GetData(Node* node, int& data)
{
    if (node == NULL)
        return false;
    data = node->data;    // node에 존재하는 data를 print
    printf("GetData %d\n", data);
    return true;
}
 
bool BinaryTreeLinkedList::SetData(Node* node, int data) // ?: 여기는 왜 &가 안 붙을까
{
    if (node == NULL)
        return false;
    node->data = data;    // 입력받은 data를 node의 data로 할당
    printf("SetData : %d\n", node->data);
    return true;
}
 
bool BinaryTreeLinkedList::GetLeftNode(Node* parent, Node** node) // ?: 여기는 왜 **
{
    if (parent == NULL || parent->left == NULL)
    {
        *node = NULL;
        return false;
    }
 
    *node = parent->left;
    printf("GetLeftNode : %d\n", (*node)->data);
    return true;
}
 
bool BinaryTreeLinkedList::GetRightNode(Node* parent, Node** node) // 여기는 왜 **?
{
    if (parent == NULL || parent->right == NULL)
    {
        *node = NULL;
        return false;
    }
 
    *node = parent->right;
    printf("GetrightNode : %d\n", (*node)->data);
    return true;
}
 
bool BinaryTreeLinkedList::SetLeftNode(Node* parent, Node* child)
{
    if (parent == NULL || child == NULL)
        return false;
    
    if (parent->left != NULL)    // 이미 왼쪽 자식 노드가 존재하면
        RemoveNode(parent->left);    // 왼쪽 자식 노드를 지워준다
 
    parent->left = child;
    printf("Set %d Node's LeftData : %d\n", parent->data, child->data);
    return true;
}
 
bool BinaryTreeLinkedList::SetRightNode(Node* parent, Node* child)
{
    if (parent == NULL || child == NULL)
        return false;
 
    if (parent->right != NULL)    // 이미 오른쪽 자식 노드가 존재하면
        RemoveNode(parent->right);    // 오른쪽 자식 노드를 지워준다
 
    parent->right = child;
    printf("Set %d Node's RightData : %d\n", parent->data, child->data);
    return true;
}
 
void BinaryTreeLinkedList::PreorderPrint(Node* node)
{
    if (node == NULL)
        return;
 
    printf("Pre : %d\n", node->data);
    PreorderPrint(node->left);
    PreorderPrint(node->right);
}
 
void BinaryTreeLinkedList::InorderPrint(Node* node)
{
    if (node == NULL)
        return;
 
    InorderPrint(node->left);
    printf("In : %d\n", node->data);
    InorderPrint(node->right);
}
 
void BinaryTreeLinkedList::PostorderPrint(Node* node)
{
    if (node == NULL)
        return;
 
    PostorderPrint(node->left);
    PostorderPrint(node->right);
    printf("Post : %d\n", node->data);
}
 
void BinaryTreeLinkedList::RemoveNode(Node* node)
{    // 지우는 방식은 후위 순회방식
    if (node == NULL)
        return;
    RemoveNode(node->left);
    RemoveNode(node->right);
    printf("Delete : %d\n", node->data);
    delete node;
}

 

 ❔ 🙄 ❔

💨 GetData와 SetData의 차이

// line 22
bool BinaryTreeLinkedList::GetData(Node* node, int& data)
{
    if (node == NULL)
        return false;
    data = node->data;    // node에 존재하는 data를 print
    printf("GetData %d\n", data);
    return true;
}

bool BinaryTreeLinkedList::SetData(Node* node, int data) // ?: 여기는 왜 &가 안 붙을까
{
    if (node == NULL)
        return false;
    node->data = data;    // 입력받은 data를 node의 data로 할당
    printf("SetData : %d\n", node->data);
    return true;
}

설명 추가

 

💨 GetLeftNode 원리

// line 53
bool BinaryTreeLinkedList::GetLeftNode(Node* parent, Node** node) // ?: 여기는 왜 **
{
    if (parent == NULL || parent->left == NULL)
    {
        *node = NULL;
        return false;
    }

    *node = parent->left;
    printf("GetLeftNode : %d\n", (*node)->data);
    return true;
}

 : 노드를 반환하는 Get 함수 같은 경우 이중 포인터를 사용

   함수 반환 값을 노드로 지정 X

   bool로 성공/실패 여부를 반환하는 방식을 택하여 이중 포인터를 사용했다

 

 : 입력 받은 node를 부모 노드의 왼쪽 자식으로 할당한다. 

 

 

💻 실행 예시

#include <iostream>
#include "BinaryTreeLinkedList.h"
 
int main()
{
    BinaryTreeLinkedList* ListBinaryTree = new BinaryTreeLinkedList();
 
    Node* tempANode = ListBinaryTree->CreateNode();
    Node* tempBNode = ListBinaryTree->CreateNode();
    Node* tempCNode = ListBinaryTree->CreateNode();
    Node* tempDNode = ListBinaryTree->CreateNode();
    Node* tempENode = ListBinaryTree->CreateNode();
    Node* tempFNode;
 
    ListBinaryTree->SetData(tempANode, 1);
    ListBinaryTree->SetData(tempBNode, 2);
    ListBinaryTree->SetData(tempCNode, 3);
    ListBinaryTree->SetData(tempDNode, 4);
    ListBinaryTree->SetData(tempENode, 5);
 
    printf("\n");
    ListBinaryTree->SetLeftNode(tempANode, tempBNode);
    ListBinaryTree->SetRightNode(tempANode, tempCNode);
    ListBinaryTree->SetData(tempANode->left, 20);        //왼쪽 자식 노드 값 변경
 
    printf("\n");
    ListBinaryTree->GetRightNode(tempANode, &tempFNode); //오른쪽 자식 노드 가져와서
    ListBinaryTree->SetData(tempFNode, 30);             //그 노드의 값 변경
 
    printf("\n");
    ListBinaryTree->GetLeftNode(tempANode, &tempFNode);
    ListBinaryTree->SetLeftNode(tempFNode, tempDNode);
    ListBinaryTree->SetRightNode(tempFNode, tempENode);
 
    printf("\n");
 
    int data;
    ListBinaryTree->GetData(tempANode, data);
    ListBinaryTree->GetData(tempBNode, data);
    ListBinaryTree->GetData(tempCNode, data);
    ListBinaryTree->GetData(tempDNode, data);
    ListBinaryTree->GetData(tempENode, data);
    ListBinaryTree->GetData(tempFNode, data);
 
    printf("\n");
    ListBinaryTree->PreorderPrint(tempANode);
    printf("\n");
    ListBinaryTree->InorderPrint(tempANode);
    printf("\n");
    ListBinaryTree->PostorderPrint(tempANode);
 
    printf("\n");
    ListBinaryTree->RemoveNode(tempANode);
    delete ListBinaryTree;
}

실행 결과

Get