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

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

 

8.1 트리의 개념

• 계층적인 자료를 표현하는데 적합한 자료구조

 

• 차수: 어떤 노드가 가지고 있는 자식 노드의 개수
• 계층에 따라 부모, 자식, 형제, 자손 등 관계가 만들어짐
•  

---

8.2 이진 트리 소개

• 모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree)라고 한다.
• 공집합이거나 루트와 왼쪽, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다.

 

이진 트리의 성질

• n개의 노드를 가진 이진트리는 정확하게 n-1의 간선을 가진다.
• 높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며 최대 (2^h) - 1 의 노드를 가진다.

---

8.3 이진 트리의 표현

https://seongkyun.github.io/data_structure/2019/08/01/data_structure/

CH8. 트리(Tree) 2 (이진 트리의 구현) · Seongkyun Han's blog

 

잘 설명해 주셨다.

 

 

 

링크법으로 생성된 이진 트리

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

typedef struct TreeNode {
	int data;
	struct TreeNode *left, *right;
} TreeNode;
//  		    n1
//		   / |
//		  n2  n3
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 = 20;		// 두 번째 노드를 설정한다.
	n2->left = NULL;
	n2->right = NULL;
	n3->data = 30;		// 세 번째 노드를 설정한다.
	n3->left = NULL;
	n3->right = NULL;
	free(n1); free(n2); free(n3);
	return 0;
}

 

---

8.4 이진 트리의 순회

전위 순회

1. 루트 노드 방문
2. 왼쪽 서브트리 방문
3. 오른쪽 서브트리 방문

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

 

 

중위 순회

1. 왼쪽 서브트리 방문
2. 루트 노드 방문
3. 오른쪽 서브트리 방문

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

 

 

후위 순회

1. 왼쪽 서브트리 방문
2. 오른쪽 서브트리 방문
3. 루트 노드 방문

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