二叉平衡树相关算法

#include<stdio.h>
#include<iostream>
typedef int KeyType;
typedef char InfoType;
typedef struct node
{
	KeyType Key;
	int bf;
	InfoType data;
	struct node *lchild, *rchild;
}BSTNode;
void LeftProcess(BSTNode *&p, int &taller)
{
	BSTNode *p1,*p2;
	if (p->bf == 0)
	{
		p->bf = 1;
		taller = 1;
	}
	else if (p->bf == 1)
	{
		p->bf = 0;
		taller = 0;
	}
	else
	{
		p1 = p->lchild;
		if (p1->bf == 1)
		{
			p->lchild = p1->rchild;
			p1->rchild = p;
			p->bf = p1->bf = 0;
			p = p1;
		}
		else if (p1->bf == -1)
		{
			p2 = p1->rchild;
			p1->rchild = p2->lchild;
			p2->lchild = p1;
			p->lchild = p2->rchild;
			p2->rchild = p;
			if (p2->bf == 1)
				p->bf = p1->bf = 0;
			else if (p2->bf == 1)
			{
				p1->bf = 0;
				p->bf = -1;
			}
			else
			{
				p1->bf = 1;
				p->bf = 0;
			}
			p = p2; p->bf = 0;
		}
		taller = 0;
	}
}void RightProcess(BSTNode * &p, int &taller)
{
	BSTNode *p1, *p2;
	if (p->bf == 0)
	{
		p->bf = -1;
		taller = 1;
	}
	else if (p->bf == 1)
	{
		p->bf = 0;
		taller = 0;
	}
	else
	{
		p1 = p->rchild;
		if (p1->bf == -1)
		{
			p->rchild - p1->lchild;
			p1->lchild = p;
			p->bf = p1->bf = 0;
			p = p1;
		}
		else if (p1->bf == 1)
		{
			p2 = p1->lchild;
			p1->lchild = p2->rchild;
			p2->rchild = p1;
			p->rchild = p2->lchild;
			p2->lchild = p;
			if (p2->bf == 0)
				p->bf = p1->bf = 0;
			else if (p2->bf == -1)
			{
				p1->bf = 0;
				p->bf = 0;
			}
			else
			{
				p1->bf = -1;
				p->bf = 0;
			}
			p = p2; p->bf = 0;
		}
		taller = 0;
	}
}

int InseertAVL(BSTNode * &b, KeyType e, int &taller)
{
	if (b == NULL)
	{
		b = (BSTNode *)malloc(sizeof(BSTNode));
		b->Key = e;
		b->lchild = b->rchild = NULL;
		b->bf = 1;
		taller = 1;
	}
	else
	{
		if (e == b->Key)
		{
			taller = 0;
			return 0;
		}
		if (e < b->Key)
		{
			if ((InseertAVL(b->lchild, e, taller)) == 0)
				return 0;
			if (taller == 1)
				LeftProcess(b, taller);
		}
		else
		{
			if ((InseertAVL(b->lchild, e, taller)) == 0)
				return 0;
			if (taller == 1)
				RightProcess(b, taller);
		}
	}
	return 1;
}
void DispBSTree(BSTNode * b)
{
	if (b != NULL)
	{
		printf("%d", b->Key);
		if (b->lchild != NULL || b->rchild != NULL)
		{
			printf("(");
			DispBSTree(b->lchild);
			if (b->rchild != NULL)printf(",");
			DispBSTree(b->rchild);
			printf(")");
		}
	}
}

