碳之狼

用户名：1024650038

访问量：8491

签　名：

现在的我什么都做不到

等　　级
排　　名	664
经　　验	4015
参赛次数	0
文章发表	17
年　　龄	18
在职情况	学生
学　　校	东莞理工学院
专　　业	计算机类

　　自我简介：

TA的其他文章

数据结构-平衡二叉树的基本操作-题解(C语言代码)
浏览：533

蓝桥杯算法提高VIP-铺地毯-题解(C语言代码)
浏览：290

数据结构-二叉链表存储的二叉树-题解(C语言代码)
浏览：595

你可能喜欢

数据结构-平衡二叉树的基本操作-题解(C语言代码)

　　作者: 碳之狼　　　　发表时间：2020-01-28 20:53:22 浏览：533　|　评论：0　

原题链接：数据结构-平衡二叉树的基本操作

```c
#include<stdio.h>
#include<stdlib.h>

int sign;

typedef struct AVLNode* AVLTree;
struct AVLNode {
	int data;
	AVLTree left;
	AVLTree right;
};

int GetHeight(AVLTree T)
{
	int HL, HR, MaxH;
	if (T) {
		HL = GetHeight(T->left);
		HR = GetHeight(T->right);
		MaxH = (HL > HR) ? HL : HR;
		return (MaxH + 1);
	}
	return 0;
}

AVLTree SingleRightRotation(AVLTree A)
{
	AVLTree B = A->right;
	A->right = B->left;
	B->left = A;
	return B;
}

AVLTree SingleLeftRotation(AVLTree A)
{
	AVLTree B = A->left;
	A->left = B->right;
	B->right = A;
	return B;
}

AVLTree DoubleRightLeftRotation(AVLTree A)
{
	A->right = SingleLeftRotation(A->right);
	return SingleRightRotation(A);
}

AVLTree DoubleLeftRightRotation(AVLTree A)
{
	A->left = SingleRightRotation(A->left);
	return SingleLeftRotation(A);
}

AVLTree Insert(AVLTree T, int val)
{
	if (!T) {
		T = (AVLTree)malloc(sizeof(struct AVLNode));
		T->data = val;
		T->left = T->right = NULL;
	}
	else if (val < T->data) {
		T->left = Insert(T->left, val);
		if (GetHeight(T->left) - GetHeight(T->right) == 2) {
			if (val < T->left->data)
				T = SingleLeftRotation(T);
			else
				T = DoubleLeftRightRotation(T);
		}
	}
	else if (val > T->data) {
		T->right = Insert(T->right, val);
		if (GetHeight(T->left) - GetHeight(T->right) == -2) {
			if (val > T->right->data)
				T = SingleRightRotation(T);
			else
				T = DoubleRightLeftRotation(T);
		}
	}
	return T;
}

int PreOrderTraversal(AVLTree T, int val)
{
	if (T) {
		if (val == T->data) sign = 1;
		PreOrderTraversal(T->left, val);
		PreOrderTraversal(T->right, val);
	}
	if (sign) return 1;
	else return 0;
}

int main()
{
	int n, k, tmp;
	AVLTree T = NULL;
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &tmp);
		T = Insert(T, tmp);
	}
	for (int i = 1; i <= k; i++) {
		sign = 0;
		scanf("%d", &tmp);
		printf("%d ", PreOrderTraversal(T, tmp));
	}
	return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

碳之狼

TA的其他文章

你可能喜欢

明明的随机数（C++代码）

剪刀石头布（Java代码）

C语言程序设计教程（第三版）课后习题8.2 （C++代码）

字符逆序（C语言代码）

The 3n + 1 problem （C语言代码）

数据结构-平衡二叉树的基本操作-题解(C语言代码)

评论区

精彩推荐

Tom数（C语言代码）

大神老白（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

1017题解

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

1250题解

碳之狼

TA的其他文章

你可能喜欢

明明的随机数 （C++代码）

剪刀石头布 （Java代码）

C语言程序设计教程（第三版）课后习题8.2 （C++代码）

字符逆序 （C语言代码）

The 3n + 1 problem （C语言代码）

数据结构-平衡二叉树的基本操作-题解(C语言代码)

评论区

精彩推荐

Tom数 （C语言代码）

大神老白 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

1017题解

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

1250题解

明明的随机数（C++代码）

剪刀石头布（Java代码）

字符逆序（C语言代码）

　　评论区

Tom数（C语言代码）

大神老白（C语言代码）