08장 트리(Tree) – 이진트리(Binary Tree), 순회(Traverse)

Posted on: 2019년 03월 31일 2019년 03월 31일
Categories: 강의자료, 자료구조

트리 관련 용어
1. 노드(node)
2. 간선(edge)
3. 루트노드(root node)
4. 단말노드(terminal node)
5. 내부노드(internal node)
6. 차수(degree)
7. 레벨(level)
8. 높이(height) = 깊이 를 사용하기도 함
차트 관련 문제 : 그림 출처(https://ko.wikipedia.org/wiki/트리_순회)
1. 다음 트리를 보고 답하시오.
2. 위 트리의 차수는?
3. 위 트리를 Preorder 운행법으로 운행할 경우 다섯 번째로 탐색 되는 것은?
4. 위 트기의 터미널 노드 수는?
5. 위 트기의 내부 노드 수는?
6. 위 트리에 대한 inorder 운행 결과는?
7. 깊이가 5인 이진트리에서 가질 수 있는 최대 노드 수는?
트리 종류
1. 이진트리(Binary Tree)과 서브트리(Sub Tree)
2. 포화이진트리(Full Binary Tree)과 완전이진트리(Complete Binary Tree)
  1. 레벨(level)
  2. 높이(height) = 깊이 를 사용하기도 함

이진트리의 순회(Traversal)

전위순회(Preorder Traversal) : root, left, right
중위순회(Inorder Traversal) : left, root, right
후위순회(Postorder Traversal) : left, right, root
예제 1 : 그림 출처(https://ko.wikipedia.org/wiki/트리_순회)
1. 전위 순회 : F B A D C E G I H
2. 중위 순회 : A B C D E F G H I
3. 후위 순회 : A C E D B H I G F
4. 레벨 순서 순회 : F B G A D I C E H

예제 2 : 수식 트리(Expression Tree)

중위(Inorder)   		전위(preorder)		후위(postorder)
5 + 2 / 7     		+ 5 / 2 7		5 2 7 / +
(1 + 2) * 7   		* + 1 2 7		1 2 + 7 *
(1 + 2 * 3) / 4		/ + 1 * 2 3		1 2 3 * + 4 /

중위(Inorder) 전위(preorder) 후위(postorder)

5 + 2 / 7 + 5 / 2 7 5 2 7 / +

(1 + 2) * 7 * + 1 2 7 1 2 + 7 *

(1 + 2 * 3) / 4 / + 1 * 2 3 1 2 3 * + 4 /

연결리스트를 이용한 이진 트리(Binary Tree) 완성버전 : S008_BinaryTree.c

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

typedef struct _bTreeNode{
	int data;
	struct _bTreeNode * left;
	struct _bTreeNode * right;
} BTreeNode;

BTreeNode * MakeBTreeNode(void){
	BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

	nd->left = NULL;
	nd->right = NULL;
	return nd;
}

int GetData(BTreeNode * bt){
	return bt->data;
}

void SetData(BTreeNode * bt, int data){
	bt->data = data;
}

BTreeNode * GetLeftSubTree(BTreeNode * bt){
	return bt->left;
}

BTreeNode * GetRightSubTree(BTreeNode * bt){
	return bt->right;
}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub){
	if(main->left != NULL)
		free(main->left);

	main->left = sub;
}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub){
	if(main->right != NULL)
		free(main->right);

	main->right = sub;
}

int main(void){
	BTreeNode * bt1 = MakeBTreeNode();
	BTreeNode * bt2 = MakeBTreeNode();
	BTreeNode * bt3 = MakeBTreeNode();
	BTreeNode * bt4 = MakeBTreeNode();

	SetData(bt1, 1);
	SetData(bt2, 2);
	SetData(bt3, 3);
	SetData(bt4, 4);

	MakeLeftSubTree(bt1, bt2);
	MakeRightSubTree(bt1, bt3);
	MakeLeftSubTree(bt2, bt4);

	printf("%d\n", GetData(GetLeftSubTree(bt1)));
	printf("%d\n", GetData(GetLeftSubTree(GetLeftSubTree(bt1))));

	free(bt4);
	free(bt3);
	free(bt2);
	free(bt1);

	return 0;
}

#include <stdio.h>

#include <stdlib.h>

typedef struct _bTreeNode{

int data;

struct _bTreeNode * left;

struct _bTreeNode * right;

} BTreeNode;

BTreeNode * MakeBTreeNode(void){

BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

nd->left = NULL;

nd->right = NULL;

return nd;

}

int GetData(BTreeNode * bt){

return bt->data;

}

void SetData(BTreeNode * bt, int data){

bt->data = data;

}

BTreeNode * GetLeftSubTree(BTreeNode * bt){

return bt->left;

}

BTreeNode * GetRightSubTree(BTreeNode * bt){

return bt->right;

}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub){

if(main->left != NULL)

free(main->left);

main->left = sub;

}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub){

if(main->right != NULL)

free(main->right);

main->right = sub;

}

int main(void){

BTreeNode * bt1 = MakeBTreeNode();

BTreeNode * bt2 = MakeBTreeNode();

BTreeNode * bt3 = MakeBTreeNode();

BTreeNode * bt4 = MakeBTreeNode();

SetData(bt1, 1);

SetData(bt2, 2);

SetData(bt3, 3);

SetData(bt4, 4);

MakeLeftSubTree(bt1, bt2);

MakeRightSubTree(bt1, bt3);

MakeLeftSubTree(bt2, bt4);

printf("%d\n", GetData(GetLeftSubTree(bt1)));

printf("%d\n", GetData(GetLeftSubTree(GetLeftSubTree(bt1))));

free(bt4);

free(bt3);

free(bt2);

free(bt1);

return 0;

}

