[DS] 이진트리(Binary Tree)란?

이진트리(Binary Tree)란?

각 노드가 최대 두 개의 자식을 갖는 트리입니다.

 

 

- 유한개(>=0)의 node로 이루어짐

- empty이거나 root와 두개의 disjoint binary tree로 구성됨

 

이진트리(binary tree)에는 순서(order)가 있습니다.

Disjoint binary tree

- left subtree

- right subtree

 

 

 

이진트리(Binary tree) 관련 용어(Terminology)

---

완전 이진 트리(Complete binary tree)이란

n개의 노드(node)가 level 순서로 모두 채워진 이진트리(binary tree)입니다.

노드(node)가 위에서 아래로 왼쪽부터 오른쪽으로 잘 채워져 있으면 됩니다.

 

 

정 이진트리(Full binary tree)이란

주어진 height(=depth)에서 최대 노드(node)수를 갖는 이진트리(binary tree)입니다.

Level 순서로 hight 만큼 노드(node)가 꽉 채워져 있으면 됩니다.

 

 

 

Lemma

---

① Level이 i인 노드(node)는 최대 2^(i-1)개이다.

② Height가 k인 이진 트리(binary tree)에서 최대 노드(node) 수는 2^k-1개이다.

③ 어떤 이진 트리(binary tree)에서 degree가 0인 노드(node-leaf)의 수는 degree가 2인 node 수보다 1개 많다.

 

n - 총 노드(node)의 수

B - 총 브랜치(branch, edge) 수

n0 - leaf node의 수

n1 - degree가 1인 노드(node)의 수

n2 - degree가 2인 노드(node)의 수

 

총 node의 수 

n = n0 + n1 + n2  -  (1)

 

Branch는 각 node의 degree의 합

B = n1 + n2  -  (2)

 

총 node 수는 branch 수보다 1개 많음

n = B + 1  -  (3)

 

 

(2), (3) 계산하면

n = n1 + 2n2 + 1  -  (4)

 

(1), (4) 계산하면

n0 = n2 + 1

 

 

이진트리(binary tree) 구현하기 위한 ADT 정의

---

class node {
public:
    string name;
    double score;
    node *left, *right;
    void set_data(string s, double d);
};

데이터와 포인터를 포함한 node 클래스를 만들어줍니다.

포인터는 node 클래스를 가르키기 때문에 node type으로 정의합니다.

 

*left - left child

*right - right child

 

 

class binary_tree {
    int node_cnt;
    node *root;
public:
    binary_tree();
    int insert_root(node t);
    int insert_left(string tname, node t);
    int insert_right(string tname, node t);

    double score_sum();
    double score_average();
    void print_data_inorder();
    void print_data_preorder();
    void print_data_postorder();
};
int node_insert_left(node *p, string tname, node tnode);
int node_insert_right(node *p, string tname, node tnode);
double sum_allnodes(node *p);
void inorder_print(node *p);
void preorder_print(node *p);
void postorder_print(node *p);

binary_tree - 이진트리(binary tree)를 생성한 초기 상태

insert_root - root node에 원소 추가

insert_left - left child node에 원소 추가 성공 여부

insert_right - right child node에 원소 추가 성공 여부

score_sum - node 데이터로 들어온 score 값의 총점을 return

score_average - node 데이터로 들어온 score 값의 평균을 return

print_data_inorder - private root 데이터를 파라미터로 넘겨주는 역할

print_data_preorder - private root 데이터를 파라미터로 넘겨주는 역할

print_data_postorder - private root 데이터를 파라미터로 넘겨주는 역할

node_insert_left - left child node에 원소 추가

node_insert_right - right child node에 원소 추가

sum_allnodes - node를 traversal 하면서 score의 총점을 구해주는 함수

inorder_print - 

preorder_print - 

postorder_print - 

 

 

 

함수 구현

---

void node::set_data(string s, double n) {
    name = s;
    score = n;
}

node class의 data를 셋팅(setting)해주는 메소드(method)입니다.

 

 

 

binary_tree::binary_tree() {
    node_cnt = 0;
    root = NULL;
}

이진트리(binary tree) class의 생성자(constructor)에서는 node_cnt를 0으로, root는 NULL로 초기화 시킵니다.

 

 

 

int binary_tree::insert_root(node t) {
    if(root != NULL) return 0;

    node *p;
    p = new node;
    (*p) = t;

    p->left = NULL;
    p->right = NULL;
    root = p;
    node_cnt++;

    return 1;
}

insert_root는 이진트리(binary tree) root에 원소를 넣는 함수입니다.

 

if( root != NULL) return 0;

