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

01 (3)

 

02 05(a)

 

03 (2)

 

04  100,00,000     경사트리일 경우, 최악의 경우는 O(n)

 

05(b) 06

 

07 생략

 

08

이진 탐색 트리는 정렬되어있지않은 배열을 못받기 때문에 AVL tree를 활용해 정렬시킨 후 

해당 트리를 중위순회하며 arr[] 배열에 담아서 정렬한 숫자를  출력하였다.

// 위는 AVL Tree code
int arr[6];
int k=0;

void inorder(AVLNode *root){
	if(root !=NULL){
		inorder(root->left);
		arr[k++] = root->key;
		inorder(root->right);
	}
}

int main(){
	AVLNode *root = NULL;
	
	root = insert(root,30);
	root = insert(root,20);
	root = insert(root,10);
	root = insert(root,50);
	root = insert(root,40);
	root = insert(root,29);
	
	printf("중위 순회 결과 \n");
	inorder(root);
	for(int i=0; i<6;i++){
		printf("%d ",arr[i]);
	}
	printf("\n");
	return 0;
}

 

09