(18分)实现和使用平衡二叉树(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 kl;
_______________a)(3分)
k2->height =MAX(Height(k2->1eft),Height(k2->right))+1;
k1->height=MAX(Height(kl->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)
}
查看答案和解析【26考研辅导课程推荐】：26考研集训课程,VIP领学计划,26考研VIP全科定制套餐（公共课VIP＋专业课1对1） , 这些课程中都会配有内部讲义以及辅导书和资料，同时会有教研教辅双师模式对大家进行教学以及督学，并配有24小时答疑和模拟测试等，可直接咨询在线客服老师领取大额优惠券。
启航教育热门私房课
MORE小班面授 名额有限 抢先体验
为你推荐
编辑推荐
最新内容
姓名
手机号
