이진트리

이진트리 탐색 알고리즘

• 트리의 탐색은 트리의 각 노드를 방문하는 작업을 말한다.

 👉 다음과 같은 방법들을 생각해 볼 수 있다.

1. 레벨 순 : 레벨이 낮은 순으로 방문
2. 왼쪽 트리 L→ A → 오른쪽 트리 R (중위 탐색)
3. A→왼쪽 트리 L → 오른쪽 트리 R (전위 탐색)
4. 왼쪽 트리 L → 오른쪽 트리 R → A (후위 탐색)

중위 탐색(inorder traversal)

• 왼쪽 트리 → 루트 노드 → 오른쪽 트리 순으로 방문
• 주의점 : 왼쪽 트리를 방문할 때 왼쪽 트리 자체가 트리이기 때문에 왼쪽 트리 안에서도 다시 중위 탐색을 한다.
  • 왼쪽 트리로 간 다음 왼쪽 트리의 왼쪽 트리, 왼쪽 트리의 루트노드, 왼쪽 트리의 오른쪽 트리 순이 된다.

예시 1

중위 탐색을 하면

1. 왼쪽 트리(B D E H 0, 루트(A), 오른쪽 트리(C F G)이기 때문에 왼쪽 트리를 방문해야 한다.
2. 왼쪽 트리(B D E H I)가 트리를 구성하기 때문에 왼쪽 트리를 다시 중위 방문을 하면 다음과 같은 방법들을 생각해 볼 수 있습니다. 왼쪽 트리 ( H D I), 루트(B), 오른쪽 트리(E)
3. 다시 왼쪽 트리를 (H D I)를 중위 탐색을 하면 왼쪽 트리(H), 루트(D), 오른쪽 트리(I)가 된다.
4. 왼쪽 트리(H)를 중위탐색을 하면 왼쪽(없음), 루트노드(H), 오른쪽트리(없음)이 되기 때문에 H가 결과가 되고 출력된다(출력 =〉 H)
5. 3번으로 돌아가서 루트방문(출력 =〉 HD)하고, 오른쪽 트리(I)를 다시 중위 탐색을 한다.
6. 오른쪽 트리(I)를 중위탐색을 하면 왼쪽(없음), 루트노드(|), 오른쪽 트리(없음)이 되기 때문에 I가 결과가 되고 출력된다(출력 =〉 HD I)
7. 3번이 끝났으므로 2번에서 루트방문(줄력 =〉 HDIB) 오른쪽 트리(E)를 방문한다(출력 =〉 HDIBE)
8. 2번이 끝나면 1 번의 루트방문(출력 =〉 HDIBEA)하고 1 번의 오른쪽 트리를 방문한다.
9. 1 번의 오른쪽을 마찬가지 중위 탐색을 하면 결과는→ HDIBEAFCG 가 된다.

중위탐색 알고리즘

순환 알고리즘이 간단하다

 

👉 void inorer(tree_ptr ptr){ if (ptr){ inorder(ptr→left_child); printf(”%d”, ptr→data); inorder(ptr→right_child);}}

 

전위 탐색

• 루트노드 → 왼쪽 트리 → 오른쪽 트리 순으로 방문을 하게된다.
• 중위 탐색과 마찬가지로 왼쪽트리를 방문할 때 왼쪽 트리 자체가 트리이기 때문에 왼쪽 트리에서도 다시 전위 탐색을 한다.
• 왼쪽 트리의 루트 노드, 왼쪽 트리의 왼쪽 트리, 왼쪽 트리의 오른쪽 트리 순이 된다.
• 노드가 1개 있는 트리는 그냥 왼쪽, 오른쪽 트리가 없기 때문에 바로 방문을 한다.

알고리즘

void preorder(tree_ptr ptr){
if (ptr){
printf(”%d”, ptr→data);
preorder(ptr→left_child);
preorder(ptr→right_child);}}

후위 탐색

• 왼쪽 트리 → 오른쪽 트리 → 루트 노드 순으로 방문을 하게 된다. 중위 탐색과 마찬가지로 왼쪽 트리를 방문할 때 왼쪽 트리자체가 트리이기 때문에 왼쪽 트리에서도 다시 후위 탐색을 한다.
• 왼쪽 트리의 왼쪽 트리, 왼쪽 트리의 오른쪽 트리 왼쪽 트리의 루트 노드 순이 된다. 노드가 1개 있는 트리는 그냥 왼쪽, 오른쪽 트리가 없기 때문에 바로 방문을 한다.

알고리즘

void postorder(tree_ptr ptr){
if (ptr){

postorder(ptr→left_child);
postorder(ptr→right_child);
printf(”%d”, ptr→data);}}

반복적 중위 탐색 알고리즘

트리 탐색을 꼭 순환 알고리즘으로 작성해야 하는 것은 아니다

void iter_inorder(tree_ptr node){
	int top = -1;
	tree_ptr stack[MAX_SIZE];
	while(1){
		while(node){
			push(&top, node);
			node=node -> left_child; }
		node =pop(&top);
		if(!node) break;
		printf("%d", node -> data);
		node = node -> right_child;
}}

level order traversal(레벨 탐색)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

• 레벨 탐색은 queue 처럼 탐색이 이뤄진다.

void level_order(tree_ptr ptr) {

	int front = rear = 0;
	tree_ptr queue[MAX_SIZE] ;
	if (!ptr) return;
	add(front ,&rear ,ptr);
	for(;;) {
		ptr= delete(&front, rear);
		if(ptr) {
			printf("%d", ptr->data);
			if(ptr->left_child) add( front ,&rear , ptr-> left_child) ;
			if(ptr->right_child){add(front, &rear ,ptr->right_child);}
		else break;
	}
}

쓰레드(Threaded) 이진 트리

• 100개의 노드의 경우 200개의 링크를 갖게 된다. 이 중 반절이 null 이며 동시에 버려지는 공간이다.
• recursive 프로그램은 간단하다 함수호출이 많아질 경우 속도가 느려진다.
• 트리의 전체 노드 수는 N개이고 링크의 수는 2N 개이며 이 중 N+1개의 링크는 비어있게 된다. 이 N+1 개의 링크를 활용하는 것을 thread 라고 한다.

쓰레드 만들기

• 비어있는 링크 값이 왼쪽인지 오른쪽인지에 따라 다음과 같이 구축한다.

1. 왼쪽 링크가 비어있으면 (if ptr→left_child is null)
   • 노드의 링크 값을 중위 탐방 순서의 바로 전 노드값을 저장한다.
2. • 노드의 링크 값을 중위 탐방 순서의 바로 다음 노드 값을 저장한다.오른쪽 링크가 비어있으면( if ptr→ right_child is null)

• 노드의 링크에 저장된 값이 자식 노드에 대한 포인터인지 쓰레드인지 구분을 어떻게 하는가?
  • ptr->left_thread = true
  • ptr->left_child 가 thread 값일 경우
  • ptr->left_thread= FALSE
  • ptr->left_child가 왼쪽 자식일 경우
  • ptr->right_thread = TRUE
  • ptr->right_child 가 thread 값일 경우
  • ptr->right_thread = FALSE
  • ptr->right_child 가 오른쪽 자식일 경우
• ⇒ 필드를 두어 표시하여야 한다.

쓰레드 트리를 위한 노드의 선언과 구조

left_thread left_child data right_child right_thread

struct tnode{
	short int left_thread;
	struct tnode *left_child;
	char data;
	struct tnode *right_child;
	short int right_thread;
};

typedef struct tnode threaded_tree;
typedef threaded_tree *threaded_ptr;

머리노드

left_thread left_child data right_child right_thread

True

←

-

→

false

쓰레드 트리에서는 왼쪽 끝과 오른쪽 끝의 두 노드는 가리킬 곳이 없으므로 전체 트리를 관리하는 머리노드(헤드노드, head node)를 둔다. 트리가 비어있어도 머리노드는 남아있게 된다.

 

쓰레드 트리의 중위 탐색

• 이진 트리를 쓰레드 트리로 바꾼 후에는 중위 탐색을 편하게 할 수 있다.
• 자식 노드가 있으면 자식 노드에 대한 링크 값을 바로 알 수 있고 자식노드가 없으면 쓰레드 링크에 다음 방문지 링크 값이 포함되어 있으므로 역시 바로 찾을 수 있따.

알고리즘

1. 임의의 노드의 다음 방문 링크를 찾는 insucc() 함수를 만들어보자
2. find the inorder successor of ptr - if ptr -> right_thread=True, then ptr-> right_child - otherwise follow a path of left-child links form the right-child of ptr until we reach a node with left_thread=True}
3. 쓰레드 트리의 중위 탐색에 대한 다음 노드 값 찾기
   • 노드의 포인터 값 tree를 인자로 주면 반환되는 값은 주위 탐색의 다음 방문노드이다.

   thread_ptr insucc(threaded_ptr tree){
   	threaded_ptr temp;
   	temp=tree->right_thread
   	if (!tree->right_thread)
   		while(!temp->left_thread)
   			temp=temp->left_child;
   	return temp;
   }
   
   

4. 쓰레드 트리의 중위 탐색 알고리즘
   • 쓰레드 트리의 중위 탐색 알고리즘은 루트노드에서 시작하여서 다음 노드를 계속 찾아나가면 된다.

   void tinorder(threaded_ptr tree){
   	threaded_ptr temp=tree;
   	for(;;){
   		temp=insucc(temp);
   		if(temp==tree) break;
   		printf("%3c", temp=>data);
   }
   }
   

쓰레드 이진트리에 새로운 노드를 첨가한다면 어떻게 될까?

•알고리즘 insert-right() : 쓰레드 트리에서 노드의 오른쪽자식노드 삽입

1) parent—right—threaded 를 FALSE 로 변경
2) child—>left thread 과 child—>right—thread 들 TRUE 로 변경
3) child—>left child 를 parent 로 변경
4) child—>right_child 를 parent—>right_child 로 변경
5) parent—right—child 를 child 로 변경

