네 번 째 프로 그래 밍 작업

10625 단어 데이터 구조 MOOC - 진 월 하 흠 명

 
  
 04- 4              (25 ) 
  
 
   
    
                          。  ，                         。        {2, 1, 3} {2, 3, 1}            ，        。             ，                    。 
        : 
               。      1         $() ， 。 2 ， 。 ， ， 。$  
        ，            1  $。 0 ， ， 。$  
        : 
               ，                        ，  “Yes”，    “No”。 
        : 
     4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
  
        : 
     Yes
No
No
  
    
   
  
 
   #include 
#include 
#define ElementType int

typedef struct Node *Tree;
struct Node{
	ElementType Element;
	Tree Left;
	Tree Right;
	int Flag;
};

Tree BuildTree(int);
Tree CreateNewNode(int);
Tree Insert(Tree, int);
int Judge(Tree, int);
int Check(Tree, int);
void Reset(Tree);
void FreeTree(Tree);

int main()
{
	int N, L, i;
	Tree T;
	
	scanf("%d", &N);
	while (N){
		scanf("%d", &L);
		int Result[L];
		T = BuildTree(N);
		
		for(i = 0; i < L; i++){
			Result[i] = Judge(T, N);
			Reset(T);
		}
		
		for(i = 0; i < L; i++){
			if(Result[i] == 1)
				printf("Yes
");
			else
				printf("No
");	
		}
		FreeTree(T);
		scanf("%d", &N);
	}
	return 0;
}

Tree BuildTree(int N)
{
	int i, data;
	Tree T;
	
	scanf("%d", &data);
	T = CreateNewNode(data);
	for(i = 1; i < N; i++){
		scanf("%d", &data);
		T = Insert(T, data);
	}
	
	return T;
}

Tree CreateNewNode(int data)
{
	Tree T = (Tree)malloc(sizeof(struct Node));
	T->Element = data;
	T->Left = NULL;
	T->Right = NULL;
	T->Flag = 0;
	
	return T;
}

Tree Insert(Tree T, int data)
{
	if(!T)
		T = CreateNewNode(data);
	else{
		if(data < T->Element)
			T->Left = Insert(T->Left, data);
		else if(data > T->Element)
			T->Right = Insert(T->Right, data);
	}
		
	return T;			
}

int Judge(Tree T, int N)
{
	int i, data;
	int flag = 1;
	
	scanf("%d", &data);
	if(data != T->Element)
		return 0;
	else
		T->Flag = 1;	
	
	//flag = 1     flag = 0       
	for(i = 1; i < N; i++){
		scanf("%d", &data);
		flag = Check(T, data);
		if(!flag)
			break;
	}
	return flag;
}

//  1         
int Check(Tree T, int data)
{	
	if(T->Flag){
		if(data < T->Element)
			return Check(T->Left, data);
		else if(data > T->Element)
			return Check(T->Right, data);
		else
			return 0;	
	}
	else{
		if(data == T->Element){
			T->Flag = 1;
			return 1;
		}
		else
			return 0;
	}
				
}

void Reset(Tree T)
{
	if(T->Left)
		Reset(T->Left);
	if(T->Right)
		Reset(T->Right);
		
	T->Flag = 0;		
}

void FreeTree(Tree T)
{
	if(T->Left)
		FreeTree(T->Left);
	if(T->Right)
		FreeTree(T->Right);
	
	free(T);		
}  
  
 04- 5 Root of AVL Tree   (25 ) 
  
 
   
    
    An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules. 
     
       
      
      
     Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree. 
     
     
    Input Specification: 
    Each input file contains one test case. For each case, the first line contains a positive integer  $() which is the total number of keys to be inserted. Then distinct integer keys are given in the next line. All the numbers in a line are separated by a space.$  
    Output Specification: 
    For each test case, print the root of the resulting AVL tree in one line. 
    Sample Input 1: 
     5
88 70 61 96 120
  
    Sample Output 1: 
     70
  
    Sample Input 2: 
     7
88 70 61 96 120 90 65
  
    Sample Output 2: 
     88
  
    
   
  
 
   
   // bug 
#include 
#include 
#define ElementType int

typedef struct Node * Tree;
struct Node{
	ElementType Element;
	Tree Left;
	Tree Right;
	int Height;
};

Tree BuildTree(int);
Tree Insert(Tree, int);
Tree SingleLeftRotation(Tree);
Tree SingleRightRotation(Tree);
Tree DoubleLeftRightRotation(Tree);
Tree DoubleRightLeftRotation(Tree);
void PrintRoot(Tree);
int Max(int, int);
int GetHeight(Tree);

int main()
{
	int N;
	Tree AVLTree;
	
	scanf("%d", &N);
	AVLTree = BuildTree(N);
	PrintRoot(AVLTree);
	
	return 	0;
}

Tree BuildTree(int N)
{
	int i, data;
	Tree T;
	
	for(i = 0; i < N; i++){
		scanf("%d", &data);
		T = Insert(T, data);
	}	

	return T;
}

// data  AVL  ，       AVL  
Tree Insert(Tree T, int data)
{
	//         
	if(!T){
		T = (Tree)malloc(sizeof(struct Node));
		T->Element = data;
		T->Left = NULL;
		T->Right = NULL;
		T->Height = 0;
	}
	//   T     
	else if(data < T->Element){
		T->Left = Insert(T->Left, data);
		if(GetHeight(T->Left) - GetHeight(T->Right) == 2){
			if(data < T->Left->Element)
				T = SingleLeftRotation(T);
			else
				T = DoubleLeftRightRotation(T);	
		}
	}
	//  T     
	else if(data > T->Element){
		T->Right = Insert(T->Right, data);
		if(GetHeight(T->Left) - GetHeight(T->Right) == -2){
			if(data > T->Right->Element)
				T = SingleRightRotation(T);
			else
				T = DoubleRightLeftRotation(T);	
		}
	}	
	//     
	T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;
	
	return T;
}

//LL LR RR Rl               
Tree SingleLeftRotation(Tree A)
{
	Tree B = A->Left;
	A->Left = B->Right;
	B->Right = A;
	A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
	B->Height = Max(GetHeight(B->Left), A->Height) +1;
	
	return B;
}

Tree SingleRightRotation(Tree A)
{
	Tree B = A->Right;
	A->Right = B->Left;
	B->Left = A;
	A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
	B->Height = Max(A->Height, GetHeight(B->Right)) + 1;
	
	return B;
}

Tree DoubleLeftRightRotation(Tree A)
{
	A->Left = SingleRightRotation(A->Left);
	return SingleLeftRotation(A);
}

Tree DoubleRightLeftRotation(Tree A)
{
	A->Right = SingleLeftRotation(A->Right);
	return SingleRightRotation(A);
}

void PrintRoot(Tree T)
{
	printf("%d", T->Element);
}

//     
int Max(int a, int b)
{
	return a >= b ? a : b;
}

//    ，       ，  -1 
int GetHeight(Tree T)
{
	if(T == NULL)
		return -1;
	else
		return T->Height;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

정수 반전

Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

백준 5928 Contest Timing

데이터구조 4

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다