数据结构抽象数据类型的实现

1、数据结构实验报告 题目：二叉树 学 院 计算机学院 专 业 软件工程 年级班别 2010级 4 班 学 号 学生姓名 指导教师 成 绩 _2012年6月1、设计任务【Design Tasks】完成二叉树的17中基本操作。如：二叉树中插入、删除节点或一棵子树。求节点的双亲、孩子、兄弟节点等。2、设计思路【Design Ideas】2.1主函数设计框图X = 0YN结束通过switch()函数选择基本操作开始2.2 基本操作函数设计框图主函数随机生成二叉树新建二叉树嵌套输出二叉树二叉树深度节点的双亲根节点遍历二叉树节点的孩子节点的兄弟删除子树删除节点插入节点修改节点的值查找节点的值插入子树摧毁二叉

2、树清空二叉树凹进输出二叉树先序遍历中序遍历后序遍历层次遍历左孩子右孩子左兄弟右兄弟1. 所有的分支通过switch()函数实现。2. 在遍历、找节点孩子和节点的兄弟时，通过while()实现循环。3. 实现插入删除子树和插入删除节点,注意节点的重新连接。3、部分代码分析【Code Analysis】3.1插入子树分析：1、通过建立队列，采用层次遍历查找要插入子树的双亲x，在通过Flag标志，决定插入的是左子树还是右子树。2、if( p-data = x & ( ( flag = 0 & p-lchild = NULL) | ( flag = 1 & p-rchild = NULL ) ) )。

3、找到双亲节点时，如果插入的是左子树，则其双亲的左孩子必须是空的；如果插入的是右子树，则其双亲的右孩子必须是空的。 3、通过f标志，判断是否查找成功。void Enter( BTree &T, BTree s, elemtype x, int flag )BTree p = T;int f=0;LinkQueue Q;InitQueue(Q); /建立工作队列EnQueue(Q,T);/*按层次遍历查找x节点*/while( !QueueEmpty(Q) ) DeQueue( Q,p );/*可建立子树的条件*/if( p-data = x & ( ( flag = 0 & p-lchild =

4、 NULL) | ( flag = 1 & p-rchild = NULL ) ) )f=1;/查找成功break;if( p-lchild ) EnQueue( Q,p-lchild );if( p-rchild ) EnQueue( Q,p-rchild );/*如果 flag = 0 则建立该节点的左子树* flag = 1 则建立该节点的右子树*/if( f )switch( flag )case 0: p-lchild = s; break;case 1: p-rchild = s; break;Print_tree( T );cout 插入成功!endl;elsePrint_tre

5、e( T );cout 插入失败!lchild; p-lchild = NULL;dispose(q);break;case 1: q = p-rchild; p-rchild = NULL; dispose(q);break;查找成功时，要重新连接节点。同时释放删除子树的空间3、通过f标志，判断是否查找成功。void DeleChild( BTree &T, elemtype x, int flag )BTree p = T, q;int f=0;LinkQueue Q;InitQueue(Q); /建立工作队列EnQueue(Q,T);/*按层次遍历查找x节点*/while( !Queue

6、Empty(Q) ) DeQueue( Q,p );if( p-data = x )f=1;/删除成功break;if( p-lchild ) EnQueue( Q,p-lchild );if( p-rchild ) EnQueue( Q,p-rchild );/*如果 flag = 0 则删除该节点的左子树* flag = 1 则删除该节点的右子树*/if( f )switch( flag )case 0: q = p-lchild; p-lchild = NULL;dispose(q);break;case 1: q = p-rchild; p-rchild = NULL; dispose

7、(q);break;Print_tree( T );cout 删除成功!endl;elsePrint_tree( T );cout 删除失败!data = x & ( ( p-lchild-lchild = NULL ) | ( p-lchild-rchild = NULL ) | ( p-rchild-lchild = NULL ) |( p-rchild-rchild = NULL ) ) )，只有在删除节点的度为1时才满足条件。2、 查找成功后要重新连接节点switch( flag )case 0: q = p-lchild;if( q-lchild != NULL )p-lchild