이진트리의 순회(Traverse) 기능 추가 : S008_BinaryTreeTraverse.c

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

typedef struct _bTreeNode{
	int data;
	struct _bTreeNode * left;
	struct _bTreeNode * right;
} BTreeNode;

BTreeNode * MakeBTreeNode(void){
	BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

	nd->left = NULL;
	nd->right = NULL;
	return nd;
}

int GetData(BTreeNode * bt){
	return bt->data;
}

void SetData(BTreeNode * bt, int data){
	bt->data = data;
}

BTreeNode * GetLeftSubTree(BTreeNode * bt){
	return bt->left;
}

BTreeNode * GetRightSubTree(BTreeNode * bt){
	return bt->right;
}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub){
	if(main->left != NULL)
		free(main->left);

	main->left = sub;
}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub){
	if(main->right != NULL)
		free(main->right);

	main->right = sub;
}

void PreorderTraverse(BTreeNode * bt){
	if(bt == NULL)
		return;

	printf("%d ", bt->data);
	PreorderTraverse(bt->left);
	PreorderTraverse(bt->right);
}

void InorderTraverse(BTreeNode * bt){
	if(bt == NULL)
		return;

	InorderTraverse(bt->left);
	printf("%d ", bt->data);
	InorderTraverse(bt->right);
}

void PostorderTraverse(BTreeNode * bt){
	if(bt == NULL)
		return;

	PostorderTraverse(bt->left);
	PostorderTraverse(bt->right);
	printf("%d ", bt->data);
}

int main(void){
	BTreeNode * bt1 = MakeBTreeNode();
	BTreeNode * bt2 = MakeBTreeNode();
	BTreeNode * bt3 = MakeBTreeNode();
	BTreeNode * bt4 = MakeBTreeNode();
	BTreeNode * bt5 = MakeBTreeNode();
	BTreeNode * bt6 = MakeBTreeNode();

	SetData(bt1, 1);
	SetData(bt2, 2);
	SetData(bt3, 3);
	SetData(bt4, 4);
	SetData(bt5, 5);
	SetData(bt6, 6);

	MakeLeftSubTree(bt1, bt2);
	MakeRightSubTree(bt1, bt3);
	MakeLeftSubTree(bt2, bt4);
	MakeRightSubTree(bt2, bt5);
	MakeRightSubTree(bt3, bt6);

	printf("\nPreorder : \t");	PreorderTraverse(bt1);
	printf("\nInorder : \t");	InorderTraverse(bt1);
	printf("\nPostorder : \t");	PostorderTraverse(bt1);

	free(bt6);
	free(bt5);
	free(bt4);
	free(bt3);
	free(bt2);
	free(bt1);

	return 0;
}

100

101

102

103

104

105

106

107

108

#include <stdio.h>

#include <stdlib.h>

typedef struct _bTreeNode{

int data;

struct _bTreeNode * left;

struct _bTreeNode * right;

} BTreeNode;

BTreeNode * MakeBTreeNode(void){

BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

nd->left = NULL;

nd->right = NULL;

return nd;

}

int GetData(BTreeNode * bt){

return bt->data;

}

void SetData(BTreeNode * bt, int data){

bt->data = data;

}

BTreeNode * GetLeftSubTree(BTreeNode * bt){

return bt->left;

}

BTreeNode * GetRightSubTree(BTreeNode * bt){

return bt->right;

}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub){

if(main->left != NULL)

free(main->left);

main->left = sub;

}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub){

if(main->right != NULL)

free(main->right);

main->right = sub;

}

void PreorderTraverse(BTreeNode * bt){

if(bt == NULL)

return;

printf("%d ", bt->data);

PreorderTraverse(bt->left);

PreorderTraverse(bt->right);

}

void InorderTraverse(BTreeNode * bt){

if(bt == NULL)

return;

InorderTraverse(bt->left);

printf("%d ", bt->data);

InorderTraverse(bt->right);

}

void PostorderTraverse(BTreeNode * bt){

if(bt == NULL)

return;

PostorderTraverse(bt->left);

PostorderTraverse(bt->right);

printf("%d ", bt->data);

}

int main(void){

BTreeNode * bt1 = MakeBTreeNode();

BTreeNode * bt2 = MakeBTreeNode();

BTreeNode * bt3 = MakeBTreeNode();

BTreeNode * bt4 = MakeBTreeNode();

BTreeNode * bt5 = MakeBTreeNode();

BTreeNode * bt6 = MakeBTreeNode();

SetData(bt1, 1);

SetData(bt2, 2);

SetData(bt3, 3);

SetData(bt4, 4);

SetData(bt5, 5);

SetData(bt6, 6);

MakeLeftSubTree(bt1, bt2);

MakeRightSubTree(bt1, bt3);

MakeLeftSubTree(bt2, bt4);

MakeRightSubTree(bt2, bt5);

MakeRightSubTree(bt3, bt6);

printf("\nPreorder : \t"); PreorderTraverse(bt1);

printf("\nInorder : \t"); InorderTraverse(bt1);

printf("\nPostorder : \t"); PostorderTraverse(bt1);

free(bt6);

free(bt5);

free(bt4);

free(bt3);

free(bt2);

free(bt1);

return 0;

}

whan0623

517