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

typedef int ElementType;
typedef struct AVLNode
{
	ElementType data;
	struct AVLNode *left;
	struct AVLNode *right;
	int Height;
}AVLnode,*AVLTree;

// 求二叉树的高度：后序遍历
int depth(AVLTree root)
{
	int max, hl, hr;
	if (root != NULL)
	{
		hl = depth(root->left);  // 求左子树的高度
		hr = depth(root->right);  // 求右子树的高度
		max = hl > hr ? hl : hr;  // 求左右子树中的最大值
		return max + 1;          // 返回树的高度
	}
	else
		return 0;         // 如果是空树，返回0
}

// 左单旋
/* 注意：A必须有一个左子结点B
 将A与B做左单旋，更新A与B的高度，返回新的根结点B  */
AVLTree SingleLeftRotation(AVLTree A)
{
	AVLTree B = A->left;
	A->left = B->right;
	B->right = A;
	A->Height = depth(A);
	B->Height = depth(B);

	return B;
}

// 右单旋
/*注意：A必须有一个右子结点B
将A与B做右单旋，更新A与B的高度，返回新的根结点B*/
AVLTree SingleRightRotation(AVLTree A)
{
	AVLTree B = A->right;
	A->right = B->left;
	B->left = A;
	A->Height = depth(A);
	B->Height = depth(B);

	return B;
}
// 左-右双旋
/* 注意：A必须有一个左子结点B，且B必须有一个右子结点C
将A、B与C做两次单旋，返回新的根结点C */
AVLTree DoubleLeftRightRotation(AVLTree A)
{
	A->left = SingleRightRotation(A->left);  // 将B与C做右单旋，C被返回
	return SingleLeftRotation(A);      // 将A与C做左单旋，C被返回
}

//  右-左双旋
/* 注意：A必须有一个右子结点B，且B必须有一个左子结点C
将A、B与C做两次单旋，返回新的根结点C */
AVLTree DoubleRightLeftRotation(AVLTree A)
{
	A->right = SingleLeftRotation(A->right);  // 将B与C做左单旋，C被返回
	return SingleRightRotation(A);      // 将A与C做右单旋，C被返回
}

// 将x插入AVL树T中，并且返回调整后的AVL树
AVLTree Insert(AVLTree T,ElementType x)
{
	if (T == NULL)      /* 若插入空树，则新建包含一个结点的树 */
	{
		T = (AVLTree)malloc(sizeof(AVLnode));
		T->data = x;
		T->Height = 0;
		T->left = T->right = NULL;
	}
	else if (x < T->data)
	{
		T->left = Insert(T->left, x);    /* 插入T的左子树 */
		if (depth(T->left) - depth(T->right) == 2)        /* 如果需要左旋 */
			if (x < T->left->data)
				T = SingleLeftRotation(T);   /* 左单旋 */
			else
				T = DoubleLeftRightRotation(T);  /* 左-右双旋 */
	}
	else if (x>T->data)      
	{
		T->right = Insert(T->right, x);   /* 插入T的右子树 */
		if (depth(T->left) - depth(T->right) == -2)   /* 如果需要右旋 */
			if (x>T->right->data)
				T = SingleRightRotation(T);   /* 右单旋 */
			else
				T = DoubleRightLeftRotation(T);  /* 右-左双旋 */
	}
	/* 更新树高 */
	T->Height = depth(T);

	return T;
}

// 访问根结点
void visit_root(AVLTree root)
{
	if (root != NULL)
	{
		printf("%d ", root->data);   // 访问根结点
	}
}

int main()
{
	int i,N;
	int Elem;
	AVLTree T = NULL;

	printf("请输入要插入的元素个数：");
	scanf_s("%d",&N);
	for (i = 0;i < N;i++)
	{
		scanf_s("%d",&Elem);
		T = Insert(T,Elem);
	}
	visit_root(T);
	return 0;
}

八、哈夫曼树及哈夫曼编码

1.哈夫曼树

带权路径长度（WPL）：设二叉树有n个叶子结点，每个叶子结点带有权值Wi，从根结点到每个叶子结点的长度为Li，则每个叶子结点的带权路径长度之和为：

WPL最小的二叉树称为最优二叉树或者哈夫曼树。

哈夫曼树的存储结构，用C语言描述哈夫曼树如下：

#define N 200   // 叶子结点数
typedef struct
{
	int weight;  // 结点的权值
	int parent;  // 双亲的下标
	int left;    // 左孩子结点序号
	int right;  // 右孩子结点序号
}*HTree;

// 构造哈夫曼树,数组w存放n个叶子结点的权值
HTree CreateHuffmanTree(HTree ht, int w[], int n)
{
	/* 1-n号单元存放叶子结点，赋初值 */
	for (int i = 1;i <= n;i++)
		ht[i] = { w[i-1],0,0,0 };
	/* 创建非叶子结点 */
	int m = 2 * n - 1;
	int s1, s2;
	for (int i = n ;i < m;i++)
	{
		/* 在ht[1]-ht[i]的范围内找parent为0,且weight最小的结点s1和s2 */
		findMin(ht,i,&s1);
		ht[s1].parent = i+1;
		findMin(ht, i, &s2);
		ht[s2].parent = i+1;

		ht[i + 1].weight = ht[s1].weight + ht[s2].weight;
		ht[i + 1].parent = 0;
		ht[i + 1].left = s1;
		ht[i + 1].right = s2;
	}
	return ht;
}

void CreateHuffmanCode(HTree ht, int n, char *hc[])
{
	int c, p;   // 分别表示孩子结点和双亲结点的下标
	char *cd = (char *)malloc(n*sizeof(char));
	cd[n - 1] = '\0';  // 从右向左逐位存放编码，首先存放编码结束符
	/* 求n个叶子结点对应的哈夫曼编码 */
	for (int i = 1;i <= n;i++)
	{
		int start = n - 1;  // 初始化编码起始指针
		/* 从叶子结点开始向上倒推 */
		c = i;
		p = ht[c].parent;
		while (p != 0)
		{
			start--;
			if (ht[p].left == c)   // 左分支标0
				cd[start] = '0';
			else                   // 右分支标1
				cd[start] = '1';
			c = p;
			p = ht[c].parent;   // 向上倒推
		}
		hc[i] = (char* )malloc((n-start)*sizeof(char));
		strcpy(hc[i], &cd[start]);
	}
	free(cd);
}