C언어로 쉽게 풀어쓴 자료구조 [연습문제 8장]

1. (4)
   
   

2. (2)  ∵ inorder: A B D C E G H F
   
   

3. (4)
   
   

4. (3)  ∵ D, G, H, F
   
   

5. (1)   ∵ Degree(B) = 3
   
   

6. (3)

풀이1 : 수식트리로 바꾼 뒤, 전순위 탐색한다.
<수식트리 변환>

<수식트리 전위 순회 결과>
＋ * A B / C D

풀이2 : 주어진 중위 수식을 스택을 이용하여 후위수식으로 변경 후, 전위 수식으로 변경한다.
<후위 수식으로 변환한 결과>
A B * C D / + (Ch4. 중위수식 → 후위수식 알고리즘 이용)

<후위 수식을 스택을 이용하여 전위수식으로 변경>

1	2	3	4	5	6	7
				D
	B		C	C	/CD
A	A	*AB	*AB	*AB	*AB	+*AB/CD

7. (4)  ∵ 2^5-1 = 31
   
   

8. (3)
   
   

9. 평균: O(logn), 최악: O(n)  
   ∵ 삽입, 삭제연산을 수행하기 위해서는 먼저 탐색이 필요하므로, 탐색의 복잡도를 따라간다.
   
   

10. (1)

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

      (2) 6 4 2 1 3 5 9 7 10 8 11

      (3) 1 3 2 5 4 7 8 11 10 9 6

      (4) 1 2 3 4 5 6 7 9 8 10 11

      (5) 6 4 9 2 5 7 10 1 3 8 11

      (6) X  ∵ 9보다 작은 8이 9의 오른쪽 서브트리에 포함되어있으므로 이진탐색트리가 아니다.

11. (1)
    
    (2) 10 혹은 17이 루트로 옮겨질 수 있다.
    또는
    (3)
    
    (4) 11, 6, 8
    
    
    (5)

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	11	6	19	4	8	17	43		5		10			31	49

12. 8  ∵ 리프노드 중 최댓값을 반환하는 함수이다.
    
    

int balance(node* root) {	// 균형트리인 경우 양수(트리의 높이)를 반환하고, 편향트리인 경우 음수(-1)을 반환하는 함수
	int c = 0;
	if (root) {
		int left = balance(root->left);
		int right = balance(root->right);
		int max = (left > right) ? left : right;
		int min = (left < right) ? left : right;
		if ((min >= 0) && (max - min <= 1))
			c = max + 1;
		else
			c = -1;
	}
	return c;
}

int sum(node* root) {
	if (!root)
		return 0;
	return (root->data + sum(root->left) + sum(root->right));
}

void prints(node* root, int key) {
	if (root == NULL)
		return;
	if (root->data < key)
		printf("[%d] ", root->data);
	prints(root->left, key);
	prints(root->right, key);
}

int child(node* root) {
	int count = 0;
	if (root) {
		int left = child(root->left);
		int right = child(root->right);
		if ((root->left == NULL && root->right) || (root->left && root->right==NULL))
			count++;
		count += (left + right);
	}
	return count;
}

int min = INT_MAX;
int max = INT_MIN;

void minmax(node* root) {
	if (root) {
		if (root->left || root->right) {
			minmax(root->left);
			minmax(root->right);
		}
		int num = root->data;
		if (num > max)
			max = num;
		if (num < min)
			min = num;
	}
}

void ascending(node* root) {
	if (root) {
		ascending(root->left);
		printf("%d ", root->data);
		ascending(root->right);
	}
}

void descending(node* root) {
	if (root) {
		descending(root->right);
		printf("%d ", root->data);
		descending(root->left);
	}
}

void plus(node* root) {
	if (root) {
		root->data++;
		plus(root->left);
		plus(root->right);
	}
}

while (root->right)
	root = root->right

22. 생략