0405 TIL - 이진 트리 순회

순회 방식순서

전위	루트 → 왼쪽 → 오른쪽

중위	왼쪽 → 루트 → 오른쪽

후위	왼쪽 → 오른쪽 → 루트

 

//Tree.h

#pragma once
#ifndef TREE_H

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

Tree* createNode(int);
Tree* insertNode(Tree*, int);
void printInorder(Tree*);
void printPreorder(Tree*);
void printPostorder(Tree*);
#endif // !TREE_H

 

//TreeFunc.c

#include <stdio.h>
#include <stdlib.h>
#include "Tree.h"

Tree* createNode(int value)
{
	Tree* newNode = (Tree*)malloc(sizeof(Tree));
	newNode->data = value;
	newNode->left = NULL;
	newNode->right = NULL;

	return newNode;
}

Tree* insertNode(Tree* tree, int value)
{
	Tree* currentTree = tree;

	if (currentTree == NULL)
	{
		return createNode(value);
	}

	if (currentTree->data > value)
	{
		currentTree->left = insertNode(currentTree->left, value);
	}
	else
	{
		currentTree->right = insertNode(currentTree->right, value);
	}
	return tree;
}

void printInorder(Tree* root) //중위 순회
{
	if (root == NULL) return;

	printInorder(root->left);
	printf("%d ", root->data);
	printInorder(root->right);
}

void printPreorder(Tree* root) //전위 순회
{
	if (root == NULL) return;

	printf("%d ", root->data);
	printPreorder(root->left);
	printPreorder(root->right);
}

void printPostorder(Tree* root) //후위 순회
{
	if (root == NULL) return;

	printPostorder(root->left);
	printPostorder(root->right);
	printf("%d ", root->data);
}

 

 

오늘의 학습 포인트

• 전위: 트리 구조 저장 (복원용, 직렬화)
• 중위: 정렬된 값 출력 (이진 탐색 트리용)
• 후위: 트리 삭제 (자식 먼저 해제 후 부모 제거)

구조 자체는 이전에 한 것과 크게 다르지 않다.

하지만 트리부터 재귀 함수를 적극적으로 이용하는 느낌인데

 

재귀 함수는 대충

int roundAndRoundWeGo(int root)
{
	int temp = root;
	if (temp > 10)
	{
		return temp;
	}

	else roundAndRoundWeGo(++temp);
}

 

이런건데 함수 내부에서 자신을 호출해서 해당 함수를 반복시키는 내용이다.

 

물론 탈출구는 항상 만들어둬야 한다.

 

중위 함수를 살펴보자.

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

void printInorder(Tree* root) //중위 순회
{
	if (root == NULL) return;

	printInorder(root->left);
	printf("%d ", root->data);
	printInorder(root->right);
}

 

외부에서 트리 포인터 root를 받아왔다.

 

root가 NULL이면 반환, 즉 함수가 종료된다.

   10
   /  \
  5   15

 

이런 모양의 이진트리가 있다고 했을 때에

간단하게 정수로 변환해서 설명하면

1. printInorder(10)이 실행됨. 왼쪽은 5, 오른쪽은 15

2. 함수 진행 중 printInorder(5)가 실행됨, 왼쪽은 NULL, 오른쪽도 NULL

3. 함수 진행 중 printInorder(NULL)이 실행됨, NULL값이기 때문에 return (함수종료)

4. printInorder(5)가 아직 실행 중 printf를 통해 5 값 출력 후 printInorder(NULL) (오른쪽 값) 실행

5. 함수 진행 중 printInorder(NULL)이 실행됨, NULL값이기 때문에 return (함수종료)

6. printInorder(5)가 종료됨

7. printInorder(10)이 아직 실행 중 printf를 통해 10 값 출력 후  printInorder(15) (오른쪽 값) 실행

...

 

이 되어서 출력 값이 5 10 15 순으로 낮은 수 부터 나오게 된다.

 

이제 자고 일어나서 마저 해야지