6-4. [C++] 연결 리스트로 구현한 이진 트리

앞서 다뤘던 이진 트리의 ADT를 이용해 정수(int)를 저장하는 이진 트리의 UML 다이어그램을 구성해보자.

이진 트리의 노드를 구현한 BinaryNode 클래스를 만들고,

이진 트리를 구현한 BinaryTree 클래스에서는 노드 클래스를 사용할 것이다.

BinaryNode 클래스를 먼저 구현해보자.

// BinaryNode.h
#include <iostream>

class BinaryNode {
protected:
    int data;
    BinaryNode *left;
    BinaryNode *right;

public:
    BinaryNode(int data = 0, BinaryNode *left = NULL, BinaryNode *right = NULL)
        : data(data), left(left), right(right) {}

    void setData(int data) { this->data = data; }
    void setLeft(BinaryNode *left) { this->left = left; }
    void setRight(BinaryNode *right) { this->right = right; }

    int getData() { return data; }
    BinaryNode *getLeft() { return left; }
    BinaryNode *getRight() { return right; }

    bool isLeaf() { return (left == NULL) && (right == NULL); }
};

BinaryNode 클래스를 사용해서 BinaryTree 클래스를 구현해보자.

(아직 미완성인 코드, 주석 처리된 부분은 뒤에서 자세히 다뤄보자.)

// BinaryTree.h
#include "BinaryNode.h"

class BinaryTree {
    BinaryNode *root;

public:
    BinaryTree() : root(NULL) {}

    void setRoot(BinaryNode *node) { root = node; }
    BinaryNode *getRoot() { return root; }

    bool isEmpty() { return (root == NULL); }

    // void preorder() {...}
    // void inorder() {...}
    // void postorder() {...}
    // void levelorder() {...}
    // void display() {
    //     preorder();
    //     inorder();
    //     postorder();
    //     levelorder();
    // }

    // int getCount() {...}
    // int getHeight() {...}
    // int getLeafCount() {...}
};

위에서 구현한 클래스를 이용해서 아래 사진의 이진 트리를 생성해보자.

// BinaryTree.cpp
#include "BinaryTree.h"

int main() {
    BinaryTree tree;

    BinaryNode *F = new BinaryNode(6, NULL, NULL);
    BinaryNode *E = new BinaryNode(5, NULL, NULL);
    BinaryNode *D = new BinaryNode(4, NULL, NULL);
    BinaryNode *C = new BinaryNode(3, F, NULL);
    BinaryNode *B = new BinaryNode(2, D, E);
    BinaryNode *A = new BinaryNode(1, B, C);

    tree.setRoot(A);

    return 0;
}

위 코드는 아래 이미지를 클릭해 깃허브에서도 확인할 수 있다.