二叉平衡排序树.docx

《二叉平衡排序树.docx》由会员分享，可在线阅读，更多相关《二叉平衡排序树.docx（19页珍藏版）》请在第一文库网上搜索。

1、数据结构课程设计报告专业：计算机科学与技术班级：2009级1姓名：陈雪敏指导教师：张珑学号：2009040608二叉平衡排序树一、课程设计内容问题描述：从一棵空树开始创建，在创建过程中，保证树的有序性，同时还要针对树的平衡性做些调整。最终要把创建好的二叉排序树转换为二叉平衡排序树。基本要求：1创建(插入、调整、改组)2.输出二、概要设计1、.主要数据结构定义typedefstructnodenode;structnodenode*parent;node*1eft;node*right;intba1ance;左右子树高度之差intkey;I.2：主要函数说明intSearchNode(intke

2、y,node*root,node*parent)：按key查找结点node*minNode(node*root)：树root的最小结点node*maxNode(node*root)：树root的最大结点node*preNode(node*target)：求前驱结点node*nextNode(node*target)：求后继结点node*adjustAV1(node*root,node*parent,node*chi1d)：调整，保证二叉树的平衡性node*insertNode(intkey,node*root)：插入node*de1eteNode(intkey,node*root)：删除nod

3、e*CreateAV1(int*data,intsize)：建造新的二叉树voidinterordertraverse(node*root)：中序遍历voidpreordertraverse(node*root)：先序遍历3、二叉排序树的插入和删除a.二叉排序树的插入在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。插入过程：若二叉排序树已存在，则返回根节点；当节点不存在时，将待插结点关键字key和树根关键字parent-key进行比较，若keykey,则插入到根的左子树中，否则，则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点作为一

4、个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。并且注意二叉树的平衡性，时刻调整。b.二叉排序树的删除假设在二叉排序树上被删结点为*tp,其双亲结点为*parent,且不失一般性，可设*parent是*Parent-1eft;的左孩子。下面分3种情况进行讨论：(1)若*parent结点为叶子结点，即P1和PR均为空树。由于删去叶子结点不破坏整棵树的结构，则只需要修改其双亲结点的指针即可。(2)若*parent结点只有左子树P1或者只有右子树PR,此时只要令P1或PR直接成为其双亲结点*f的左子树即可。显然，作此修改也不破坏二叉排序树的特性。(3)若*parent结点的左子

5、树和右子树均不空。并且注意二叉树的平衡性，时刻调整。4、中序遍历和先序遍历voidinterordertraverse(node*root)中序遍历(if(root!=NU11)(interordertraverse(root-1eft);printf(,%d,%dn”,root-key,root-ba1ance);interordertraverse(root-right);)voidpreordertraverse(node*root)先序遍历if(root!=NU11)printf(z,%d,%dn”,root-key,root-ba1ance);preordertraverse(roo

6、t-1eft);preordertraverse(root-right);1J5、调整二叉树的平衡性node*adjustAV1(node*root,node*parent,node*chi1d)主要有四种调整类型根据平衡因子主要有1R、11、R1、RR(1)根据Parent-ba1ance的值为2时，chi1d-ba1ance=-1时是1R型，否则为11型；if(chi1d-ba1ance=-1)1R型(cur-chi1d-right;cur-parent=parent-parent;chi1d-right=cur-1eft;if(cur-1eft!=NU11)cur-1eft-parent

7、=chi1d;parent-1eft=cur-right;if(cur-right!=NU11)cur-right-parent-parent;cur-1eft=chi1d;chi1d-parent-cur;cur-right=parent;if(parent-parent!-NU11)if(parent-parent-1eft=parent)parent-parent-1eft-cur;e1separent-parent-right=cur;e1seroot=cur;parent-parent-cur;if(cur-ba1ance=0)parent-ba1ance=0;chi1d-ba1an

8、ce=0;)e1seif(cur-ba1ance=-1)(parent-ba1ance-0;chi1d-ba1ance=1;e1separent-ba1ance=-1;chi1d-ba1ance-0;)cur-ba1ance=0;)e1se/11型chi1d-parent-parent-parent;parent-1eft=chi1d-right;if(chi1d-right!=NU11)chi1d-right-parent=parent;chi1d-right=parent;if(parent-parent!=NU11)if(parent-parent-1eft=parent)parent-

9、parent-1eft=chi1d;e1separent-parent-right-chi1d;e1seroot=chi1d;parent-parent=chi1d;if(chi1d-ba1ance=1)插入时chi1d-ba1ance-O;parent-ba1ance=O;)e1se删除时chi1d-ba1ance=-1;parent-ba1ance-1;)break;(2)、Parent-ba1ance的值为-2时，chi1d-ba1ance=1时是R1型，否则为RRif(chi1d-ba1ance=1)/R1型(cur=chi1d-1eft;cur-parent=parent-paren

10、t;chi1d-1eft=cur-right;if(cur-right!=NU11)cur-right-parent=chi1d;parent-right=cur-1eft;if(cur-1eft!=NU11)cur-1eft-parent=parent;cur-1eft=parent;cur-right=chi1d;chi1d-parent-cur;if(parent-parent!=NU11)if(parent-parent-1eft=parent)parent-parent-1eft=cur;e1separent-parent-right=cur;e1seroot-cur;parent-

11、parent=cur;if(cur-ba1ance=0)(parent-ba1ance=0;chi1d-ba1ance=0;e1seif(cur-ba1ance=1)parent-ba1ance=0;chi1d-ba1ance-1;)e1se(parent-ba1ance-1;chi1d-ba1ance=O;cur-ba1ance=O;)e1se/RR型chi1d-parent=parent-parent;parent-right=chi1d-1eft;if(chi1d-1eft!=NU11)chi1d-1eft-parent=parent;chi1d-1eft=parent;if(paren

12、t-parent!-NU11)if(parent-parent-1eft=parent)parent-parent-1eft-chi1d;e1separent-parent-right=chi1d;e1seroot=chi1d;parent-parent-chi1d;if(chi1d-ba1ance=-1)插入时chi1d-ba1ance=0;parent-ba1ance=0;e1se删除时chi1d-ba1ance-1;parent-ba1ance=-1;)break;6、主函数Voidmain()给出了一组数据1,13,7,4),对数据中序遍历和先序遍历，然后是插入、删除、查询、退出操作。

13、三、系统实现运行环境Windows7操作系统，MicrosoftVisua1C+6.0。四、程序#inc1udeinc1ude#inc1ude#inc1ude#inc1udeinc1ude/assert用于调试声明宏，用于定位程序开发中的逻辑错误当参数expression为fa1se时程序执行被中断tjedefstructnodenode;structnodenode*parent;node*1eft;node*right;intba1ance;平衡因子(左右子树高度之差)intkey;)；externvoidinterordertraverse(node*root);中序遍历externvo

14、idpreordertraverse(node*root);前序遍历intSearchNode(intkey,node*root,node*parent)按key查找结点(node*temp;assert(root!=NU11);temp=root;*parent=root-parent;whi1e(temp!=NU11)(if(temp-key=key)return1;e1se*parent=temp;if(temp-keykey)temp=temp-1eft;e1setemp=temp-right;returnO;)node*minNode(node*root)树root的最小结点returnNU11;whi1e(root-1eft!=NU11)root=root-1eft;returnroot;node*max