root에 NULL인지 아닌지부터 파악합니다.

 

node *p; p = new node;

원소를 추가할 때마다 node의 자리(메모리)를 만들어줘야 됩니다.

이 코드가 바로 node의 새로운 자리를 만들어주는 코드입니다.

 

p->left = NULL; p->right = NULL;

new node의 left child와 right child 모두 NULL로 만들어줍니다.

 

root = p;

root에 new node를 넣고,

 

node_cnt++;

node의 개수를 증가시켜줍니다.

 

 

int binary_tree::insert_left(string tname, node tnode) {
    int result;

    result = node_insert_left(root, tname, tnode);
    if(result == 1) 
        node_cnt ++;
    return result;
}

int binary_tree::insert_right(string tname, node tnode) {
    int result;

    result = node_insert_right(root, tname, tnode);
    if(result == 1)
        node_cnt++;
    return result;
}

insert_left(or insert_right)는 파라미터(parameter)로 들어온 문자열과 일치하는 node를 찾아

left child(or right child)에 원소가 추가되면 node_cnt를 증가시켜주는 함수입니다.

 

이 코드를 리뷰하기 위해서는 node_insert_left 함수도 알아야 됩니다.

아래 바로 아래에 있는 코드를 먼저 보고 와주세요!

 

(보고 오셨나요?)

node_insert_left 함수가 node 추가를 성공했다면 1을 return합니다.

 

if(result == 1) node_cnt++;

result의 값이 1이면 node_cnt의 값을 하나 증가시킵니다.

 

 

int node_insert_left(node *p, string tname, node tnode) {
    int result;

    if(p == NULL) return 0;
    if(p->name == tname) {
        if (p->left != NULL) return -1;

        node *t;
        t = new node;
        (*t) = tnode;

        t->left = NULL;
        t->right = NULL;
        p->left = t;

        return 1;
    } else {
        result = node_insert_left(p->left, tname, tnode);
        if(result != 0) 
            return result;
        return node_insert_left(p->right, tname, tnode);
    }
}

int node_insert_right(node *p, string tname, node tnode) {
    int result;

    if(p == NULL) return 0;
    if(p->name == tname) {
        if(p->right != NULL) return -1;

        node *t;
        t = new node;
        (*t) = tnode;

        t->left = NULL;
        t->right = NULL;
        p->right = t;

        return 1;
    } else {
        result = node_insert_right(p->left, tname, tnode);
        if(result != 0) return result;
        return node_insert_right(p->right, tname, tnode);
    }
}

 

node_insert_left(or node_insert_right)는 파라미터(parameter)로 들어온

문자열과 일치하는 node를 찾아 left child(or right child)에 원소를 넣어주는 함수입니다.

 

 

함수의 파라미터(parameter)를 먼저 살펴보겠습니다.

node *p;

이 함수는 binary_tree class의 함수가 아니기 때문에 tree의 구조를 파라미터(parameter)로 넘겨줍니다.

 

string tname;

left child에 node를 추가하기 위해 tname이라는 문자열을 찾게 됩니다.

 

node tnode;

추가될 new node입니다.

 

 

코드입니다.

if(p == NULL) return 0;

root가 존재하지 않으면 0을 return 합니다.

 

if(p->name == tname)

root가 존재하고 파라미터(parameter)로 들어온 문자열과 일치한 경우입니다.

 

if(p->left != NULL) return -1;  (or if(p->right != NULL) return -1)

root가 존재하고 파라미터(parameter)로 들어온 문자열과 일치한 경우를 찾았지만

이미 left child(or right child)가 존재하면 -1을 return 합니다.

 

 

<insert_root 코드 참고>

 

 

t->left = NULL; t->right = NULL;

new node의 left child와 right child를 NULL로 셋팅해주고,

 

p->left = t;  (or p->right = t;)

파라미터(parameter)로 들어온 문자열과 일치하는 노드(node) left child(or right child)에 new node를 넣어주고,

 

return 1;

성공의 표시로 1을 return 해줍니다.

 

