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

01 (4)

02 (2)     A-B-D-C-E-G-H-F

03 (4)

04 (3)     D,G,H,F -> 4개

05 (1)     트리의 차수 = B의 차수 = 3

06 (3)        +

               /     \

            *          /

          /  \       /    \

       A    B    C     D              + * A B / C D

07 (4)       2^5-1

08 (3)

09 평균의 시간 복잡도: 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 4 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)  9보다 작은 8이 9의 오른쪽 서브트리에 존재하기 때문에 이진 탐색 트리가 아니다.

 

11 추가 예정

 

12 8 

4로 헷갈렸었는데, 함수의 순환이므로 종국에는 max(4,8)을 비교하게 돼서 8이 반환된다.

ㅊ

13

int isBalanced(TreeNode *node){
	if(node == NULL){
		return 1;
	}
	if(node->left ==NULL || node->right ==NULL){
		return 1;
	}
	int left_height = get_height(node->left);
	int right_height = get_height(node->right);
	if((left_height - right_height)<=1 && (left_height - right_height) >=-1 && isBalanced(node->left) && isBalanced(node->right)){
		return 1;
	}
	return 0;
}

 

14

int sum=0;

void inoder_sum(TreeNode *root){
	if(root!=NULL){
		inoder_sum(root->left);
		sum +=root->data;
		inoder_sum(root->right);
	}
}


int main(){
	inoder_sum(root);
	printf("합은 %d\n",sum);
}

 

15

void inorder_print_if_less_than(TreeNode* root, int input){
	if(root !=NULL){
		inorder_print_if_less_than(root->left,input);
		if(root->data <input)
		{
			printf("%d보다 작은 노드: %d\n",input,root->data);
		}
		inorder_print_if_less_than(root->right,input);
	}
}

16

int count= 0;

int inorder_count_have_one_child(TreeNode *root){
	if(root!=NULL){
		inorder_count_have_one_child(root->left);
		if(root->left ==NULL && root->right !=NULL){
			count ++;
		}
		else if(root->left !=NULL && root->right ==NULL){
			count ++;
		}
		inorder_count_have_one_child(root->right);
	}
	return count;
}

17

int max =0;
int min =9999;

int inorder_find_max(TreeNode *root){
	if(root!=NULL){
		inorder_find_max(root->left);
		if(root->data > max) max = root->data;
		inorder_find_max(root->right);
	}
	return max;
}

int inorder_find_min(TreeNode *root){
	if(root!=NULL){
		inorder_find_min(root->left);
		if(root->data <min) min = root->data;
		inorder_find_min(root->right);
	}
	return min;
}

int main(){
	printf("노드의 최대값은 %d  ",inorder_find_max(root));
	printf("노드의 최소값은 %d  ",inorder_find_min(root));
	
	return 0;
}

18

void inorder(TreeNode *root){
	if(root){
		inorder(root->left);
		printf("[%d] ",root->key);
		inorder(root->right);
	}
}


int main(){
	TreeNode * root = NULL;
	TreeNode *temp = NULL;
	
	root = insert_node(root,11);
	root = insert_node(root,3);
	root = insert_node(root,4);
	root = insert_node(root,1);
	root = insert_node(root,56);
	root = insert_node(root,5);
	root = insert_node(root,6);
	root = insert_node(root,2);
	root = insert_node(root,98);
	root = insert_node(root,32);
	root = insert_node(root,23);
	
	printf("이진 탐색 트리 중위 순회 결과 \n");
	inorder(root);
	printf("\n");
	
	return 0;
}

19

void inorder_inverse(TreeNode *root){
	if(root){
		inorder_inverse(root->right);
		printf("[%d] ",root->key);
		inorder_inverse(root->left);
	}
}

20

void add_one(TreeNode *root){
	if(root){
		add_one(root->left);
		root->key +=1;
		printf("[%d] ",root->key);
		add_one(root->right);
	}
}

21

가장 오른쪽 노드로 이동한다

 

22

생략