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

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

1、实验报告课程名:数据结构（C语言版） 实验名：二叉排序树 姓名：班级：学号：撰写时间：2023.1 2.18int i ;/逐个结点插入二叉树中for (i=0; ilen g t h ;i + + ) insea r t (r o o t , ke y Array i )； int ma i n ( v o id) (int i;PNode r o ot= NULL;KeyTyp e node Arra y 1 1 = 1 5, 6, 1 8, 3, 7, 17, 20, 2, 4,13, 9)；create (&root, nodeA r ray, 11);fo r ( i =0;ik e

2、 y)；p r i ntfse a rchSucc e sso r (roo t )-ke y );p r intf ( %d n ，s ea r c h Min(ro o t) ke y );p r in t f ( %d n n , s e ar c hM a x (ro o t ) -k e y)；prin tf (dn，se a rch (root, 13)-k e y);r e t ur n 0；, C:UsersAdministratorDesktopVS 据结的-Debug二叉树排序.exe131822013Press any key to cont inue图1:二义树排序实验

3、结果一实验目的与规定1 .掌握二叉排序树上进行插入和删除的操作2 .运用C语言实现该操作二实验内容对于一个线形表，运用不断插入的方法，建立起一株二叉排序树从该二叉排序树中删除一个叶子节点，一个只有一个子树的非叶子节，一 个有两个子树的非叶子节点。三实验结果与分析#incl u de#inclu d e二叉查找树结点描述t y pe d ef i nt KeyType；ty p e d e f s truct Node(KeyTy p e key；/ / 关键字str u ct Node * 1 eft; 左孩子指针stru c t Node * r i ght； / / 右孩子指针struct

4、 Nod e * p a rent； /指向父节点指针N o de, *PNod e ；/往二叉查找树中插入结点插入的话,也许要改变根结点的地址,所以传的是二级指针v oid i n seart (PNod e * r oot, Ke y Type key)/初始化插入结点PNod e p=( PNo d e) malloc (sizeo f (Node);p -ke y = k ey;p-left=p- r ight= p -par e n t=NU L L ;空树时，直接作为根结点if (*root) = NULL) * r oot=p;r e turn；/插入到当前结点(*roo t )

5、的左孩子if (*r o o t )- 1 eft = NUL L & & (*root)-k e y k e y) p-p a ren t =(* r oot)；(* r o o t )-left=p;r e tu r n;插入到当前结点(* root)的右孩子i f (* r o ot)-r i g h t = NULL & (* r oot) -k e y pa r ent= (*root);(* r oo t ) righ t =p;r et u r n;if (*root) -k e y key)insear t (&(*ro o t )-left, key);else if ( (

6、 *roo t )-key r ight, key)；e 1 seret u rn;查找元素,找到返回关键字的结点指针,没找到返回NULLPNode se a rch(PN o de root, Key Type ke y ) (if(root = NULL)r e turn NULL；if (key roo t - k e y) 查找右子树r e turn search (root -ri g h t , key);else i f (k e y k ey)/ /查找左子树r e turn search (root lef t , key);elseret u rn root;查找最小关键字

7、,空树时返回NULLPNod e s ea r chM in (PN o de ro o t)(if( r oot = NULL)return NULL;if (ro o t-l eft = NULL)return root;els e/ /一直往左孩子找，直到没有左孩子的结点ret urn searc h Min (root- 1 ef t );查找最大关键字,空树时返回NULLPNode sea r c h M a x (PNo d e roo t )(if(root = NULL)ret urn NULL;if(root-right = NULL)r e turn root；else 一

8、直往右孩子找，直到没有右孩子的结点 return se a rchMax (root-rig h t);)查找某个结点的前驱PN o de sear c h P red ece s sor (P Node p)(/空树if(p=NUL L)r e t u rn p;/有左子树、左子树中最大的那个if (p-lef t )re t urn sear chMa x (p- 1 eft);/无左子树，查找某个结点的右子树遍历完了e 1 s e if (p-pare n t = = NULL)re t urn NULL；向上寻找前驱w h i 1 e (p) if (p-parent-righ t =

9、 p)b reak;p=p-pa rent；)r e turn p-parent;I/查找某个结点的后继P N o d e s ea r c hSuc c e s s or (PNode p )(空树i f(p=NULL)ret u rn p;有右子树、右子树中最小的那个i f (p- r igh t )return s earchMin(p- r igh t );/ /无右子树,查找某个结点的左子树遍历完了 elsei f (p paren t = NULL)r eturn NULL ；/向上寻找后继while(p) i f (p-par e n t-lef t = p)b r e ak;p

10、=p -parent;)ret urn p-p a rent;)/根据关键字删除某个结点，删除成功返回1,否则返回0/假如把根结点删掉，那么要改变根结点的地址,所以传二级指针 int dele t eNode (PNode* r o o t, KeyType key)(PNod e q；/查找到要删除的结点PN o de p= s earc h (* root, key);KeyType temp; /暂存后继结点的值没查到此关键字if (1p)retu r n 0;/I.被删结点是叶子结点，直接删除if (p- left = NULL & p-ri g h t = NULL)(只有一个元素,

11、删完之后变成一颗空树if(p-paren t = NUL L) f r e e(p );(* r oot) =NULL； else/删除的结点是父节点的左孩子if (p- p arent-lef t = p)p -p are nt 1 e f t=NULL;else /删除的结点是父节点的右孩子p-par e nt-r i ght二NULL;fre e (p);)2.被删结点只有左子树e 1 se if (p-l e ft & ! (p r i ght) pleft pa r e n t= p -pa r ent；/假如删除是父结点，要改变父节点指针i f (p-par ent = NULL)

12、*r o ot=p-le f t ；删除的结点是父节点的左孩子else i f (p -pa r e nt-le f t = p )p-pa r e n t-le f t= p -left;else 删除的结点是父节点的右孩子p -pa r ent-right=pleft;f r ee (p);3.被删结点只有右孩子else if (p-right & ! (p- 1 e ft) p ri g ht pa r cnt=p-par e n t ;/假如删除是父结点,要改变父节点指针i f (p-parent = NULL)*r o o t = p -right;/ /删除的结点是父节点的左孩子e

13、lse if (p-paren t - 1 eft = = p)pparent-l e ft=p-right;eIse 删除的结点是父节点的右孩子 p-pa r on t -r i g h t= p right;f ree(p)；/4.被删除的结点既有左孩子,又有右孩子/该结点的后继结点肯定无左子树(参考上面查找后继结点函数) 删掉后继结点,后继结点的值代替该结点e 1 se找到要删除结点的后继q=se a r ch S u ccessor (p)；tem p =q-key;/删除后继结点d eleteNod e ( r o ot, q key);p-ke y = t emp;)re t urn 1;)/ /创建一棵二叉查找树void create (PNodc* roo t , Key T ype * kcyArra y , int length)