[C언어로 쉽게 풀어쓴 자료구조] 8장 트리 - Ⅱ

C언어로 쉽게 풀어쓴 자료구조: 8장 트리

8.6 레벨 순회

• 큐를 사용하는 순회법
• 루트 노드의 레벨이 1이고 아래로 내려갈수록 레벨이 증가.
• 동일한 레벨의 경우 좌에서 우로 방문

void levelOrder(TreeNode *ptr)
{	
    QueueType q;
    init_quque(q); // 큐 초기화
    if(ptr == NULL) return;
   
    enqueue(&q, ptr);
    while(!is_empty(&q))
    {
    	ptr = dequeue(&);
        printf("[%d]", ptr->data);
        if(ptr->left);
        	enqueue(&q, ptr->left);
        if(ptr->right)
        	enqueue(&q, ptr->right);
    }
}

---

8.9 이진트리의 추가 연산 

노드의 개수

• 노드의 개수를 세기 위해서는 트리 안의 노드들을 전체적으로 순회해야 함
• 각 서브트리를 순환 호출한 후 반환되는 값에 1을 더해 반환한다. 

int get_node_count(TreeNode *node)
{
   int count = 0;
   
   if(node != NULL)
       count = 1+ get_node_count(node->left) +
       get_node_count(node->right);
       
   return count;
}

 

---

단말 노드 개수 구하기

• 단말노드: 자식이 없는 노드
• 단말 노드의 개수를 세기 위해서는 트리 안의 노드들을 전체적으로 순회해야 함
• 순회하면서 왼쪽 자식과 오른쪽 자식이 동시에 0이 되면 단말노드이므로 1을 반환한다.

int get_leaf_count(TreeNode *node)
{
    int couint = 0;
    if(node != NULL)
    {
    	if(node -> left == NULL && node -> right == NULL)
            return 1;
        else
            count = get_leaf_count(node->left) + get_leaf_count(node->right);
    }
    return count;
}

 

---

트리의 높이 구하기

• 각 서브 트리에 순환 호출한다.
• 서브 트리들의 반환값 중에서 최댓값을 구하여 반환한다.

int get_height(TreeNode *node)
{
    int height = 0;
    
    if(node != NULL)
        height = 1 + max(get_height(node->left), 
            get_height(node->right));
            
    return height;
}

---

8.10 스레드 이진 트리

• 스레드(Thread): 실을 이용하여 노드들을 순회 순서대로 연결시켜 놓은 트리 
• 중위 선행자(Inorder predecessor, NULL 링크에 중위 순회 시에 선행 노드)나 중위 후속자(Inorder successor, 중위 순회시에 후속 노드)를 저장시켜 놓은 트리가 스레드 이진 트리이다.
• 장점:
  • 스택을 사용하지 않아 순회가 가능하다. 
  • 탐색이 빠르다
• 단점:
  • 추가 공간을 요구한다.(LTag, RTag)
  • 삽입, 삭제가 느리다.

 

노드 p의 중위 후속자를 반환하는 함수

TreeNode * find_successor(TreeNode * p)
{
	// q는 p의 오른쪽 포인터
	TreeNode * q = p->right;
	// 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환
	if (q == NULL || p->is_thread == TRUE)
		return q;

	// 만약 오른쪽 자식이면 다시 가장 왼쪽 노드로 이동
	while (q->left != NULL) q = q->left;
	return q;
}

1. p의 is_thread가 TRUE로 되어 있으면 바로 오른쪽 자식이 중위 후속자가 되므로 오른쪽 자식을 반환
2. 오른쪽 자식이 NULL이면 더 이상 후속자가 없다는 것이므로 NULL반환
3. is_thread가 TRUE가 아닌경우 서브 트리의 가장 왼쪽 노드로 간다.
4. 왼쪽 자식이 NULL이 될 때까지 왼쪽 링크를 타고 이동한다. 

 

스레드 이진 트리에서 중위 순회를 하는 함수

void thread_inorder(TreeNode * t)
{
    TreeNode * q;
    
    q = t;
    while(q->left)
        q = q->left; // 가장 왼쪽 노드로 간다
    do{
        printf("%c->", q->data);  // 데이터 출력
        q = find_successor(q); //후속자 함수 호출
    } while(q); // NULL이 아니면
}

---

8.11 이진 탐색 트리