이제부터 recursion 파트입니다.

 } else {

root가 존재하고 파라미터(parameter)로 들어온 문자열과 일치하는 node를 찾지 못한 경우입니다.

 

 

result = node_insert_left(p->left, tname, tnode);

(or result = node_insert_right(p->left, tname, tnode);)

파라미터(parameter)로 들어온 문자열과 일치하는 node를 찾을 때까지 자기 자신(함수)을 호출하며

계속해서 일치하는 node를 찾습니다.

 

left child에서 파라미터(parameter)로 들어온 문자열과 일치하는 node를 찾는 코드입니다.

if(result != 0) return result;

돌아온 결과가 0이 아니면 그대로 result를 돌려주고,

return node_insert_left(p->right, tname, tnode);

(or return node_insert_right(p->right, tname, tnode);)

파라미터(parameter)로 들어온 문자열과 일치하는 node를 찾을 때까지 자기 자신(함수)을 호출하며

계속해서 일치하는 node를 찾습니다.

 

right child에서 파라미터(parameter)로 들어온 문자열과 일치하는 node를 찾는 코드입니다.

 

 

 

 

double binary_tree::score_sum() {
    return sum_allnodes(root);
}

socre_sum은 sum_allnodes의 값을 return 해줍니다.

sum_allnodes는 binary_tree의 함수가 아니기 때문에 score_sum함수에서

접근 가능한 트리의 데이터를 파라미터(parameter)로 넘겨주는 역할을 합니다.

 

 

 

double sum_allnodes(node *p) {
    if(p == NULL) return 0;
    else return sum_allnodes(p->left) + sum_allnodes(p->right) + p->score;
}

sum_allnodes는 파라미터(parameter)로 들어온 트리(tree) score 데이터들의 총합을 구해주는 함수입니다.

 

여기서도 recursion을 사용합니다.

if(p == NULL) return 0;

node가 더이상 존재하지 않을 때 recursion을 끝내는 코드입니다.

 

else return sum_allnodes(p->left) + sum_allnodes(p->right) + p->score;

트리의 left child, right child를 돌아보면서 모든 node의 데이터를 더해줍니다.

 

 

 

double binary_tree::score_average() {
    return score_sum()/node_cnt;
}

score_average는 트리(tree) score 데이터들의 평균을 구해주는 함수입니다.

앞서 만들어둔 score_sum() 함수를 사용해서 node 데이터의 총합을 구하고 노드의 개수로 나눠주며 평균을 구해줍니다.

 

 

void binary_tree::print_data_inorder() {
    inorder_print(root);
}
void binary_tree::print_data_preorder() {
    preorder_print(root);
}
void binary_tree::print_data_postorder() {
    postorder_print(root);
}

각각의 함수는 binary_tree class의 private root 데이터를 파라미터로 보내주는 역할을 하게 됩니다.

 

 

void inorder_print(node *p) {
    if(p == NULL) return ;

    inorder_print(p->left);
    cout << p->name << " : " << p->score << endl;
    inorder_print(p->right);
}
void preorder_print(node *p) {
    if(p == NULL) return ;

    cout << p->name << " : " << p->score << endl;
    preorder_print(p->left);
    preorder_print(p->right);
}
void postorder_print(node *p) {
    if(p == NULL) return ;

    postorder_print(p->left);
    postorder_print(p->right);
    cout << p->name << " : " << p->score << endl;
}

inorder, preorder, postorder 맞춰서 트리를 traversal하는 함수들입니다.

 

 

if(p == NULL) return ;

더이상 읽을 node가 없으면 함수를 끝내줍니다.

 

inorder_print(p->left); preorder_print(p->left); postorder_print(p->left);

inorder_print(p->right); preorder_print(p->right); postorder_print(p->right);

이 코드들이 inorder, preorder, postorder 순서에 맞춰서 들어가면 됩니다.

 

cout << p->name << " : " << p->score << endl;

node의 데이터를 출력하는 코드입니다.

 

main 함수 구현

---

int main(){
    binary_tree bt;
    node  tmp;
    tmp.set_data("A", 8.1);
    bt.insert_root(tmp);
    tmp.set_data("B", 6.5);
    bt.insert_left("A", tmp);
    tmp.set_data("C", 8.3);
    bt.insert_right("A", tmp);
    tmp.set_data("D", 7.2);
    bt.insert_left("B", tmp);
    tmp.set_data("E", 9.0);
    bt.insert_right("B", tmp);
    tmp.set_data("F", 7.7);
    bt.insert_right("C", tmp);

    cout<< "Score Sum : " << bt.score_sum() << "\n";
    cout<< "Score Average : " << bt.score_average() << "\n";
    cout <<"\n Inorder Traversal Result \n";
    bt.print_data_inorder();
    cout << "\n Preorder Traversal Result \n";
    bt.print_data_preorder();
    cout << "\n Postorder Traversal Result \n";
    bt.print_data_postorder();
    
    return 0;  
}

결과가 잘 나오는 것을 확인할 수 있습니다.

 

 

↓↓↓         Tree traversal       ↓↓↓

https://yyyeji.tistory.com/371

[DS] 트리순회(Binary tree Traversal)란?

 

 

 

◡̈