이진트리를 다루는 알고리즘

이진트리 복사

• 이진트리가 있을 때 똑같은 모양의 이진트리를 만든다면?
  • 트리를 탐색하면서 새로운 노드를 만날 때마다 노드를 복사하여야 한다.

  tree_ptr copy(tree_ptr original){
  tree_ptr temp;
  if(original){
  	temp=(tree_ptr)malloc(sizeof(node));
  	temp->left_child=copy(original->left_child);
  	temp->right_child=copy(original->right_child);
  	temp->data=copy(original->data);
  	return temp;
  	}
  return NULL;
  }
  

  

이진트리 동등비교

• 두개의 이진트리가 있을 때 두 이진트리가 모양과 노드에 값이 똑같은지 비교하려면?
• 두 개의 이진트리를 탐색하면서 노드를 만날 때 마다 두 트리의 노드의 값을 비교하면 된다.

int equal(tree_ptr first, tree_ptr second){
return ((!first && !second) ||
		(first -> data ==second -> data)
		&& equal(first-> left_child, second->left_child)
		&& equal(first-> right_child, second -> right_child)));

Q&A

Q 9.1

1. 다음 순환 프로그램의 결과는?

void fun(int n)
{
if(n>0){

fun(n — 1);
printf("%d",n);
fun(n — 1);
}}