8、= q-lchild;/*双亲节点的左孩子域指向删除节点的左孩子*/elseif( q-rchild != NULL )p-lchild = q-rchild;/*双亲节点的左孩子域指向删除节点的右孩子*/elsep-lchild = NULL;/当删除的节点左右孩子都是空时，p-lchild为空free(q);break;case 1:q = p-rchild;if( q-lchild != NULL )p-rchild = q-lchild;/*双亲节点的右孩子域指向删除节点的左孩子*/elseif( q-rchild != NULL )p-rchild = q-rchild;/*双亲节点

9、的右孩子域指向删除节点的右孩子*/elsep-rchild = NULL;/当删除的节点左右孩子都是空时，p-rchild为空free(q);break;4、部分测试结果【Test Result】4.1、系统界面4.2、主界面4.3、二叉树遍历界面4.4、嵌套输出二叉树4.5、查找双亲节点4.6、查找孩子节点4.7、查找兄弟节点4.8、删除子树4.9、删除节点4.10、插入节点4.11、插入子树4.12、查找节点4.13、修改节点5、总结【summary】5.1、通过这次试验，我熟练掌握了二叉树的所有基本操作，很好的做到了学以自用。5.2、二叉树在查找、删除效率高，经常用到文件级中的排序，是一

10、个经常用到的一种结构。5.3、该实验虽然不难，但操作起来就会遇到很多困难，比如：各个操作之间的相互连接。6、源代码【source code】5.1、主函数main()/运行环境：vc+6.0/学生：江达强/学号：/#includetree.hvoid Menu();void OrderTreaverse_Menu();void Find_child();void Find_Sibling();void main()int x,count;BTree tree,root, bt,t;char e,ch;elemtype value,a;int flag,deep;char stMAXSIZE;s

