526互联

1012打卡

发布时间 2023-10-12 00:36:15作者: aallofitisst

今天学习了avl二叉排序树

#include<iostream>
using namespace std;

struct tree
{
	tree* lchild=NULL;
	tree* rchild=NULL;
	int data;
	int height;
};

int getHeight(tree* t)
{
	if (t)
	{
		return t->height;
	}
	else
		return 0;
}

tree* lltree(tree* t)
{
	tree* tmp = t->lchild;
	t->lchild = tmp->rchild;
	tmp->rchild = t;
	t->height = max(getHeight(t->lchild), getHeight(t->rchild)) + 1;
	tmp->height = max(getHeight(t->lchild), getHeight(t->rchild)) + 1;
	return tmp;
}

tree* rrtree(tree* t)
{
	tree* tmp = t->rchild;
	t->rchild = tmp->lchild;
	tmp->lchild = t;
	t->height = max(getHeight(t->lchild), getHeight(t->rchild)) + 1;
	tmp->height = max(getHeight(t->lchild), getHeight(t->rchild)) + 1;
	return tmp;
}

int max(int a, int b)
{
	return a > b ? a : b;
}

void addTree(tree*& t, int data)
{
	if (t == NULL)
	{
		t = new tree;
		t->data = data;
	}
	else
	{
		if (data < t->data)
		{
			addTree(t->lchild, data);
			int lheight = getHeight(t->lchild);
			int rheight = getHeight(t->rchild);
			if (lheight - rheight > 1)
			{
				if (data < t->lchild->data)
				{
					//ll形
					t = lltree(t);
				}
				else if(data > t->lchild->data)
				{
					//lr形
					t->lchild = rrtree(t->lchild);
					t = lltree(t);
				}
			}
		}
		else if (data > t->data)
		{
			addTree(t->rchild, data);
			int lheight = getHeight(t->lchild);
			int rheight = getHeight(t->rchild);
			if (rheight - lheight > 1)
			{
				if (data > t->rchild->data)
				{
					//rr形
					t = rrtree(t);
				}
				else if (data < t->rchild->data)
				{
					//rl形
					t->rchild = lltree(t->rchild);
					t = rrtree(t);
				}
			}
		}
	}
	t->height = max(getHeight(t->lchild), getHeight(t->rchild)) + 1;
}


//中序遍历
void print(tree* t)
{
	if (t)
	{
		cout << t->data << ' ';
		print(t->lchild);
		print(t->rchild);
	}
}

int main()
{
	int nums[5] = { 1,8,6,7,10 };
	tree* t = NULL;
	for (int i = 0; i < 5; i++)
	{
		addTree(t, nums[i]);
	}
	print(t);
	return 0;
}