자료구조 - 트리

트리 : 계층적인 구조를 나타내는 자료구조( 부모- 자식 등의 관계들이 나타남)

<트리의 용어>

• 노드(node) : 트리의 구성요소
• 루트(root) : 부모가 없는 노드(가장 위의 노드)
• 서브트리(subtree) : 하나의 노드와 자손들로 이루어진 작은트리
• 단말노드(terminal) : 자식이 없는 노드
• 비단말노드 : 자식을 가지는 노드
• 간선(edge) : 노드간 연결 링크
• 레벨(level) : 트리의 각층의 번호
• 높이(height) : 트리의 최대 레벨 (부모가 레벨1)
• 차수(degree) : 노드의 자식 노드수

---

일반트리의 경우 포인터를 이용하면 너무 복잡함

그래서 이진트리(binary tree)를 사용

1. 각 노드에는 최대 2개까지의 자식 노드가 존재
2. 모든 노드의 차수가 2이하
3. 서브 트리간의 순서가 존재한다
4. 이진트리는 노드의 개수가 n개이면 간선의 개수는 n-1
5. 높이는 최소 h ~ 2h-1개를 가짐 n개의 노드 => 밑이2인 log2(n+1)개

---

포화 이진트리 : 트리의 각 레벨에 노드가 꽉차있는 이진트리

완전 이진트리 : 높이가 h일 때, 레벨1부터 h-1까지 노드가 모두 채워졌고, 마지막레벨은 순서대로 채워진 이진트리

---

 

이진트리는 배열로 표현하거나, 링크로 표현가능하다

배열로 표현할 시 완전이진트리라 가정하고 각 해당 번호를 배열의 번호에 집어넣는다

링크로 표현할 시 왼쪽자식 링크, 오른쪽 자식 링크, 자신의 데이터가 존재하게 표현한다.

---

이진트리의 순회방법

순회의 방법들은 모두 재귀를 사용

1. 전위순회(preorder traversal) : VLR => 루트->왼쪽자식->오른쪽자식
2. 중위순회(inorder traversal) : LVR => 왼쪽자식->루트->오른쪽자식
3. 후위순회(postorder traversal) : LRV => 왼쪽자식->오른쪽자식->루트
4. 레벨순회(level traversal) : 왼쪽부터 레벨순서대로

#include <cstdio>

void preorder(TNode* n){
	if(n! = NULL){
        printf("[%c] ", n->data);
        preorder(n->left);
        preorder(n->right);
     }
}

void inorder(TNode* n){
	if(n! = NULL){
    	inorder(n->left);
        printf("[%c] ", n->data);
        inorder(n->right);
     }
}

void postorder(TNode* n){
	if(n! = NULL){
    	postorder(n->left);
        postorder(n->right);
        printf("[%c] ", n->data);
     }
}

// 이진트리의 노드 개수 연산

//트리의 노드 개수를 구하는 함수
int getCount() { return isEmpty() ? 0 : getCount(root); }

// 순환 호출에 의해 node를 루트로 하는 서브트리의 노드 수 계산
int getCount(BinaryNode* node){
	if( node == NULL ) { return 0; }
    return 1 + getCount(node->getLeft()) + getCount(node->getRight());
}

// 이진트리의 높이 구하는 연산

//트리의 높이를 구하는 함수
int getHeight() { return isEmpty() ? 0 : getHeight(root); }

// 순환 호출에 의해 node를 루트로 하는 서브트리의 높이 계산 함수
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;
}