北邮 数据结构 平衡二叉树报告

《北邮 数据结构 平衡二叉树报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告实验名称：平衡二叉树第8页实验目的和内容根据平衡二叉树的抽象数据类型的定义，使用二叉链表实现一个平衡二叉树。二叉树的基本功能：1、平衡二叉树的建立2、平衡二叉树的查找3、平衡二叉树的插入4、平衡二叉树的删除5、平衡二叉树的销毁6、其他：自定义操作编写测试main()函数测试平衡二叉树的正确性。2.程序分析2.1存储结构structnode{intkey;//值intheight;//这个结点的父节点在这枝最长路径上的结点个数node*left;//左孩子指针node*right;//右孩子指针node(int

2、k){key=k;left=right=0;height=1;}//构造函数};2.2程序流程插入结点构建排序二叉树小于根节点？插入右枝插入左枝是第8页左/右为空根节点下移是插入平衡？平衡否2.3关键算法分析（由于函数过多，在此只挑选部分重要函数）算法1：voidAVL_Tree::left_rotate(node*&x)[1]算法功能：对R-R型进行调整[2]算法基本思想：将结点右孩子进行逆时针旋转[3]算法空间、时间复杂度分析：都为0（1）[4]代码逻辑node*y=x->right;y为x的右孩子x->right=y-

3、>left;将y的左孩子赋给x的右孩子y->left=x;x变为y的左孩子fixheight(x);修正x，y的height值fixheight(y);x=y;使x的父节点指向y算法2：voidAVL_Tree::right_rotate(node*&x)[1]算法功能：对L-L型进行调整[2]算法基本思想：将左孩子进行顺时针旋转[3]算法空间、时间复杂度分析：都为0（1）[4]代码逻辑node*y=x->left;//y为x的左孩子x->left=y->right;y的右孩子赋给x的左孩子第8页y->right=x;x变为

4、y的右孩子fixheight(x);修正x和y的height值fixheight(y);x=y;使x的父节点指向y算法3：node*&AVL_Tree::balance(node*&p)[1]算法功能：对给定结点进行平衡操作[2]算法基本思想：通过平衡因子判断属于哪种情况，再依照情况进行平衡[3]算法空间、时间复杂度分析：没有递归和循环，都为O（1）[4]代码逻辑fixheight(p);//修正P的height值if(bfactor(p)==2)平衡因子为2，为L-？型if(bfactor(p->left)<0)P的左孩子

5、平衡因子<0时，为L-R型，执行left_rotate(p->left);相关平衡操作，若>0，为L-L型。right_rotate(p);}elseif(bfactor(p)==-2)平衡因子为2，为R-?型{if(bfactor(p->right)>0)P的右孩子平衡因子>0，为R-L型right_rotate(p->right);小于0时，为R-R型left_rotate(p);}fixheight(p);修正平衡后的P的height值returnp;算法4：node*AVL_Tree::remove(node*&p,

6、intk)[1]算法功能：删除给定key值的结点[2]算法基本思想：首先通过递归找到待删除结点，如果其没有右孩子，直接将其删除，将其左孩子链上去。若有右孩子，找到右枝中的最小结点代替待删除结点，对改变后的结点进行平衡。注意右孩子要删除其中的最小结点第8页[3]算法空间、时间复杂度分析：有递归，递归次数最多为深度，时间复杂度0（nlogn），空间复杂度0（logn）[4]代码逻辑if(kkey)K小于根节点，在左枝中寻找p->left=remove(p->left,k);递归elseif(k>p->key)K大于根节点

7、，在右枝中寻找p->right=remove(p->right,k);递归else找到待删除结点{node*q=p->left;q为删除结点的左孩子node*r=p->right;p为删除结点右孩子deletep;if(!r)//没有右子树returnq;直接将左孩子返回，相当于直接删除pnode*min=findmin(r);//有右子树时，找到右枝中的最小值min->right=removein(r);使删除最小值后的右枝变为min的右枝min->left=q;p的左孩子变为min的左孩子，相当于删除了p，balance

8、(min);对min进行balance操作returnmin;}balance(p);每次递归完都对p进行平衡操作returnp;算法5：voidAVL_Tree::insert(node*&p,intk)[1]算法功能：一边插入结点一边进行平衡[2]算法基本思想：按照构建排序二叉树的方法