[C언어로 쉽게 풀어쓴 자료구조] 8장 트리

8.1 트리의 개념

• 노드(node) : 트리의 구성요소
• 루트(root) : 부모가 없는 노드 
• 서브트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리
• 단말노드(terminal node) : 자식이 없는 노드
• 비단말노드 : 적어도 하나의 자식을 가지는 노드
• 레벨(level) : 트리의 각층의 번호
• 높이(height) : 트리의 최대 레벨
• 차수(degree) : 노드가 가지고 있는 자식 노드의 개수

8.2 이진 트리 소개

이진트리의 정의

• 모든 노드가 2개의 서브 트리를 가지고 있는 트리
• 서브트리는 공집합 일 수 있따.
• 이진트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수가 2이하

이진트리의 성질

• n개의 노드를 가진 이진트리 n-1의 간선을 가짐
• 높이가 h인 이진트리의 경우 최소 h개의 노드를 가지며 최대 2^h-1개의 노드를 가짐.
• 레벨i에서의 노드의 최대 개수는 2^(i-1) (→ 하나의 노드는 최대 2개의 자식을 가질 수 있기 때문)
• n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소[log2(n+1)]

이진트리의 성질

• 포화 이진 트리 (full binary tree)
• 완전 이진 트리 (complete binary tree)
• 기타 이진 트리

8.3 이진 트리 표현

배열 표현법

배열 표현법에서 부모와 자식의 인덱스의 관계

• 노드 i의 부모 노드 인덱스 = i/2
• 노드 i의 왼쪽 자식 노드 인덱스 = 2i
• 노드 i의 오른쪽 자식 노드 인덱스 =2i+1

링크 표현법

링크법으로 표현된 트리는 루트 노드를 가리키는 포인터만 있으면 트리안의 모든 노드들에 접근할 수있다.

typedef struct TreeNode{
	int datal
	struct TreeNode *left, *right;
} TreeNode;

 

8.4 이진 트리의 순회

이진 트리 순회 방법 

이진트리를 순회하는 표준적인 방법에는 전위, 중위, 후위의 3가지 방법이 있다.

이는 루트와 왼쪽 서브트리, 오른쪽서브트리 중에서 루트를 언제 방문하느냐에 따라 구분된다.

전위순회 (preorder traversal) : VLR

중위순회 (inorder traversal) : LVR

후위순회 (postorder traversal) : LRV

 

전위, 중위, 후위 순회 구현

// 8.2  이진트리의 3가지 순회방법

// 중위 순회
void inorder(TreeNode *root){
    if (root != NULL){
        inorder(root->left);            // 왼쪽 서브 트리 순회
        printf("[%d] ", root->data);    // 노드 방문
        inorder(root->right);           // 오른쪽 서브 트리 순회
    }
}
// 전위 순회
void preorder(TreeNode *root){
    if (root != NULL){
        printf("[%d] ", root->data);    // 노드 방문
        preorder(root->left);           // 왼쪽 서브 트리 순회
        preorder(root->right);          // 오른쪽 서브 트리 순회
    }
}
// 후위 순회
void postorder(TreeNode *root){
    if (root != NULL){
        postorder(root->left);           // 왼쪽 서브 트리 순회
        postorder(root->right);          // 오른쪽 서브 트리 순회
        printf("[%d] ", root->data);    // 노드 방문
    }
}

8.5 반복적 순회