[📗c언어 쉽게 풀어쓴 자료구조8] 트리

👑 트리의 개념

✔ 트리의 용어들

• 노드, 루트노드, 서브트리, 간선, 포리스트
• 조상노드: 루트노드에서 임의의 노드까지의 경로를 이루고 있는 노드들
• 후손 노드: 임의의 노드 하위에 연결된 모든 노드들
• 단말노드: 자식 노드가 없는 노드 (<-> 비단말노드)
• 차수: 노드가 가지고 있는 자식노드의 수
• 레벨: 각 층의 번호 (루트 레벨: 1)
• 높이: 트리가 가지고 있는 최대 레벨

--> 여기서는 이진트리를 자세하게 다룰 것임!

👑 이진 트리 소개

: 모든 노드가 2개의 서브트리를 가지고 있는 트리 (모든 노드의 차수가 2 이하)

• n-1개의 간선
• 높이가 h인 이진트리의 경우, 최소 h개의 노드 최대 2h-1개의 노드

✔ 이진트리의 분류

• 포화 이진트리: 각 레벨에 노드가 꽉 차있는 이진트리
• 완전 이진트리: 마지막 이전 레벨까지는 꽉 차 있고, 마지막 레벨은 왼쪽부터 순서대로 차 있는 트리

👑 이진 트리의 표현

1. 배열: 인덱스 1부터 사용
2. 포인터

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

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

int main(void)
{
	TreeNode *n1, *n2, *n3;
	n1 = (TreeNode*)malloc(sizeof(TreeNode));
	n2 = (TreeNode*)malloc(sizeof(TreeNode));
	n3 = (TreeNode*)malloc(sizeof(TreeNode));
	n1->data = 10;
	n1->left = n2;
	n1->right = n3;
	n2->data;
	n2->left = NULL;
	n2->right = NULL;
	n3->data = 30;
	n3->left = NULL;
	n3->right = NULL;
	free(n1); free(n2); free(n3);
	return 0;
}

👑 이진 트리의 순회

: 루트노드 방문 순서에 따라 (스택 사용)
1. 전위 순회: 루트를 제일 먼저 (루-왼-오)
2. 중위 순회: 왼-루-오
3. 후위 순회: 왼-오-루
--> 순환이나 반복 (스택 필요)을 통해 구현 가능

👑 레벨 순회

: 각 노드를 레벨 순으로 검사 (큐 사용)