试题出自试卷《西安电子科技大学2017年833计算机学科专业基础综合真题解析》

实现和使用平衡二叉树（AVL树）的插入构造算法。

（1）对于元素序列{3，2，1，4，5，6，7，16，15，14，13，12，11，10，8，9}，画出依序插入平衡二叉树后，平衡二叉树的结果。（5分）
（2）写出该平衡二叉树的后序遍历结果。（2分）
（3）将以下AVL树插入构造算法的片段补充完整。（11分）

typedef struct AVLTreeNode{
	int key;                    //键值
	int height;
	struct AVLTreeNode *left;   //左孩子
	struct AVLTreeNode *right;  //右孩子
}Node,*AVLTree;

int Height(AVLTree p){return (p==NULL)?-1:p->height;}
int MAX(int a, int b){return a>b?a:b;}
void postorder_avltree(AVLTree tree){···/*后序遍历AVL树*/}

/*LL：左单旋转。返回值：旋转后的根节点*/
static Node* LL_Rotation(AVLTree k2){
	AVLTree k1;
a）（3分）
	k2->height=MAX(Height(k2->left),Height(k2->right))+1;
	k1->height=MAX(Height(k1->left),k2->height)+1;
	return k1;
}

/*RR：右单旋转。返回值：旋转后的根节点*/
static Node* RR_Rotation(AVLTree k1){
	AVLTree k2;
b）（3分）
	k1->height=MAX(Height(k1->left),Height(k1->right))+1;
	k2->height=MAX(Height(k2->right),k1->height)+1;
	return k2;
}

/*LR：左双旋转。返回值：旋转后的根节点*/
static Node* LR_Rotation(AVLTree k1){
	k1->left= c）（1分）    
	return LL_Rotation(k1);
}

/*RL：右双旋转。返回值：旋转后的根节点*/
static Node* RL_Rotation(AVLTree k1){
	k1->right= d）（1分） 
	return RR_Rotation(k1);
}

/*创建AVL树结点。*/
static Node* avltree_create_node(int key, Node *left,Node* right){
	Node *p;
	if((p=(Node*)malloc(sizeof(Node)))==NULL)
		return NULL;
	p->key=key;
	p->height=0;
	p->left=left;
	p->right=right;
	return p;
}

/*将结点插入到AVL树中，并返回根节点。
参数: tree为AVL树 的根结点; key为插入的结点的键值*/
Node* avltree_insert(AVLTree tree, int key){
	if (tree == NULL) { //新建节点
		tree = avltree_create_node(key, NULL, NULL);
		if (tree==NULL){ //创建AVL树节点失败
			return NULL;
		}
	}
	else if (key < tree->key){ //将key插入tree的左子树
		tree->left = avltree_insert(tree->left, key);
		if (Height(tree->left) - Height(tree->right) == 2) {
			//插入节点后AVL树失去平衡，进行调节
			if (key < tree->left->key)
				tree=LL_Rotation(tree);
			else
				tree= e）（1分） 
		}
	}
	else if (key > tree->key){ //将key插入tree的右子树
		tree->right = avltree_insert(tree->left, key);
		if (Height(tree->right) - Height(tree->right) == 2) {
			//插入节点后AVL树失去平衡，进行调节
			if (key > tree->right->key)
				tree=RR_Rotation(tree);
			else
				tree= f）（1分） 
		}
	}
	else{   //key==tree->key
		printf("添加失败，已存在key相同的节点。\n");
	}
	tree->height= g）（1分） 
	return tree;
}

void main(){
	int arr[]={3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
	
	AVLTree root=NULL;
	for(int i=0;i<16;i++){
		root=avltree_insert(root,arr[i]);
	}
	postorder_avltree(root);
}