[자료구조] 이진트리(Binary Tree)

이진트리

모든 노드가 최대 2개의 서브 트리를 가질 수 있는 트리

높이가 h일 때 최소 h개의 노드, 최대 2^h-1개의 노드를 가짐

노드의 개수가 n개일 때 간선의 개수는 n-1

 

이진트리 종류

포화 이진트리 : 트리의 모든 레벨에 노드가 모두 차있는 이진트리

완전 이진트리 : 높이가 h일 때 레벨 1부터 h-1까지는 노드가 모두  채워져 있고 마지막 레벨 h에서는 왼쪽부터 오른쪽의 순서로 노드가 채워져 있는 이진트리

<- 포화 이진트리, 완전 이진트리 ->

 

연결리스트를 이용한 이진트리

#include <iostream>

using namespace std;
typedef int element;

typedef struct Node{
    element data;
    Node* left;
    Node* right;
}Node;

class BinaryTree{
    public:
        BinaryTree();
        ~BinaryTree();

        Node* CreateNode(element data);

        
        int getNodeCount(Node* node);
        int getHeight(Node* node);
        element getData(Node* node);
        bool setData(Node* node, element data);

        void preOrder(Node* node);
        void inOrder(Node* node);
        void postOrder(Node* node);

};
BinaryTree::BinaryTree(){}
BinaryTree::~BinaryTree(){}

Node *BinaryTree::CreateNode(element data){
    Node* newNode = new Node();
    newNode->left = nullptr;
    newNode->right = nullptr;
    newNode->data = data;
    return newNode;
}
int BinaryTree::getNodeCount(Node* node){
    int count = 0;
    if(node != nullptr)count = 1 + getNodeCount(node->left) + getNodeCount(node->right);
    return count;
}
int BinaryTree::getHeight(Node* node){
    int height = 0;
    if(node != nullptr)height = 1 + max(getHeight(node->left),getHeight(node->right));
    return height;
}
element BinaryTree::getData(Node* node){
    if(node == nullptr)return -1;
    return node->data;
}
bool BinaryTree::setData(Node* node, element data){
    if(node == nullptr)return false;
    node->data = data;
    return true;
}
void BinaryTree::preOrder(Node* node){
    if(node != nullptr){
        cout << getData(node) << " ";
        preOrder(node->left);
        preOrder(node->right);
    }
}
void BinaryTree::inOrder(Node* node){
    if(node != nullptr){
        inOrder(node->left);
        cout << getData(node) << " ";
        inOrder(node->right);
    }
}

void BinaryTree::postOrder(Node* node){
    if(node != nullptr){
        postOrder(node->left);
        postOrder(node->right);
        cout << getData(node) << " ";
    }
}


int main(){
    BinaryTree* tree = new BinaryTree();

    Node* root = tree->CreateNode(1);
    Node* nodeA = tree->CreateNode(2);
    Node* nodeB = tree->CreateNode(3);
    Node* nodeC = tree->CreateNode(4);
    Node* nodeD = tree->CreateNode(5);
    Node* nodeE = tree->CreateNode(6);
    Node* nodeF = tree->CreateNode(7);
    root->left = nodeA;
    root->right = nodeB;
    nodeA->left = nodeC;
    nodeA->right = nodeD;
    nodeB->left = nodeE;
    nodeB->right = nodeF;

    tree->preOrder(root);
    cout << "\n";
    tree->inOrder(root);
    cout << "\n";
    tree->postOrder(root);
    cout << "\n";
    /*
	1 2 4 5 3 6 7
	4 2 5 1 6 3 7
	4 5 2 6 7 3 1
    */
}

 

순회 종류

순회 : 트리의 노드들을 체계적으로 방문하는 것

 

• 전위순회 VLR (preorder) : 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 방문
• 중위순회 LVR (inorder) : 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서로 방문
• 후위순회 LRV (postorder) : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순서로 방문