11、ystem(color 2B);InitBiTree( tree, a(b(,d),c(e) );while(1) int choice;Menu();printf(ntttt请选择您需要的操作(0-18):); scanf(%d,&x);getchar(); switch(x)case 0:cout随机生成二叉树!endl;srand( (unsigned)time( NULL ) );InitBiTree( tree, Treerand()%5);if(BiTreeEmpty( tree ) )cout 该树是空树! endl;elsecout 该树不是空树!endl;break;case

12、 1:cout请输入新的二叉树(如:a(b(c),c(,b)形式:st;InitBiTree( tree, st);if(BiTreeEmpty( tree ) )cout 该树是空树! endl;elsecout 该树不是空树!endl;break; case 2:cout嵌套输出二叉树endl;Print_tree( tree );coutendl;break;case 3: deep = BiTreeDepth( tree );coutn 该树的深度为: deepchoice;switch( choice )case 1: cout先序遍历:endl;PreOrderTreaverse(

13、 tree ,visit );coutendl;break;case 2: cout中序遍历:endl;InOrderTreaverse( tree, visit );coutendl;break;case 3: cout后序遍历:endl;PostOrderTreaverse( tree, visit );coutendl;break;case 4: cout层次遍历:endl;LevelOrderTreaverse( tree, visit );coutendl;break;case 0:break;default:cout输入错误!endl;if( !choice )break;brea

14、k;case 5: root = Root( tree );cout该树根节点为: dataendl;break;case 6: coutvalue;a = Parent( tree, value );if( a != 0 )coutn该节点的双亲为: aendl;elsecout无双亲节点choice;if( choice )coutvalue;switch( choice )case 1:a = LeftChild( tree, value );if( a != 0 )coutn该节点的左孩子为: aendl;elsecout该节点无左孩子endl;break;case 2:a = Rig

15、htChild( tree, value );if( a != 0 )coutn该节点的右孩子为: aendl;elsecout该节点无右孩子endl;break;case 0:break;default:cout输入错误!choice;if( choice )coutvalue;switch( choice )case 1:a = LeftSibling( tree, value );if( a != 0 )coutn该节点的左兄弟为: aendl;elsecout该节点无左兄弟endl;break;case 2:a = RightSibling( tree, value );if( a !

16、= 0 )coutn该节点的右兄弟为: aendl;elsecout该节点无右兄弟endl;break;case 0:break;default:cout输入错误!endl;if( !choice )break;break;case 9: coutn输入要删除的节点的双亲节点的值ch;cout输入是删除左(0)还是右子树(1):flag;DeleChild( tree, ch, flag );/Print_tree( tree );break;case 10:cout输入删除的节点的双亲节点的值ch;cout输入是删除左(0)还是右节点(1):flag;DeleChild_Node( tree

17、, ch, flag );/Print_tree( tree );break;case 11:cout插入一个节点!endl;cout请输入要插入节点值ch;coutn请输入这个节点的双亲节点:value;cout请输入要插入的是左节点(0)还是右节点(1):flag;Enter_Node( tree, value, ch, flag );/Print_tree( tree );break;case 12:cout插入一个二叉树!endl;cout请输入要插入的二叉树(如:a(b(,d),c(f)形式:st;InitBiTree( t, st);/Print_tree( t );coutn请输

18、入要这棵子树的双亲节点:value;cout请输入要插入的是左子树(0)还是右子树(1):flag;Enter( tree, t, value, flag );break;case 13:coute;bt = Value( tree, e );if( bt != NULL )count = Count( tree, bt-data );if( bt != NULL )printf(节点 %c 存在tree树中的第 %d 个节点(按层次遍历)!n,e,count);elseprintf(节点 %c 不存在tree树中!n,e);break;case 14:coute;bt = Value( tr

19、ee, e );if( bt != NULL )printf(节点 %c 存在tree树中!n,e);elseprintf(节点 %c 不存在tree树中!n,e);if( bt != NULL )cout输入新值!value;Assign( tree, e, value );Print_tree( tree );/新增coutn修改成功!endl;break;case 15:DestroyBiTree( tree );cout摧毁成功!endl;break;case 16:ClearBiTree( tree );cout清空二叉树!endl;break;case 17:cout凹进形式输出二

20、叉树;Braverse_l( tree );break; case 18: printf(nttttt);time_t t;struct tm *now;t=time(0);now = localtime(&t);couttm_year+1900-tm_mon+1-tm_mdayendl;printf(nttttt);cout谢谢使用!endl;exit(0); default: printf(tttt输入信息错误,请重新输入!n); break; 5.2、菜单函数menu()#include#includevoid Menu() printf(nnntttt二叉树的抽象数据类型的实现nn);

21、 printf(ttttn);printf(tttt0. 随机生成二叉树 n); printf(tttt1. 新建二叉树 n); printf(tttt2. 嵌套输出二叉树 n);printf(tttt3. 二叉树深度 n); printf(tttt4. 遍历二叉树 n);printf(tttt5. 根节点 n);printf(tttt6. 节点的双亲 n); printf(tttt7. 节点的孩子 n);printf(tttt8. 节点的兄弟 n);printf(tttt9. 删除子树 n);printf(tttt10. 删除节点 n);printf(tttt11. 插入节点 n);prin

22、tf(tttt12. 插入子树 n);printf(tttt13. 查找节点的值 n);printf(tttt14. 修改节点的值 n);printf(tttt15. 摧毁二叉树 n);printf(tttt16. 清空二叉树 n);printf(tttt17. 以凹进输出二叉树n); printf(tttt18. 退出系统 n); printf(ttttn); void OrderTreaverse_Menu() printf(nnnttttt二叉树的遍历nn); printf(ttttn); printf(tttt1. 先序遍历 n); printf(tttt2. 中序遍历 n); pri

23、ntf(tttt3. 后序遍历 n);printf(tttt4. 层次遍历 n); printf(tttt0. 返回上级菜单 n); printf(ttttn); void Find_child() printf(nnntttt查找二叉树孩子节点nn); printf(ttttn); printf(tttt1. 左孩子 n); printf(tttt2. 右孩子 n); printf(tttt0. 返回上级菜单 n); printf(ttttn); void Find_Sibling() printf(nnntttt 查找二叉树兄弟节点nn); printf(ttttn); printf(tt

24、tt1. 左兄弟 n); printf(tttt2. 右兄弟 n); printf(tttt0. 返回上级菜单 n); printf(ttttn); 5.3、头文件tree.h#include#include#include#include#include#include#include#define MAXSIZE100 /*存储树字符串的最大值*/#define OK 1;#define TRUE 1;#define FALSE 0;#define ERROR 0;typedef int Status;typedef char elemtype;/*生成随机树数组，这里也可以通过一棵树来生

25、成任意的树*/char Tree5MAXSIZE= () ,(a), (a(b,c), (a(b(d,e),c), (a(b(d,e),c(f,g) ;/*存储树的结构体*/typedef struct nodeelemtype data;struct node *lchild,*rchild;*BTree,BTNode;/*存储队列的结构体*/typedef struct QNodeBTree data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;/*初始化队列

26、*/Status InitQueue( LinkQueue &Q )Q.front = Q.rear = ( QueuePtr )malloc(sizeof(QNode);if( Q.front = NULL )exit(1);Q.front -next = NULL;return OK;/*入队列*/Status EnQueue( LinkQueue &Q, BTree &e )QueuePtr p;p = ( QueuePtr )malloc(sizeof(QNode);if( !p )exit(1);p-data = ( BTree )malloc( sizeof(BTNode );p-

27、data = e;p-next = NULL;Q.rear-next = p;Q.rear = p;return OK;/*删除元素*/Status DeQueue( LinkQueue &Q, BTree &e )QueuePtr q;if( Q.rear = Q.front )return ERROR;q = Q.front-next ;e = q-data ;Q.front-next = q-next ;if( Q.rear = q )Q.rear = Q.front ;free(q);return OK;/*队列是否为空*/Status QueueEmpty( LinkQueue &Q

28、 )return (Q.rear = Q.front);/*变量：初始化树，自定义指针类型的一维stack作为栈，top为栈顶指针*flag = 1 建立左孩子，flag = 2 建立右孩子*左括号的第一个节点就是左孩子，分号的第一个节点即是右孩子*功能：当遇到左括号时，该节点进栈，建立该节点的左右孩子*当遇到分号时，建立右孩子*当遇到右括号时，该节点的左右孩子建立完毕，出栈。*/void InitBiTree( BTree &b, char *str )BTree stackMAXSIZE, p;int top = -1,k,j = 0;char ch;b = NULL;ch = strj;

29、while( ch != 0 )switch( ch )case (: top+; stacktop = p; k = 1;break;/建立左孩子case ): top-; break;case ,: k = 2; break;/建立右孩子default: p = ( BTree )malloc( sizeof(BTNode) );p-data = ch;p-lchild = p-rchild=NULL;if( b = NULL )/建立根节点b = p;elseswitch( k )case 1: stacktop-lchild = p; break;case 2: stacktop-rc

30、hild = p; break;j+;ch = strj;/*功能：凹进的形式输出二叉树*/void Braverse_l( BTree tree) BTree tmpMAXSIZE, p; int levelMAXSIZE2; int top = -1; int n, i, width = 4;/间隔 char type;/左子树、右子树还是根节点 if( tree != NULL ) top+; tmptop = tree; leveltop0 = width;/间隔 leveltop1 = 2; while (top -1) p = tmptop; n = leveltop0; swit

31、ch (leveltop1) case 0:type = L;/左孩子break;case 1:type = R;/右孩子break;case 2:type = B;/根节点break; /*输出节点及类型*/ for (i = 1; i data, type); printf(n); top-; if (p-rchild != NULL) top+; tmptop = p-rchild; leveltop0 = n + width; leveltop1 = 1; if (p-lchild != NULL) top+; tmptop = p-lchild; leveltop0 = n + wi

32、dth; leveltop1 = 0; /*功能：嵌套打印二叉树*/void Print_tree( BTree tree)if( tree != NULL )coutdata;/输出根节点if( tree-lchild != NULL | tree-rchild != NULL )coutlchild != NULL )Print_tree( tree-lchild );/递归输出所有的左孩子，以左括号为间隔if( tree-rchild != NULL )coutrchild != NULL )/递归输出所有的右孩子，以分号为间隔Print_tree( tree-rchild );cout

33、 );elsecout该树是空树!data = e )return tree;/找到返回该节点elsep = Value( tree-lchild, e );/遍历左子树if( p != NULL )return p;elsereturn Value( tree-rchild, e );/遍历右子树/*功能：采用先序遍历查找值为e的节点，并改变其值*/void Assign( BTree &tree, elemtype e, elemtype value )BTree p = Value( tree, e );/找到该节点if( p )p-data = value;elsecout无要改变的节

34、点!lchild );/*从左子树开始遍历*/rchild_dep = BiTreeDepth( tree-rchild );if( lchild_dep rchild_dep )/*取左右子树中最大深度*/return lchild_dep+1;/每次返回深度加 1elsereturn rchild_dep+1;/*判断树是否为空树*/Status BiTreeEmpty( BTree &tree )if( tree = NULL )return 1;elsereturn 0;/*输出函数visit()*/Status visit( elemtype e )if( e != )coutedata )if( PreO