[알고리즘 문제 day 1] 두 갈래 정렬 트 리

typedef struct BiTNode
{//         
	ElemType data; //   
	struct BiTNode *lchild,*rchild; // 、     
}BiTNode,*BiTree;

1. 주어진 이 진 트 리 가 이 진 트 리 인지 판단 하기

int predt = -32767; //predt     ，            
int JudgeBST(BiTree bt)
{//                
	int b1, b2;
	if (bt == NULL)
		return 1; //  ，         
	else
	{
		b1 = JudgeBST(bt->lChild); //             
		if (b1 == 0 || predt >= bt->data) //        0           ，        
			return 0;
		predt = bt->data; //          
		b2 = JudgeBST(bt->rChild); //     
		return b2; //        
	}
}

2. 지정 한 노드 가 주어진 두 갈래 정렬 트 리 의 차원 을 구하 기

int level(BiTree bt, BSTNode* p)
{//                   
	int n = 0; //      
	BiTree t = bt; //t     ，      
	if (bt != NULL)
	{
		n++;
		while (t->data != p->data)
		{
			if (t->data > p->data) //       
				t = t->lChild;
			else				   //       
				t = t->rChild;
			n++;				   //   1
		}
		return n;
	}
}

3. 이 진 트 리 가 밸 런 스 이 진 트 리 인지 판단 하기 [후 순 옮 겨 다 니 기]

void Judge_AVL(BiTree bt, int& balance, int& h)
{//                     
	int bl = 0, br = 0, hl = 0, hr = 0; //            
	if (bt == NULL) //  ，   0
	{
		h = 0;
		balance = 1;
	}
	else if (bt->lchild == NULL && bt->rchild == NULL) //     ，    1
	{
		h = 1;
		balance = 1;
	}
	else
	{
		Judge_AVL(bt->lchild, bl, hl); //       
		Judge_AVL(bt->rchild, br, hr); //       
		h = (hl > hr ? hl : hr) + 1;
		if (abs(hl - hr) < 2) //            2，           
			balance = bl & br; //        ，     
		else
			balance = 0;
	}
}

4. 이 진 트 리 의 가장 작은 키 와 가장 큰 키 워드 를 지정 하 십시오.

int MinKey(BSTNode* bt)
{//               
	while (bt->lchild != NULL)
		bt = bt->lchild;
	return bt->data;
}
int MaxKey(BSTNode* bt)
{//               
	while (bt->rchild != NULL)
		bt = bt->rchild;
	return bt->data;
}

5. 큰 출력 부터 작은 출력 까지 두 갈래 정렬 트 리 의 모든 값 이 k 보다 작 지 않 은 키워드

void OutPut(BSTNode* bt, int k)
{//                     k    （ - - ）
	if (bt == NULL)
		return;
	if (bt->rchild != NULL)
		OutPut(bt->rchild, k); //         
	if (bt->data >= k)
		printf("%d", bt->data); //       k    
	if (bt->lchild != NULL)
		OutPut(bt->lchild, k); //           
}

5. 재 귀 알고리즘 을 작성 하여 n 개의 노드 가 있 고 무 작위 로 만들어 진 이 진 정렬 트 리 에서 k (1 ≤ k ≤ n) 작은 요 소 를 찾 고 이 노드 를 가리 키 는 지침 을 되 돌려 줍 니 다.요구 알고리즘 의 평균 시간 복잡 도 는 O (log2n) 이다.두 갈래 정렬 트 리 의 각 노드 에 data, lchild, rchild 등 데이터 구성원 을 제외 하고 count 구성원 을 추가 하여 이 노드 를 뿌리 로 하 는 서브 트 리 의 노드 수 (루트 노드 포함) 를 저장 합 니 다.

BSTNode* Search_Small(BSTNode* t, int k)
{//  t         k    ，          。k 1    
 //         count    ，                
	if (k<1 || k>t->count)
		return NULL;
	if (t->lchild == NULL)
	{
		if (k == 1)
			return t;
		else
			return Search_Small(t->rchild, k - 1);
	}
	else
	{
		if (t->lchild->count == k - 1)
			return t;
		if (t->lchild->count > k - 1)
			return Search_Small(t->lchild, k);
		if (t->lchild->count < k - 1)
			return Search_Small(t->rchild, k - (t->lchild->count + 1));
	}
}