6-6. [C++] 이진 트리의 연산 구현

이진 트리의 연산

앞서 구현했던 이진 트리 코드에서 연산 부분을 완성시켜보자.

https://seongmoahn.tistory.com/96

6-5. [C++] 이진 트리의 순회(전위/중위/후위/레벨 순회)

이진 트리에는 순회 이외에도 여러 가지 연산들이 있다.

(노드 개수 구하기, 단말 노드 개수 구하기, 높이 구하기 등)

---

이진 트리의 노드 개수 구하기

트리의 전체 노드 개수를 구하기 위해서는 트리의 모든 노드들을 순회해야 한다.

왼쪽 서브트리의 노드 개수 + 오른쪽 서브트리의 노드 개수 + 루트 노드(+1)를 계산하면 전체 노드 개수를 구할 수 있다.

 

먼저 알고리즘을 알아보자.

getCount(x)

if x = NULL
	then return 0;
    else return 1 + getCount(LEFT(x)) + getCount(RIGHT(x));

트리가 재귀적으로 정의된 것처럼 노드의 개수를 구할 때도 재귀적으로 구할 수 있다.

---

이진 트리의 단말 노드 개수 구하기

단말 노드의 개수를 구할 때도 트리의 모든 노드들을 순회해야 한다.

순회하다가 어떤 노드의 왼쪽 자식 노드와 오른쪽 자식 노드가 모두 NULL이면 해당 노드는 단말 노드이다.

단말 노드의 경우 1을 반환하고, 비단말 노드의 경우 재귀적으로 왼쪽/오른쪽 서브트리를 순회한다.

 

알고리즘을 알아보자.

getLeafCount(x)

if x = NULL then return 0;
if LEFT(x) = NULL and RIGHT(x) = NULL
	then return 1;
    else return getLeafCount(LEFT(x)) + getLeafCount(RIGHT(x));

---

이진 트리의 높이 구하기

트리의 높이를 구할 때도 트리의 모든 노드들을 순회해야 한다.

이때도 각 서브트리에 대한 재귀 호출을 해서 왼쪽/오른쪽 서브트리의 높이를 반환받는다.

왼쪽/오른쪽 서브트리의 높이 중 더 큰 값에 현재 트리의 노드 높이(+1)까지 더한 값이 현재 트리의 높이가 된다.

 

알고리즘을 알아보자.

getHeight(x)

if x = NULL
	then return 0;
    else 1 + MAX(getHeight(LEFT(x)), getHeight(RIGHT(x));

---

C++ 코드로 구현

// BinaryTree.h
#include "circularQueue.h"
#include <algorithm>
using namespace std;

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() {
        cout << "preorder   : ";
        preorder(root);
        cout << endl;
    }
    void preorder(BinaryNode *node) {
        if (node == NULL) return ;

        cout << "[" << node->getData() << "] ";
        preorder(node->getLeft());
        preorder(node->getRight());
    }
    void inorder() {
        cout << "inorder    : ";
        inorder(root);
        cout << endl;
    }
    void inorder(BinaryNode *node) {
        if (node == NULL) return;

        inorder(node->getLeft());
        cout << "[" << node->getData() << "] ";
        inorder(node->getRight());
    }
    void postorder() {
        cout << "postorder  : ";
        postorder(root);
        cout << endl;
    }
    void postorder(BinaryNode *node) {
        if (node == NULL) return;

        postorder(node->getLeft());
        postorder(node->getRight());
        cout << "[" << node->getData() << "] ";
    }
    void levelorder() {
        CircularQueue queue;
        if (root == NULL) return;
        queue.enqueue(root);

        cout << "levelorder : ";

        while (!queue.isEmpty()) {
            BinaryNode *curNode = queue.dequeue();
            if (curNode == NULL) continue;

            cout << "[" << curNode->getData() << "] ";
            queue.enqueue(curNode->getLeft());
            queue.enqueue(curNode->getRight());
        }
        cout << endl;
    }
    void display() {
        preorder();
        inorder();
        postorder();
        levelorder();
    }

    int getCount() {
        return isEmpty() ? 0 : getCount(root);
    }
    int getCount(BinaryNode *node) {
        if (node == NULL) return 0;

        return 1 + getCount(node->getLeft()) + getCount(node->getRight());
    }

    int getLeafCount() {
        return isEmpty() ? 0 : getLeafCount(root);
    }
    int getLeafCount(BinaryNode *node) {
        if (node == NULL) return 0;

        if (node->isLeaf()) return 1;
        else return getLeafCount(node->getLeft()) + getLeafCount(node->getRight());
    }

    int getHeight() {
        return isEmpty() ? 0 : getHeight(root);
    }
    int getHeight(BinaryNode *node) {
        if (node == NULL) return 0;

        return 1 + max(getHeight(node->getLeft()), getHeight(node->getRight()));
    }
};

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

int main() {
    BinaryTree tree;

    BinaryNode *G = new BinaryNode(7, NULL, NULL);
    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, G);
    BinaryNode *B = new BinaryNode(2, D, E);
    BinaryNode *A = new BinaryNode(1, B, C);

    tree.setRoot(A);

    tree.display();

    cout << endl << "tree node count      : " << tree.getCount() << endl;
    cout << "tree leaf node count : " << tree.getLeafCount() << endl;
    cout << "tree height          : " << tree.getHeight() << endl;

    return 0;
}

/*
실행 결과:
preorder   : [1] [2] [4] [5] [3] [6] [7]
inorder    : [4] [2] [5] [1] [6] [3] [7]
postorder  : [4] [5] [2] [6] [7] [3] [1]
levelorder : [1] [2] [3] [4] [5] [6] [7]

tree node count      : 7
tree leaf node count : 4
tree height          : 3
*/

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