Cohe
이진트리 본문
728x90
이진트리 탐색 알고리즘
- 트리의 탐색은 트리의 각 노드를 방문하는 작업을 말한다.
👉 다음과 같은 방법들을 생각해 볼 수 있다.
- 레벨 순 : 레벨이 낮은 순으로 방문
- 왼쪽 트리 L→ A → 오른쪽 트리 R (중위 탐색)
- A→왼쪽 트리 L → 오른쪽 트리 R (전위 탐색)
- 왼쪽 트리 L → 오른쪽 트리 R → A (후위 탐색)
중위 탐색(inorder traversal)
- 왼쪽 트리 → 루트 노드 → 오른쪽 트리 순으로 방문
- 주의점 : 왼쪽 트리를 방문할 때 왼쪽 트리 자체가 트리이기 때문에 왼쪽 트리 안에서도 다시 중위 탐색을 한다.
- 왼쪽 트리로 간 다음 왼쪽 트리의 왼쪽 트리, 왼쪽 트리의 루트노드, 왼쪽 트리의 오른쪽 트리 순이 된다.
예시 1
중위 탐색을 하면
- 왼쪽 트리(B D E H 0, 루트(A), 오른쪽 트리(C F G)이기 때문에 왼쪽 트리를 방문해야 한다.
- 왼쪽 트리(B D E H I)가 트리를 구성하기 때문에 왼쪽 트리를 다시 중위 방문을 하면 다음과 같은 방법들을 생각해 볼 수 있습니다. 왼쪽 트리 ( H D I), 루트(B), 오른쪽 트리(E)
- 다시 왼쪽 트리를 (H D I)를 중위 탐색을 하면 왼쪽 트리(H), 루트(D), 오른쪽 트리(I)가 된다.
- 왼쪽 트리(H)를 중위탐색을 하면 왼쪽(없음), 루트노드(H), 오른쪽트리(없음)이 되기 때문에 H가 결과가 되고 출력된다(출력 =〉 H)
- 3번으로 돌아가서 루트방문(출력 =〉 HD)하고, 오른쪽 트리(I)를 다시 중위 탐색을 한다.
- 오른쪽 트리(I)를 중위탐색을 하면 왼쪽(없음), 루트노드(|), 오른쪽 트리(없음)이 되기 때문에 I가 결과가 되고 출력된다(출력 =〉 HD I)
- 3번이 끝났으므로 2번에서 루트방문(줄력 =〉 HDIB) 오른쪽 트리(E)를 방문한다(출력 =〉 HDIBE)
- 2번이 끝나면 1 번의 루트방문(출력 =〉 HDIBEA)하고 1 번의 오른쪽 트리를 방문한다.
- 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 라고 한다.
쓰레드 만들기
- 비어있는 링크 값이 왼쪽인지 오른쪽인지에 따라 다음과 같이 구축한다.
- 왼쪽 링크가 비어있으면 (if ptr→left_child is null)
- 노드의 링크 값을 중위 탐방 순서의 바로 전 노드값을 저장한다.
-
- 노드의 링크 값을 중위 탐방 순서의 바로 다음 노드 값을 저장한다.오른쪽 링크가 비어있으면( 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)를 둔다. 트리가 비어있어도 머리노드는 남아있게 된다.
쓰레드 트리의 중위 탐색
- 이진 트리를 쓰레드 트리로 바꾼 후에는 중위 탐색을 편하게 할 수 있다.
- 자식 노드가 있으면 자식 노드에 대한 링크 값을 바로 알 수 있고 자식노드가 없으면 쓰레드 링크에 다음 방문지 링크 값이 포함되어 있으므로 역시 바로 찾을 수 있따.
알고리즘
- 임의의 노드의 다음 방문 링크를 찾는 insucc() 함수를 만들어보자
- 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}
- 쓰레드 트리의 중위 탐색에 대한 다음 노드 값 찾기
- 노드의 포인터 값 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; } - 쓰레드 트리의 중위 탐색 알고리즘
- 쓰레드 트리의 중위 탐색 알고리즘은 루트노드에서 시작하여서 다음 노드를 계속 찾아나가면 된다.
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
- 다음 순환 프로그램의 결과는?
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);
}