int main()

{ fun(4); return O; }

121322141213121

void f(int k)
{
if(k==0)return;
printf("%d", k);
f(k-l);
printf("%d", k);
f(k-l);
printf("%d", k);}

void main( )
{
int i =4;
f(i);
}

432111211123211121112343211121112321112111234

 

/* DBLAB treecreate.c */
#include <stdio.h>
#include <malloc.h>

struct tnode {
	int data;
	struct tnode * left_child;
	struct tnode * right_child;
};
typedef struct tnode node;
typedef node *tree_ptr;

tree_ptr insert(tree_ptr head, int *number)
{
	tree_ptr tnodes[9];
	tree_ptr temp = NULL;
	int i = 0;

	for (i = 0; i < 9; i++)
	{
		tnodes[i] = (tree_ptr)malloc(sizeof(node));
		tnodes[i]->data = number[i];
		tnodes[i]->left_child = tnodes[i]->right_child = NULL;
	}

	head = tnodes[0];
	**//root
	tnodes[0]->left_child = tnodes[1];
	tnodes[0]->right_child = tnodes[2];
	//level 1
	tnodes[1]->right_child = tnodes[4];
	tnodes[1]->left_child = tnodes[3];
	
	tnodes[2]->right_child = tnodes[5];

	//level 2
	
	tnodes[4]->left_child = tnodes[6];
	tnodes[4]->right_child = tnodes[7];

	tnodes[5]->left_child = tnodes[8];**

	return head;

}

void preorder() {
	//전위 탐색
	if (ptr)
	{
		printf("%d ", ptr->data);
		preorder(ptr->left_child);
		preorder(ptr->right_child);
	}
}

void postorder() {
	//후위 탐색
	if (ptr)
	{
		postorder(ptr->left_child);
		postorder(ptr->right_child);
		printf("%d ", ptr->data);
	}
}

int treesum() {
	//모두 더하는 함수를 만들기
	int count = 0;
	treesum();
	return count;
}

void inorder(tree_ptr ptr)
{
	if (ptr)
	{
		inorder(ptr->left_child);
		printf("%d ", ptr->data);
		inorder(ptr->right_child);
	}
}

int main()
{
	int i, number[9] = { 2,7,5,2,6,9,5,11,4 };
	tree_ptr head = NULL;
	/* 데이터 9개 로 트리를 구성 */
	head = insert(head, number); //중위 탐색

	/* 중위탐색 */
	printf("중위탐색: ");
	inorder(head);
	printf("\\n전위탐색: ");
	preorder(head);
	printf("\\n후위탐색: ");
	postorder(head);

	int count = 0;
	int k = 0;
	for (int i = 0; i < 9; i++) {
		count += number[i];
		k++;
	}

	printf("\\n sum=%d \\n count=%d", count, k);

}