数据结构实验7中（平衡二叉树的创建与节点删除）

随机生成10个正整数，根据生成的顺序在内存中生成一棵平衡二叉树并在控制台输出该树。
从控制台输入一个整数，如果为负数，程序结束；
如果为正数，在二叉搜索树中查找该整数。
如果该数不存在，输出 - 1；如果存在，删除该结点并输出删除结点后的树

#include
#include
#include

typedef struct Tree
{
	int data;
	int high;
	struct Tree* l;
	struct Tree* r;
}tree;

void printfnode(int data, char c, int depth)
{
	for (int i = 0; i < depth; i++)
		printf("	");
	if (data == -1)
		printf("%c %c\n", c, '*');
	else
		printf("%c %d\n", c, data);
}

void printftree(tree* root, char c, int depth)
{
	if (root == NULL)
	{
		printfnode(-1, c, depth);
		return;
	}
	if (root->l == NULL && root->r == NULL)
	{
		printfnode(root->data, c, depth);
		return;
	}
	printftree(root->r, '/', depth + 1);
	printfnode(root->data, c, depth);
	printftree(root->l, '\\', depth + 1);
}

int gethigh(tree* root)
{
	if (root == NULL)
		return -1;
	else
		return root->high;
}

tree* ll(tree* root)
{
	tree* tnode = root->l;
	root->l = tnode->r;
	tnode->r = root;

	int h1, h2;
	h1 = gethigh(root->l) + 1;
	h2 = gethigh(root->r) + 1;
	root->high = h1 > h2 ? h1 : h2;
	return tnode;
}

tree* rr(tree* root)
{
	tree* tnode = root->r;
	root->r = tnode->l;
	tnode->l = root;

	int h1, h2;
	h1 = gethigh(root->l) + 1;
	h2 = gethigh(root->r) + 1;
	root->high = h1 < h2 ? h1 : h2;
	return tnode;
}

tree* lr(tree* root)
{
	root->l = rr(root->l);
	root = ll(root);
	return root;
}

tree* rl(tree* root)
{
	root->r = ll(root->r);
	root = rr(root);
	return root;
}

tree* creattree(tree* root, int data)
{
	int h1, h2;
	if (root == NULL)
	{
		root = (tree*)malloc(sizeof(tree));
		root->data = data;
		root->high = 0;
		root->l = NULL;
		root->r = NULL;
	}
	else if (data < root->data)
	{
		root->l = creattree(root->l, data);
		if (abs(gethigh(root->l) - gethigh(root->r) > 1))
			if (root->l->data >= data)
				root = ll(root);
			else
				root = lr(root);
	}
	else
	{
		root->r = creattree(root->r, data);
		if (abs(gethigh(root->l) - gethigh(root->r)) > 1)
		{
			if (root->r->data <= data)
				root = rr(root);
			else
				root = rl(root);
		}
	}
	h1 = gethigh(root->l) + 1;
	h2 = gethigh(root->r) + 1;
	root->high = h1 > h1 ? h1 : h2;
	return root;
}

tree* findmin(tree* root)
{
	if (root == NULL)
		return NULL;
	else if (root->l)
		return findmin(root->l);
	else
		return root;
}

tree* findmax(tree* root)
{
	if (root == NULL)
		return NULL;
	else if (root->r)
		return findmax(root->r);
	else
		return root;
}

tree* del(tree* root, int find, int* flag)
{
	int h1, h2;
	if (root == NULL)
	{
		*flag = -1;
		return NULL;
	}
	else if (find == root->data)
	{
		if (root->l && root->r)
		{
			if (gethigh(root->l) > gethigh(root->r))
			{
				int max = findmax(root->l)->data;
				root->data = max;
				root->l = del(root->l, max, flag);
				h1 = gethigh(root->l) + 1;
				h2 = gethigh(root->r) + 1;
				root->high = h1 > h2 ? h1 : h2;
			}
			else
			{
				int min = findmin(root->r)->data;
				root->data = min;
				root->r = del(root->r, min, flag);
				h1 = gethigh(root->l) + 1;
				h2 = gethigh(root->r) + 1;
				root->high = h1 > h2 ? h1 : h2;
			}
		}
		else
		{
			tree* tnode = root;
			if (root->l != NULL)
			{
				root = root->l;
				free(tnode);
			}
			else if (root->r != NULL)
			{
				root = root->r; 
				free(tnode);
			}
			else
			{
				free(tnode);
				root = NULL;
			}
		}
		*flag = 1;
	}
	else if (find < root->data)
	{
		root->l = del(root->l, find, flag);
		h1 = gethigh(root->l) + 1;
		h2 = gethigh(root->r) + 1;
		root->high = h1 > h2 ? h1 : h2;
		if (abs(gethigh(root->l) - gethigh(root->r)) > 1)
			if (gethigh(root->r->l) > gethigh(root->r->r))
				root = rl(root);
			else
				root = rr(root);
	}
	else
	{
		root->r = del(root->r, find, flag);
		h1 = gethigh(root->l) + 1;
		h2 = gethigh(root->r) + 1;
		root->high = h1 > h2 ? h1 : h2;
		if (abs(gethigh(root->l) - gethigh(root->r)) > 1)
			if (gethigh(root->l->l) > gethigh(root->l->r))
				root = ll(root);
			else
				root = lr(root);
	}
	return root;
}

int main()
{
	tree* root = NULL;
	int a[10];
	for (int i = 0; i < 10; i++)
	{
		a[i] = rand() % 101;
		root = creattree(root, a[i]);
	}
	printftree(root, ' ', 0);
	printf("------------------------------------------------\n");

	int find;
	int* flag = (int*)malloc(sizeof(int));
	*flag = 1;
	scanf("%d", &find);
	while (find >= 0)
	{
		root = del(root, find, flag);
		if (*flag == -1)
		{
			printf("no find\n");
			printf("------------------------------------------------\n");
		}
		else
		{
			printftree(root, ' ', 0);
			printf("------------------------------------------------\n");
		}
		*flag = 1;
		scanf("%d", &find);
	}
	free(flag);
}