• 이진 트리 기반의 탐색을 위한 자료 구조
• 모든 원소의 키는 유일한 키를 가진다.
• 왼쪽 서브 트리 키들은 루트 키보다 작다.
• 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

➡️ 찾고자 하는 키값이 이진트리의 루트 노드의 킷값과 비교하여 루트 노드보다 작으면 왼쪽, 크면 오른쪽에 있다.

 

 

---

순환적인 탐색연산

• 비교한 결과가 같으면 탐색이 성공적으로 끝난다.
• 비교한 결과가, 주어진 키 값이 루트 노드의 키값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작한다.
• 비교한 결과가, 주어진 키 값이 루트 노드 키값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다.

 

// 순환적인 탐색 함수
TreeNode * search(TreeNode * node, int key)
{
	if (node == NULL) return NULL;
	if (key == node->key) return node;
	else if (key < node->key)
		return search(node->left, key);
	else
		return search(node->right, key);
}

 

---

반복적인 탐색연산 

 

// 반복적인 탐색 함수
TreeNode * search(TreeNode * node, int key)
{
    while(node != NULL){
        if (key == node->key) return node;
	    else if (key < node->key)
	    	 node = node->left;
	    else
		    node = node->right;
    }
    return NULL;    
}

 

---

이진탐색트리에서 삽입연산

• 트리에 원소 삽입 전 먼저 탐색을 수행해야한다.
• 탐색에 성공하면 삽입하려는 원소가 트리에 이미 존재 -> 키가 중복되므로 삽입이 불가능하다.

 

TreeNode * insert_node(TreeNode * node, int key)
{
	// 트리가 공백이면 새로운 노드를 반환한다. 
	if (node == NULL) return new_node(key);

	// 그렇지 않으면 순환적으로 트리를 내려간다. 
	if (key < node->key)
		node->left = insert_node(node->left, key);
	else if (key > node->key)
		node->right = insert_node(node->right, key);

	// 변경된 루트 포인터를 반환한다. 
	return node;
}

 

---

이진탐색 트리에서 삭제 연산

• 삽입과 마찬가지로 탐색을 먼저해야한다.
• 삭제 시 다음 세가지를 고려해야 한다. 

고려사항

1. 삭제하려는 노드가 단말 노드일 경우
2. 삭제하려는 노드가 하나늬 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우
3. 삭제하려는 노드가 두개의 서브 트리 모두 가지고 있는 경우

---

삭제하려는 노드가 단말 노드일 경우

• 단말노드만 지우면 된다.
• 단말 노드의 부모노드를 찾아 부모노드 안의 링크 필드를 NULL로 만들어 연결을 끊는다.
• 만약 동적으로 색성하였다면, 동적 메모리를 해제시키면 된다. 

 

---

삭제하려는 노드가 하나늬 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우

• 자기 노드는 삭제하고 서브 트리는 자기 노드의 부모 노드에 붙여준다.

---

삭제하려는 노드가 두개의 서브 트리 모두 가지고 있는 경우

• 삭제한려는 노드의 왼쪽 서브트리에서 제일 큰 값
• 삭제한려는 노드의 오른쪽 서브트리에서 제일 작은 값
• 위 값 중 하나를 선택한다.

// 이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제하고 
// 새로운 루트 노드를 반환한다. 
TreeNode * delete_node(TreeNode * root, int key)
{
	if (root == NULL) return root;

	// 만약 키가 루트보다 작으면 왼쪽 서브 트리에 있는 것임
	if (key < root->key)
		root->left = delete_node(root->left, key);
	// 만약 키가 루트보다 크면 오른쪽 서브 트리에 있는 것임
	else if (key > root->key)
		root->right = delete_node(root->right, key);
	// 키가 루트와 같으면 이 노드를 삭제하면 됨
	else {
		// 첫 번째나 두 번째 경우
		if (root->left == NULL) {
			TreeNode * temp = root->right;
			free(root);
			return temp;
		}
		else if (root->right == NULL) {
			TreeNode * temp = root->left;
			free(root);
			return temp;
		}
		// 세 번째 경우
		TreeNode * temp = min_value_node(root->right);

		// 중외 순회시 후계 노드를 복사한다. 
		root->key = temp->key;
		// 중외 순회시 후계 노드를 삭제한다. 
		root->right = delete_node(root->right, temp->key);
	}
	return root;
}