2023年数据结构二叉排序树实验报告.pdf

《2023年数据结构二叉排序树实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构二叉排序树实验报告.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验报告课程名:数据结构（C 语言版）实验名：二叉排序树姓名：班级：学号：撰写时间:2023.1 2.18一 实验目的与规定1 .掌握二叉排序树上进行插入和删除的操作2 .运 用 C 语言实现该操作二 实验内容对于一个线形表，运用不断插入的方法，建立起一株二叉排序树 从该二叉排序树中删除一个叶子节点，一个只有一个子树的非叶子节，一个有两个子树的非叶子节点。三 实验结果与分析#in cl u det t in cl u d e二叉查找树结点描述t y pe d ef i n t K eyT ype；t y p e d e f s t ruct N odeK eyT y p e k ey；/关键字

2、st r u ct N ode*1 eft;左孩子指针st ru c t N ode*r i ght；/右孩子指针st r u ct N ode*p a ren t；/指向父节点指针N o de,*P N od e；/往二叉查找树中插入结点插入的话,也许要改变根结点的地址,所以传的是二级指针v oid i n seart (P N od e*r oot,K e y T ype k ey)/初始化插入结点P N od e p=(P N o d e)m al l oc(siz eo f(N ode);p-k e y=k ey;p-l eft=p-r ight=p-par e n t=N U L L

3、 ;空树时，直接作为根结点if(root)=N U L L)*r oot=p;r e t urn；/插入到当前结点(*roo t )的左孩子i f(*r o o t )-1 eft =N U L L&(*root)-k e y k ey)p-p a ren t =(*r oot)；(*r o o t )-l eft=p;r e t u r n;)插入到当前结点(*root)的右孩子i f(*r o ot)-r i g h t =N U L L&(*r oot)-k e y p a r en t=(*root);(*r oo t )righ t =p;r et u r n;if(*root)-k

4、 e y k e y)in sear t (&(*roo t )-l eft,k ey);el se if(*root)-k ey right,k ey)；e 1 seret u rn;查找元素,找到返回关键字的结点指针,没找到返回N U L LP N ode se a rch(P N o de root,K ey T ype k e y)if(r o ot =N U L L)r e t urn N U L L；if(k ey roo t -k e y)查找右子树r e t urn s e a r c h (root -ri g h t ,k ey);el se i f(k e y k ey)

5、/查找左子树r e tu r n search(root l ef t ,k e y);el seret u rn root;查找最小关键字,空树时返回N U L LP N od e s ea r chM in(P N o de ro o t)(if(root =N U L L)ret urn N U L L;if(ro o t-l eft =N U L L)ret urn root;el s e/一直往左孩子找，直到没有左孩子的结点ret u r n searc h M in (root-1 ef t );)查找最大关键字,空树时返回N U L LP N ode sea r c h M a

6、x(P N o d e roo t )if(r o ot =N U L L)ret u r n N U L L;if(root-right =N U L L)r e t urn root；el se 一直往右孩子找，直到没有右孩子的结点re t urn se a rchM ax(root-rig h t);查找某个结点的前驱P N o de sear c h P red ece s sor(P N ode p)(/空树if(p=N U L L )r e t u rn p;/有左子树、左子树中最大的那个if(p-l ef t )re t urn sear chM a x(p-1 eft);/无左

7、子树.，查找某个结点的右子树遍历完了e 1 s e if(p-pare n t =N U L L)re t urn N U L L；向上寻找前驱w h i 1 e(p)if(p-p a r e n t-r i g h t =p)b reak;p=p-pa r e nt；)r e t urn p-paren t;)卜/查找某个结点的后继P N o d e s ea r c hS uc c e s s or(P N ode p)(空树i f(p=N U L L)ret u rn p;/有右子树、右子树中最小的那个i f(p-r igh t )ret urn s earchM in (p-r ig

8、h t );/无右子树,查找某个结点的左子树遍历完了el se i f(p paren t =N U L L)r et urn N U L L ；/向上寻找后继whil e(p)i f(p-par e n t-l ef t =p)b r e ak;p=p-paren t;r e t urn p-p a ren t;)根据关键字删除某个结点，删除成功返回1,否则返回0/假如把根结点删掉，那么要改变根结点的地址,所以传二级指针in t del e t eN ode(P N o d e*r o o t,K eyT ype k e y)(P N od e q；/查找到要删除的结点P N o de p=

9、s earc h(*root,k ey);K eyT ype t em p;/暂存后继结点的值没查到此关键字if(!p)ret u r n 0;/I.被删结点是叶子结点，直接删除if(p-l e f t =N U L L&p-ri g h t =N U L L)只有一个元素,删完之后变成一颗空树if(p-paren t =N U L L)f r e e(p);(*r oot)=N U L L；el se/删除的结点是父节点的左孩子if(p-p aren t-l ef t =p)p-p are n t 1 e f t=N U L L;el se/删除的结点是父节点的右孩子p-par e n t-

10、r i g ht=N U L L;fre e(p);)/2.被删结点只有左子树e 1 se if(p-l e ft&!(p r i ght)p-l eft pa r e n t=p-pa r en t；/假如删除是父结点，要改变父节点指针i f(p-par en t =N U L L)*r o ot=p-l e f t ；删除的结点是父节点的左孩子el se i f(p-pa r e n t-l e f t =p)p-pa r e n t-l e f t=p-l eft;el se 删除的结点是父节点的右孩子p-pa r en t-right=p l eft;f r ee(p);)/3.被删结

11、点只有右孩子el se if(p-right&!(p-1 e ft)p ri g ht pa r en t=p-par e n t ;/假如删除是父结点,要改变父节点指针i f(p-paren t =N U L L)*r o o t =p-right;/删除的结点是父节点的左孩子e l s e if(p-paren t -1 eft =p)p paren t-l e ft=p-right;e l s e 删除的结点是父节点的右孩子p-pa r en t -r i g h t=p right;f ree(p)；)/4.被删除的结点既有左孩子，又有右孩子/该结点的后继结点肯定无左子树(参考上面查找

12、后继结点函数)删掉后继结点,后继结点的值代替该结点e 1 se找到要删除结点的后继q=se a r ch S u ccessor(p)；t em p=q-k ey;/删除后继结点d el et eN od e(r o ot,q k ey);p-k e y=t em p;)re t urn 1;/创建一棵二叉查找树void creat e(P N ode*roo t ,K ey Type*k eyA rray,in t l en gt h)in t i ;/逐个结点插入二叉树中for(i=0;il en g t h;i+)in sea r t (r o o t ,k e y A rray i )

13、；in t m a i n (v o id)(in t i;P N ode r o ot =N U L L;K eyT yp e n ode A rra y 1 1 =1 5,6,1 8,3,7,1 7,2 0,2,4,1 3,9;creat e(&root,n odeA r ray,1 1);fo r(i =0;i k e y)；p r i n t f(/z%d n/z,se a rchS ucc e sso r(roo t )-k e y);p r in t f(%d n ，s ea r c h M in(ro o t)k e y);p r in t f(”%d n n,s e ar c hM a x(ro o t )-k e y)；p r i n t f(dn，se a rch(root,1 3)-k e y);r e t ur n 0；131822013Press any key to continue图 1:二叉树排序实验结果