C++로 구현하는 자료구조 (4) - BinaryTree

c++로 구현하는 자료구조

네번째 포스팅은 이진트리이다. 나는 실제로 기술면접과 코딩테스트에서 트리관련 문제를 받았었는데 준비를 더 했었더라면 하는 아쉬움이 있었다. 알고리즘과 자료구조의 기본을 많이 물어보는 회사라면 꼭 숙지해가자!

 

---

 

1. BinaryTree

막상 이진트리에 대해 설명을 작성하려고 할 때 쉽게 설명할 수 있는 정의가 떠오르지 않는다. 내 머리 속에는 정말 '나무처럼 생긴 자료구조'(...)라고 박혀있다.

위키백과에서는 트리 구조를 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조라고 정의하고 있다. 따라서 순환하는 싸이클이 존재할 수 없고 서로 다른 두 노드를 잇는 길이 하나 뿐인 그래프를 트리라고 부른다. 트리에서는 최상위 노드를 루트 노드라고 부르고, 부모에서 자식 노드로만 길이 이어져있다.

이진트리는 트리구조의 특별한 케이스로, 자식노드를 2개까지만 갖을 수 있는 트리구조이다. 실무에서 트리 자료구조를 구현하거나, 트리를 이용한 알고리즘을 이용해보진 못했지만 코딩테스트에서는 쉽게 볼 수 있는 자료구조이다.

 

2. 재귀적 순회방법

출처: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

이진트리 자료구조를 처음 공부할 때 가장 기초적인 부분에서부터 막혔었다. 트리에 대한 어떤 문제든 우선 트리를 순회해야하는데, 어떻게 접근해야 할지 막막했다. 정답은 재귀적으로 순회하는 것이었고 처음 이진트리를 공부하는 나에겐 충격이었다. 재귀적으로 문제를 접근한다는 것 자체를 떠올리기 어려웠던 시절이라 이진트리 순회는 내가 한 단계 레벨업 할 수 있었던 문제였다.

이진트리를 순회하는 방법은 크게 3가지로 나눌 수 있다. 전위, 중위, 후위 순회로 나뉘며 기술면접에서도 기본지식을 평가하기 위해 자주 물어보는 것 같다. 코딩테스트와 기술면접에서 실제로 질문을 받아봤기 때문에 꼭 알아둬야 할 개념이다.

 

// 전위순회
void preOrder(Node* root) {
	cout << root->value << endl;
	preOrder(root->left)
	preOrder(root->right)
}

// 중위순회
void inOrder(Node* root) {
	inOrder(root->left)
	cout << root->value << endl;
	inOrder(root->right)
}

// 후위순회
void postOrder(Node* root) {
	postOrder(root->left)
	postOrder(root->right)
	cout << root->value << endl;
}

전위순회는 현재 노드를 먼저 방문하는 순회방법이다. 그래서 root의 값을 먼저 출력한다. 중위순회는 왼쪽을 먼저 방문하는 방식으로 순회가 진행된다. 후위순회의 경우에는 자식노드를 먼저 순회하기 때문에 루트노드가 가장 나중에서 방문된다.

 

3. 소스코드

// BinaryTree.h
#pragma once
#include <iostream>
#include <queue>

// 이진 트리의 노드
class Node {
public:
    int value;
    Node* left;
    Node* right;
    Node(const int& value) : value(value) {}
};

// 이진 트리 클래스
class BinaryTree {
private:
    Node* head;

		// 중위 순회 방식으로 노드에 데이터 삽입
    void insert(Node* node, const int& value) {

        std::queue<Node*> q;
        q.push(node);

        Node* cursor;
        while (!q.empty()) {
            cursor = q.front();
            q.pop();

            if (cursor->left != nullptr) {
                q.push(cursor->left);
            }
            else {
                cursor->left = new Node(value);
                break;
            }
            
            if (cursor->right != nullptr) {
                q.push(cursor->right);
            }
            else {
                cursor->right = new Node(value);
                break;
            }
        }
        return;
    }

		// 전위 순회 방식으로 노드 찾기
    Node* findPreorderTraversal(Node* cursor, const int& value) {
        if (cursor != nullptr) {
            if (cursor->value == value) {
                return cursor;
            }
            
            Node* left = this->findPreorderTraversal(cursor->left, value);
            Node* right = this->findPreorderTraversal(cursor->right, value);

            if (left != nullptr && right == nullptr) {
                return left;
            }
            else if (left == nullptr && right != nullptr) {
                return right;
            }
            else {
                return nullptr;
            }
        }
        else {
            return nullptr;
        }
    }

		// 전위순회
    void printPreorderTraversal(Node* cursor) {
        if (cursor != nullptr) {
            std::cout << cursor->value << " ";
            this->printPreorderTraversal(cursor->left);
            this->printPreorderTraversal(cursor->right);
        }
    }

		// 중위 순회
    void printInorderTraversal(Node* cursor) {
        if (cursor != nullptr) {
            this->printInorderTraversal(cursor->left);
            std::cout << cursor->value << " ";
            this->printInorderTraversal(cursor->right);
        }
    }

		// 후위 순회
    void printPostorderTraversal(Node* cursor) {
        if (cursor != nullptr) {
            this->printPostorderTraversal(cursor->left);
            this->printPostorderTraversal(cursor->right);
            std::cout << cursor->value << " ";
        }
    }

public:
    BinaryTree() {}

    void insertNode(const int& value) {
        if (this->head == nullptr) {
            this->head = new Node(value);
            return;
        }
        this->insert(this->head, value);
    }

    void printTree(const int& order) {
        switch (order) {
            case 0: this->printPreorderTraversal(this->head); break;
            case 1: this->printInorderTraversal(this->head); break;
            case 2: this->printPostorderTraversal(this->head); break;
            default: break;
        }
        std::cout << std::endl;
    }

    Node* findNode(const int& value) {
        return this->findPreorderTraversal(this->head, value);
    }
};

#include <iostream>
#include "datastructure/BinaryTree.h"

int main() {

    BinaryTree* bt = new BinaryTree();

    for (int idx = 0; idx < 10; idx++) {
        bt->insertNode(idx);
    }

    std::cout << "preorder" << std::endl;
    bt->printTree(0); // preorder
    std::cout << std::endl;
    // result : 0 1 3 7 8 4 9 2 5 6

    std::cout << "inorder" << std::endl;
    bt->printTree(1); // inorder
    std::cout << std::endl;
    // result : 7 3 8 1 9 4 0 5 2 6

    std::cout << "postorder" << std::endl;
    bt->printTree(2); // postorder
    std::cout << std::endl;
    // result : 7 8 3 9 4 1 5 6 2 0

    Node* found = bt->findNode(9);
    std::cout << found->value << std::endl;

    return 0;
}