BinaryTree 구현.

-트리의 용어

루트 노드(root node): 부모가 없는 노드. 트리는 단 하나의 루트 노드를 가짐.

서브 트리(sub tree): 루트 노드를 제외한 나머지 노드들.

링크(link): 루트 노드와 서브트리를 연결하는 선. 간선/에지(edge)라 부름.

형제(sibling): 같은 부모 노드를 가지는 노드.

단말 노드(leaf node): 자식 노드가 없는 노드.

 

노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수.

노드의 깊이(depth): 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 링크(간선)의 수.

노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합. (루트 = 1레벨)

노드의 차수(degree): 노드가 지닌 가지(간선)의 수.

트리의 차수(degree of tree): 트리의 최대 차수.

트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이.

 

-트리의 기본 성질

n개의 노드를 가진 트리는 n-1개의 링크(간선)을 가진다.

트리에서, 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드 간의 경로도 유일하다.

(같은 노드를 두 번 이상 방문하지 않는 다는 조건 하에)

 

*이진 트리

각 노드는 최대 2개의 자식을 가진다.

각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지가 지정된다. (자식이 하나일 경우도)

높이가 h인 이진트리는 2^h-1개 이하의 노드를 가진다.

 

-배열 표현법

노드 i의 부모 노드 인덱스 = i/2

노드 i의 왼쪽 자식 노드 인덱스 = 2i

노드 i의 오른쪽 자식 노드 인덱스 = 2i + 1

 

-이진트리의 순회 방법

전위 순회(root>left>right)

중위 순회(left>root>right)

후위 순회(left>right>root)

 

class BinaryNode
{
protected:
    int data;
    BinaryNode* left;
    BinaryNode* right;
public:
    BinaryNode(int value = 0, BinaryNode* l = NULL, BinaryNode* r = NULL) 
        : data(value), left(l), right(r)
    {}
    void setData(int value)
    {
        data = value;
    }
    void setLeft(BinaryNode* node)
    {
        left = node;
    }
    void setRight(BinaryNode* node)
    {
        right = node;
    }
    int getData()
    {
        return data;
    }
    BinaryNode* getLeft()
    {
        return left;
    }
    BinaryNode* getRight()
    {
        return right;
    }
    bool isLeaf()
    {
        return left == NULL && right == NULL;
    }
};
 
 
#include "BinaryNode.h"
 
class BinaryTree
{
private:
    BinaryNode* root;
public:
    BinaryTree() : root(NULL)
    {}
    void setRoot(BinaryNode* node)
    {
        root = node;
    }
    BinaryNode* getRoot()
    {
        return root;
    }
    bool isEmpty()
    {
        return root == NULL;
    }
 
    void preorder()
    {
        printf("\n  preorder: ");
        preorder(root);
    }
    void preorder(BinaryNode* node)
    {
        if (node != NULL)
        {
            printf(" [%c]", node->getData());
            preorder(node->getLeft());
            preorder(node->getRight());
        }
    }
    void inorder()
    {
        printf("\n   inorder: ");
        inorder(root);
    }
    void inorder(BinaryNode* node)
    {
        if (node != NULL)
        {
            inorder(node->getLeft());
            printf(" [%c]", node->getData());            
            inorder(node->getRight());
        }
    }    
    void postorder()
    {
        printf("\n postorder: ");
        postorder(root);
    }
    void postorder(BinaryNode* node)
    {
        if (node != NULL)
        {
            postorder(node->getLeft());
            postorder(node->getRight());
            printf(" [%c]", node->getData());
        }
    }
    void levelorder()
    {
        //
    }
 
    int getCount()
    {
        return isEmpty() ? 0 : getCount(root);
    }
    int getCount(BinaryNode* node)
    {
        if (node == NULL)
            return 0;
        else
            return 1 + getCount(node->getLeft()) + getCount(node->getRight());
    }
    int getHeight()
    {
        return isEmpty() ? 0 : getHeight(root);
    }
    int getHeight(BinaryNode* node)
    {
        if (node == NULL) return 0;
        int hLeft = getHeight(node->getLeft());
        int hRight = getHeight(node->getRight());
        return (hLeft > hRight) ? hLeft + 1 : hRight + 1;
    }
    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());
    }
};