void LeftProcee1(BSTNode * &p, int &taller)
{
	BSTNode *p1, *p2;
	if (p->bf == 1)
	{
		p->bf = 0;
		taller = 1;
	}
	else if (p->bf == 0)
	{
		p->bf = -1;
		taller = 0;
	}
	else
	{
		p1 = p->rchild;
		if (p1->bf == 0)
		{
			p->rchild = p1->lchild;
			p1->lchild = p;
			p1 -> bf = 1; p->bf = -1;
			p = p1;
			taller = 0;
		}
		else if (p1->bf == -1)
		{
			p->rchild = p1->lchild;
			p1->lchild = p;
			p1->bf = p->bf = 0;
			p = p1 = 0;
			taller = 1;
		}
		else
		{
			p2 = p1->lchild;
			p1->lchild = p2->rchild;
			p2->rchild = p1;
			p->rchild = p2->lchild;
			p2->lchild = p;
			if (p2->bf == 0)
			{
				p->bf = 0;
				p1->bf = 0;
			}
			else if (p2->bf = 1)
			{
				p->bf = 1;
				p1->bf = 0;
			}
			else
			{
				p->bf = 0;
				p1->bf = -1;
			}
			p2->bf = 0;
			p = p2;
			taller = 1;
		}
	}
}

void RightProcess1(BSTNode * &p, int &taller)
{
	BSTNode *p1, *p2;
	if (p->bf == -1)
	{
		p->bf = 0;
		taller = -1;
	}
	else if (p->bf ==0)
	{
		p->bf = 1;
		taller = 0;
	}
	else
	{
		p1 = p->lchild;
		if (p1->bf == 0)
		{
			p->lchild = p1->rchild;
			p->rchild = p;
			p1->bf = -1; p->bf = 1;
			p = p1;
			taller = 0;
		}
		else if (p1->bf == 1)
		{
			p->lchild = p1->rchild;
			p1->rchild = p;
			p->bf = p->bf = 0;
			p = p1;
			taller = 1;
		}
		else
		{
			p2 = p1->rchild;
			p1->rchild = p2->lchild;
			p2->lchild = p1;
			p->lchild = p2->rchild;
			p2->rchild = p;
			if (p2->bf == 0)
			{
				p->bf = 0;
				p1->bf = 0;
			}
			else if (p2->bf == 1)
			{
				p->bf = -1;
				p1->bf = 0;
			}
			else
			{
				p->bf = 0;
				p1->bf = 1;
			}
			p2->bf = 0;
			p = p2;
			taller = 1;
		}
	}
}

void Delete2(BSTNode * &q, BSTNode * &r, int &taller)
{
	if (r->rchild == NULL)
	{
		q->Key = r->Key;
		q = r;
		r = r->rchild;
		free(q);
		taller = 1;
	}
	else
	{
		Delete2(q, r->rchild, taller);
		if (taller == 1)
			RightProcess1(r, taller);
	}
}

int DeleteAVL(BSTNode * &p, KeyType x, int &taller)
{
	int k;
	BSTNode *q;
	if (p == NULL)
		return 0;
	else if (x < p->Key)
	{
		k = DeleteAVL(p->rchild, x, taller);
		if (taller == 1)
			RightProcess1(p, taller);
		return k;
	}
	else if (x > p->Key)
	{
		k = DeleteAVL(p->rchild, x, taller);
		if (taller == 1)
			RightProcess1(p, taller);
		return k;
	}
	else
	{
		q = p;
		if (p->rchild == NULL)
		{
			p = p->lchild;
			free(q);
			taller = 1;
		}
		else if (p->lchild == NULL)
		{
			p = p->rchild;
			free(q);
			taller = 1;
		}
		else
		{
			Delete2(q, q->lchild, taller);
			if (taller == 1)
				LeftProcee1(q, taller);
			p = q;
		}
		return 1;
	}
}

void main()
{
	BSTNode *b = NULL;
	int i, j, k;
	KeyType a[] = { 4,9,0,1,8,6,3,5,2,7 }, n = 10;
	printf("创建一颗AVL树\n");
	for (i = 0; i < n; i++)
	{
		printf("第%d步，插入%d元素：", i + 1, a[i]);
		InseertAVL(b, a[i], j);
		DispBSTree(b); printf("\n");
	}
	printf("结果AVL："); DispBSTree(b); printf("\n");
	printf("删除节点:\n");
	k = 8;
	printf("删除节点%d:", k);
	DeleteAVL(b, k, j);
	printf("AVL:"); DispBSTree(b); printf("\n");
	k -= 2;
	printf("删除节点%d", k);
	DeleteAVL(b, j, k);
	printf("AVL:"); DispBSTree(b); printf("\n");
	getchar();
}