5장 TREES

트리에 관련된 용어들

• 노드의 차수 (내 일촌관계 아들의 수)
• 단말 노드 (자식이 없는 노드)
• Parent, Children, Siblings
• Ancestor(조상), Descendants(자손) (M의 조상: H,D,A) (B의 자손: E,F,K,L)
• Level(루트로부터 단순 경로의 길이. 루트가 1임), Height or Depth (4)

---

트리의 표현

Left Child - Right Sibling 표현

왼쪽노드 - 자식, 오른쪽 노드 - 형제

이 때 모든 노드의 차수가 2 이하가 되는데, 

이런 트리를 이진 트리라고 함.

 

이진 트리

• 이진트리의 모든 노드의 차수(degree)는 2를 넘지 않는다. ==> 두개를 초과하여 쪼개지지 않음
• 왼쪽 서브트리와 오른쪽 서브트리가 구분

편향 트리와 완전 이진트리

완전 이진트리는 포화 이진 트리(full binary tree)로 가는 과정에 있는 트리도 포함된다. (순서가 맞을 시)

 

이진 트리의 성질

최대 노드 수

이진 트리의 레벨i에서 최대 노드 수는 2^(i-1)이다.

깊이가 k인 이진 트리가 가질 수 있는 최대 노드 수는 2^k -1이다. (첫 항이 1, 공비가 2일 때 k번째 항까지의 합)

 

모든 노드 수 = 단말 노드 수 + 차수가 1인 노드 수 + 차수가 2인 노드 수

==> n= n0 + n1 + n2

 

E(간선의 수) = n -1

E = 2*n2 + n1 

==> n0 = n2 +1 (단말노드의 수 = 차수가 2인 노드 +1)

---

2.3이진 트리의 표현

n개의 노드를 가진 완전 이진 트리를 배열로 표현 시

• parent(i) = i/2
• lchild(i) = 2i
• rchild(i) = 2i +1

 

링크 표현

typedef struct node *tree_pointer;
struct node{
	int data;
    struct node *left_child;
    struct node *right_child;
};

현재 값, 왼쪽자식 링크, 오른쪽자식 링크가 존재함

 

---

이진 트리 순회

세 가지 순회 방법

• 중위 순회(inorder traversal)  Left => V => Right
• 전위 순회(preorder traversal)  V => Left => Right
• 후위 순회(postorder traversal)  Left => Right => V

 

중위 순회 (inorder traversal)

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

왼쪽노드 -> 부모노드 -> 오른쪽노드 순이다.

출력시 가장 왼쪽에 위치한 노드부터 순차적으로 나옴

수식을 표현하면 inorder 방식이 곧 infix 방식이다

 

 

전위 순회(preorder traversal)

void preorder(struct node *ptr)
{
	if(ptr){
    	printf("%d",ptr->data);
        preorder(ptr->left_child);
        preorder(ptr->right_child);
        }
}

부모노드 -> 왼쪽노드 ->오른쪽노드 순으로 출력한다.

 

 

후위 순회(postorder traversal)

void postorder(struct node *ptr)
{
	if(ptr){
    	postorder(ptr->left_child);
        postorder(ptr->right_child);
        printf("%d",ptr->data);
        }
}

왼쪽자식->오른쪽자식->부모 출력.

수식을 표현 할 때 postfix 방식이 됨

 

recursion 없이 스택과 반복문을 이용하여 inorder traversal 구현하기

void iter_inorder(struct node *node){
	int top = -1;
    struct node *stack[MAX_STACK_SIZE];
    for(;;){
    	for(;node;node=node->left_child)
        	push(node);
        node=pop();
        if(!node) break;
        printf("%d",node->data);
        node=node->right_child;
    }
}

 

Level order traversal

void level_order(struct node *ptr)
{
	int front=0, rear=0;
    struct node *queue[MAX_QUEUE_SIZE];
    if(!ptr) return;
    addq(ptr);
    for(;;){
    	ptr=deleteq();
        if(ptr==NULL) break;
        printf("%d",ptr->data);
        if(ptr->left_child)
        	addq(ptr->left_child);
        if(ptr->right_child)
        	addq(ptr->right_child);
    }
}

순회 순서를 2개이상 알면 이진트리를 그릴 수 있으니 한번 시도해보길 바람.

(page27)

---

이진 트리의 추가 연산

• 이진 트리의 복사
• 이진 트리의 동일성 검사
• 이진 트리의 노드 수, 단말 노드 수 계산
• 만족성 문제

이진 트리의 복사

후위 순회 알고리즘을 응용.

입력 이진 트리의 노드 구조와 동일한 새로운 이진 트리를 생성하여 루트 노드 주소를 반환

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

 

이진 트리의 동일성 검사

두 개의 이진 트리가 동일한 데이터와 동일한 구조를 갖는지 검사.

전위 순회 알고리즘을 응용

int equal(struct node *first, struct node *second)
{
	return ((!first&& !second)||first&&second&&(first->data==second->data)
    &&equal(first->left_child,second->left_child)&&
    equal(first->right_child,second->right_child)))
}

 

이진 트리의 노드 수 계산

루트 노드가 NULL이면 0을, NULL이 아니면 1+왼쪽 서브트리의 노드 수 + 오른쪽 서브트리의 노드 수를 반환

int get_node_count(struct node *ptr)
{
	int count=0;
    if(ptr!=NULL)
    	count=1+get_node_count(ptr->left_child)+get_node_count(ptr->right_child);
    return count;
}

이진 트리의 단말 노드 수 계산

int get_leaf_count(struct node *ptr)
{
	int count=0;
    if(ptr!=NULL){
    	if(ptr->left_child==NULL && ptr->right_child==NULL)
        	return 1;
        else
        	count=get_leaf_count(ptr->left_child)+get_leaf_count(ptr->right_child);
        }
    return count;
}

 

만족성 문제