数据结构课程设计说明书树的应用树和二叉树的转换

1、中北大学数据结构与算法课程设计说 明 书学院、系：软件学院专业：软件工程班级：1314010xxx学生 姓 名：学 号： 1314010xxx设计 题 目：树的应用起迄日期 :2015 年 1 月 12 日- 2015年 1 月 29 日指导教师 :尹四清.2015 年 1 月 29 日一、需求分析1. 设计内容及设计要求a. 设计内容：（ 1）建立一棵树；（ 2）将树转换成二叉树；（ 3）实现二叉树的前序、中序、后序的递归和非递归遍历算法。b. 设计要求：(1) 符合课题要求，实现相应功能；(2) 要求界面友好美观，操作方便易行；(3) 注意程序的实用性、安全性；2. 本演示程序中，元素为单

2、个字符，以空格表示空树 ( 即结点为空 ) ，以回车符作为输入结束标志，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。在真实的运行过程中，由用户手动输入待创建树的含有空格的先根次序序列， 并按回车结束， 程序会将其转化为其对应的二叉树，然后对二叉树进行先序、中序、后序的递归及非递归遍历以及层序遍历，然后显示转化后二叉树的高度和总结点数，以验证所创建的二叉树是否正确，最后，销毁创建的树和二叉树，程序结束。3. 演示程序以用户和计算机对话方式执行，即在计算机终端（屏幕）上显示“提示信息”之后，由用户在键盘上输入演示程序规定的运算命令，相应的输入数据和运算结果显示在其后。4. 为了美观，程序的输出

3、结果采用了分块显示的模式，由虚线及标题隔开，便于用户检查和验证。5. 测试数据如图，给出一棵树，若屏幕上显示如下信息：-请按树的先根次序输入序列，如有空子树，用空格填充，完成后输入回车确认此时，你应当输入：（表示回车确认）abe f c dghi j k提示：为方便确认输入了几个空格，用星号* 表示输入序列中的空格，则序列如下abe*f*c*dghi*j*k*（不是真实的输入序列，供计算需输入空格个数时用）这时，建好的树的先根和后根次序序列如下：.树的先根序列a b e f c d g h i j k树的后根序列e f b c i j k h g d a由树和二叉树的转换关系知，二叉树的先序和

4、中序遍历所得序列分别与树的先根和后根遍历所得序列相同，据此验证转化是否正确。二叉树的先序和中序遍历序列如下：二叉树先序序列a b e f c d g h i j k二叉树中序序列e f b c i j k h g d a二、概要设计为了实现上述程序功能，树采用孩子兄弟表示法，二叉树采用二叉链表表示法。为此，需要两个抽象数据类型，树和二叉树的抽象数据类型。1. 树的抽象数据类型定义adt tree数据对象d： d 是具有相同特性的数据元素的集合。数据关系r：若 d为空集，则称为空树；若 d仅含有一个数据元素，则r为空集，否则r=h ， h是如下二元关系：(1)在 d 中存在唯一的称为根的数据元素

5、root ，它在关系 h 下无前驱；(2)若 d-root ，则存在 d-root 的一个划分 d1,d2,d3, ,dm(m0)，对于任意 j k(1 j,k m)有 dj dk= , 且对任意的 i(1 i m)，唯一存在数据元素xi di 有 h;(3)对应于 d-root的划分， h-, , 有唯一的一个划分h1， h2, , ,hm(m0)，对任意 j k(1 j,k m)有 hj hk=，且对任意 i(1 i m),hi 是 di 上的二元关系， (di,hi)是一棵符合本定义的树，称为根 root 的子树。基本操作p：inittree(&t);操作结果：构造空树t。destroy

6、tree(&t);初始条件：树t 存在。操作结果：销毁树t。createtree(&t,definition);初始条件： definition给出树 t 的定义。.操作结果：按definition构造树 t。cleartree(&t);初始条件：树t 存在。操作结果：将树t 清为空树。treeempty(t);初始条件：树t 存在。操作结果：若t 为空树，则返回true，否则返回false。treedepth(t);初始条件：树t 存在。操作结果：返回的深度。root(t);初始条件：树t 存在。操作结果：返回t 的根。value(t,cur_e);初始条件：树t 存在， cur_e 是 t

7、 中某个结点。操作结果：返回cur_e 的值。assign(t,cur_e,value);初始条件：树t 存在， cur_e 是 t 中某个结点。操作结果：结点cur_e 赋值为 value 。parent(t,cur_e);初始条件：树t 存在， cur_e 是 t 中某个结点。操作结果：若cur_e 是 t 的非根结点，则返回它的双亲，否则函数值为“空”。leftchild(t,cur_e);初始条件：树t 存在， cur_e 是 t 中某个结点。操作结果：若cur_e 是 t 的非叶子结点，则返回它的最左孩子，否则返回“空”。rightsibling(t,cur_e);初始条件：树t 存

8、在， cur_e 是 t 中某个结点。操作结果：若cur_e 有右兄弟，则返回它的右兄弟，否则返回“空”。insertchild(&t,&p,i,c);初始条件：树存在，指向中某个结点，1 i p 指结点的度，非空树与.不相交。操作结果：插入c 为中指结点的第棵子树。deletechild(&t,&p,i);初始条件：树t 存在， p 指向 t 中某个结点， 1 i p 指结点的度。操作结果：删除中所指结点的第棵子树。traversetree(t,visit();初始条件：树t 存在， visit是对结点操作的应用函数。操作结果：按某种次序对t 的每个结点调用函数visit() 一次且至多一次

9、。 一旦 visit()失败，则操作失败。adttree2. 二叉树的抽象数据类型定义adt binarytree数据对象d： d 是具有相同特性的数据元素的集合。数据关系r：若 d=，则 r=，称 binarytree 为空二叉树；若 d，则 r=h ， h 是如下二元关系；（ 1）在 d 中存在惟一的称为根的数据元素root ，它在关系h下无前驱；（ 2）若 d-root，则存在d-root=d1,dr，且 d1dr = ；（ 3）若 d1，则 d1 中存在惟一的元素x1， h，且存在 d1 上的关系h1 ?h；若dr，则dr 中存在惟一的元素xr ， h，且存在上的关系hr ? h；h=

10、,h1,hr；（ 4） (d1,h1)是一棵符合本定义的二叉树，称为根的左子树；(dr,hr)是一棵符合本定义的二叉树，称为根的右子树。基本操作：initbitree( &t )操作结果：构造空二叉树t。destroybitree( &t )初始条件：二叉树t 已存在。操作结果：销毁二叉树t。createbitree( &t, definition ).初始条件： definition给出二叉树t 的定义。操作结果：按definiton构造二叉树t。clearbitree( &t )初始条件：二叉树t 存在。操作结果：将二叉树t 清为空树。bitreeempty( t )初始条件：二叉树t 存

11、在。操作结果：若t 为空二叉树，则返回true，否则返回false。bitreedepth( t )初始条件：二叉树t 存在。操作结果：返回t 的深度。root( t )初始条件：二叉树t 存在。操作结果：返回t 的根。value( t, e )初始条件：二叉树t 存在， e 是 t 中某个结点。操作结果：返回e 的值。assign( t, &e, value )初始条件：二叉树t 存在， e 是 t 中某个结点。操作结果：结点e 赋值为 value 。parent( t, e )初始条件：二叉树t 存在， e 是 t 中某个结点。操作结果：若e 是 t 的非根结点，则返回它的双亲，否则返回“

12、空”。leftchild( t, e )初始条件：二叉树t 存在， e 是 t 中某个结点。操作结果：返回e 的左孩子。若e 无左孩子，则返回“空”。rightchild( t, e )初始条件：二叉树t 存在， e 是 t 中某个结点。操作结果：返回e 的右孩子。若e 无右孩子，则返回“空”。leftsibling( t, e ).初始条件：二叉树t 存在， e 是 t 中某个结点。操作结果：返回e 的左兄弟。若e 是 t 的左孩子或无左兄弟，则返回“空”。rightsibling( t, e )初始条件：二叉树t 存在， e 是 t 中某个结点。操作结果：返回e 的右兄弟。若e 是 t 的

13、右孩子或无右兄弟，则返回“空”。insertchild( t, p, lr, c )初始条件：二叉树t 存在， p 指向 t 中某个结点，lr 为 0 或 1，非空二叉树c 与 t不相交且右子树为空。操作结果：根据lr 为 0 或 1，插入 c 为 t 中 p 所指结点的左或右子树。p 所指结点的原有左或右子树则成为c 的右子树。deletechild( t, p, lr )初始条件：二叉树t 存在， p 指向 t 中某个结点， lr 为 0 或 1。操作结果：根据lr 为 0 或 1，删除 t 中 p 所指结点的左或右子树。preordertraverse( t, visit() )初始条件

14、：二叉树t 存在， visit是对结点操作的应用函数。操作结果：先序遍历t，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。inordertraverse( t, visit() )初始条件：二叉树t 存在， visit是对结点操作的应用函数。操作结果：中序遍历t，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。postordertraverse( t, visit() )初始条件：二叉树t 存在， visit是对结点操作的应用函数。操作结果：后序遍历t，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。l

15、evelordertraverse( t, visit() )初始条件：二叉树t 存在， visit是对结点操作的应用函数。操作结果：层次遍历t，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。adt binarytree.3. 本程序包括个模块【1】主程序模块先声明一棵树和一棵二叉树，然后输入树的含空格先根次序序列，构建一棵树，然后将其转化为二叉树，并对二叉树进行先序、中序、后序的递归和非递归遍历以及层序遍历，然后输出二叉树的高度和总结点数，最后销毁这两棵树。【2】建立树模块按照树的先根序列创建树。【3】树转化二叉树模块将树转化为二叉树。【4】二叉树的遍历二叉树

16、的先序、中序、后序的递归和非递归遍历以及层序遍历。【5】二叉树的相关信息二叉树的高度和总结点数。【6】销毁树和二叉树模块销毁创建的树和转换出的二叉树。【7】栈和队列的模块供二叉树先序、中序、后序的非递归算法调用各模块之间关系：三、详细设计1. 元素类型、结点类型和指针类型.树的结点元素类型设置为字符型，这样既可以接收字符也可以接受数字。typedef char telemtype;/树中结点元素类型/-二叉树的二叉链表存储表示-typedef struct binodetelemtype data; /数据域 , 存储结点名称struct binode *lchild,*rchild;/孩子结

17、点指针binode,*bitree;二叉树的二叉链表表示法示意图：/-树的孩子兄弟表示法-typedef struct csnodetelemtype data; /数据域 , 存储结点名称struct csnode *firstchild, *nextsibling; /孩子指针域和兄弟指针域 csnode, *cstree;树的孩子兄弟表示法示意图：.2. 构造一般树算法：按照树的先根次序序列构建一棵树：对于这棵树，按照需求分析第1 页的测试数据，用户应当输入（表示回车确认）abe f c dghi j k正确输入所需序列后，树的建立完成。status createcstree(cstre

18、e &ct) /按先根序列构造树/ 按先根次序输入树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示树tchar ch;ch=getchar();if(ch= )ct=null;elseif(!(ct=(csnode *)malloc(sizeof(csnode)printf(内存分配失败！n);exit(overflow);/ifct-data=ch;/生成根结点createcstree(ct-firstchild);/构建左子树createcstree(ct-nextsibling);/构建右子树/else.return ok;/createcstree3. 转换为二叉树树和二叉

19、树的转换关键在于树的二叉链表与其对应的二叉树的二叉链表是相同的，只是对同一个二叉链表的解释不同，二叉树的数据域存放结点名称，左指针域指向左孩子，右指针域指向右孩子；树的数据域存放结点名称，左指针域指向孩子结点，右指针域指向与该结点相邻的一个兄弟结点。当两者具有相同的存储结构时， 便可以完成转换，转换过程的实质是按照二叉树的定义将二叉链表解释为二叉树的过程。status exchangetobitree(cstree &ct,bitree &t)/ 将一棵用二叉链表表示的树递归地转换为二叉树if(!ct) /树 ct 为空时，二叉树t 为空t=null;else/ 若树的对应结点不空，申请内存空

20、间if(!(t=(binode *)malloc(sizeof(binode)printf(内存分配失败！n);exit(overflow);/if/ 将树的数据域复制到二叉树对应的数据域t-data=ct-data;/ 若树的孩子域不为空，则用树的孩子域创建二叉树的左子树exchangetobitree(ct-firstchild,t-lchild);/ 若树的兄弟域不为空，则用树的兄弟域创建二叉树的右子树exchangetobitree(ct-nextsibling,t-rchild);/else./exchangetobitree4. 二叉树的遍历二叉树有先序、中序、后序、层序四种遍历方

21、式，而先序、中序、后序遍历又有递归和非递归两种算法，总共有7 个遍历算法。其中，先序、中序、后序非递归遍历算法需要用到栈，层序遍历需要使用队列，队列和栈的相关定义和算法请参考详细设计p21。二叉树先序、中序、后序遍历的区别仅在于访问根结点的时机不同，而层序遍历则是逐层从左到右访问每一个结点。先序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则访问根结点(d) ；先序遍历左子树(l)；先序遍历右子树(r) 。中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树(l)； 访问根结点(d) ；中序遍历右子树(r) 。后序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则后序遍

22、历左子树(l)； 后序遍历右子树(r) ；访问根结点(d) 。虽然访问根结点的时机不同，但是先左后右的规则并没有改变。所有的遍历函数都调用元素访问函数visit，他们的参数列表中均含有一个函数指针变量status(* visit)(telemtype)，通过主函数向他们传递元素访问函数visit的函数名，就可以实现按元素访问函数visit设定格式输出的目的。这样的好处在于当输出格式改变时，只需修改元素访问函数visit的输出格式而无需更改7 个遍历函数，做到一改全改。以下是所有遍历算法的实现以及元素访问函数visit：/-元素访问函数visit-status printelement(tele

23、mtype e) /输出元素e 的值printf( %c ,e); /元素类型设定为字符型return ok;/printelement/-递归算法 -status preordertraverse(bitree t,status(* visit)(telemtype) /先序遍历递归算法./ 采用二叉链表存储结构， visit 是对数据元素操作的应用函数/ 先序遍历二叉树t 的递归算法，对每个数据元素调用函数visitif(t)if(visit(t-data) /访问根结点if(preordertraverse(t-lchild,visit) /访问左子树if(preordertravers

24、e(t-rchild,visit) /访问右子树return ok;return error; /ifelse return ok;/preordertraversestatus inordertraverse(bitree t,status(* visit)(telemtype) /中序遍历递归算法/ 采用二叉链表存储结构， visit 是对数据元素操作的应用函数/ 中序遍历二叉树t 的递归算法，对每个数据元素调用函数visitif(t)if(inordertraverse(t-lchild,visit) /访问左子树if(visit(t-data) /访问根结点if(inordertrav

25、erse(t-rchild,visit) /访问右子树return ok;return error; /ifelse return ok;/inordertraversestatus postordertraverse(bitree t,status(* visit)(telemtype) /后序遍历递归算法/ 采用二叉链表存储结构， visit 是对数据元素操作的应用函数/ 后序遍历二叉树t 的递归算法，对每个数据元素调用函数visitif(t)if(postordertraverse(t-lchild,visit) /访问左子树if(postordertraverse(t-rchild,v

26、isit) /访问右子树if(visit(t-data) /访问根结点.return ok;return error;/ifelse return ok;/postordertraverse/-非递归遍历算法-status preordertraverse1(bitree t,status(* visit)(telemtype) /先序遍历非递归算法/ 采用二叉链表存储结构， visit 是对数据元素操作的应用函数/ 先序遍历二叉树t 的非递归算法，对每个数据元素调用函数visitstack s;initstack(s); /初始化栈bitree p=t;/设置工作指针p 并对其赋初值whil

27、e(p|!(stackempty(s)if(p)if(!visit(p-data)/访问根结点return error;push(s,p);/根指针进栈p=p-lchild;/遍历左子树/ifelsepop(s,p);/根指针退栈p=p-rchild;/遍历右子树/else/whilereturn ok; /preordertraverse1status inordertraverse1(bitree t,status(* visit)(telemtype) /中序遍历非递归算法/ 采用二叉链表存储结构， visit 是对数据元素操作的应用函数/ 中序遍历二叉树t 的非递归算法，对每个数据元素

28、调用函数visitstack s;.initstack(s);bitree p=t;while(p|!(stackempty(s)if(p)push(s,p);/根指针进栈p=p-lchild;/遍历左子树/ifelsepop(s,p);/根指针退栈if(!visit(p-data)/访问根结点return error;p=p-rchild;/遍历右子树/else/whilereturn ok; /inordertraverse1status postordertraverse1(bitree t,status(* visit)(telemtype) /后序遍历非递归算法/ 采用二叉链表存储结

29、构， visit 是对数据元素操作的应用函数/ 后序遍历二叉树t 的非递归算法，对每个数据元素调用函数visitbitree p=t, q=null; / int n=0;stack s;initstack(s);while(p)|(!stackempty(s) while(p)push(s,p);p=p-lchild;/whileq=null;while(!stackempty(s)gettop(s, p);.if(p-rchild=null)|(p-rchild=q)if(!visit(p-data)/访问根结点return error;if(p=t) return error;q=p;p

30、op(s,p);/ifelsep=p-rchild;break;/else/while/whilereturn ok; /postordertraverse1status levelordertraverse1(bitree t,status(* visit)(telemtype) /层序遍历非递归算法/ 采用二叉链表存储结构， visit 是对数据元素操作的应用函数/ 层序遍历二叉树t 的算法，对每个数据元素调用函数visitqueue q;bitree p=t;if(t)/根结点入队列initqueue(q);/初始化队列enqueue(q,t);while(!queueempty(q)/

31、队列不空dequeue(q,p);if(!visit(p-data)/访问根结点return error;if(p-lchild)enqueue(q,p-lchild);/左孩子入队列if(p-rchild).enqueue(q,p-rchild);/右孩子入队列/whileprintf(n);/ifreturn ok; /levelordertraverse15. 二叉树的信息int bitreedepth(bitree t) /递归求二叉树高度/ 若二叉树t 存在，返回t 的深度（高度），否则返回0int thigh,leftthigh,rightthigh; /分别表示二叉树高度，左子树

32、高度，右子树高度if(!t) return 0; /树高为 0elseleftthigh=bitreedepth(t-lchild);/求左子树高度rightthigh=bitreedepth(t-rchild);/求右子树高度if(leftthigh=rightthigh)/求二叉树高度thigh=leftthigh+1;elsethigh=rightthigh+1;/elsereturn thigh;/bitreedepthint nodesubnum(bitree t) /统计二叉树的结点个数if(!t) return 0; /二叉树为空树，没有结点else return(nodesub

33、num(t-lchild)+nodesubnum(t-rchild)+1); /nodesubnum6. 销毁树void destorycstree(cstree &ct)/ 按照树的定义递归地销毁树if(ct) /非空树if(ct-firstchild)/孩子子树非空.destorycstree(ct-firstchild);if(ct-nextsibling) /兄弟子树非空destorycstree(ct-nextsibling);free(ct); /释放根结点ct=null;/空指针赋0/if/destorytreevoid destorybitree(bitree &t)/ 按照二

34、叉树定义递归地销毁二叉树if(t) /非空树if(t-lchild) /左子树非空 , 销毁左子树destorybitree(t-lchild);if(t-rchild) /右子树非空 , 销毁右子树destorybitree(t-rchild);free(t); /释放根结点t=null;/空指针赋0/if/destorytreevoid destorytree(cstree &ct,bitree &t)/ 销毁树和二叉树destorycstree(ct);destorybitree(t);printf(-生成的树和二叉树已被销毁！);/destorytree7. 栈和队列的定义及算法/-栈

35、的顺序存储表示-typedef bitree selemtype;/栈的元素为二叉树指针类型typedef struct /栈的顺序存储表示selemtype *base;/栈底指针，在栈构造之前和销毁之后，base 的值为 nullselemtype *top;/栈顶指针.int stacksize;/当前已分配的存储空间，以元素为单位stack;/-队列的链式存储表示-typedef bitree qelemtype;/队列元素为二叉树指针类型typedef struct qnode /链队列的c 语言表示qelemtype data;/数据域struct qnode * next;/指针

36、域qnode,* queueptr;typedef structqueueptr front; /队头指针queueptr rear;/队尾指针queue;/-栈的相关函数 ( 供非递归后序遍历使用)-status initstack(stack &s)/构造一个空的顺序栈if(!(s.base=(selemtype *)malloc(stack_init_size*sizeof(selemtype)printf(内存分配失败！n);exit(overflow);s.top=s.base;s.stacksize=stack_init_size;return ok;/initstackstatu

37、s destorystack(stack &s)/释放顺序栈s 所占内存空间free(s.base);s.base=null;s.top=null;return ok;/destorystackstatus stackempty(stack s)/判断顺序栈s 是否为空栈 , 是返回 1，否返回0.return s.top=s.base;/stackisemptystatus push(stack &s,selemtype e) /入栈if(s.top-s.base = s.stacksize)if(!(s.base=(selemtype*)realloc(s.base,(stack_init

38、_size+stackincrement)*sizeof(selemtype)printf(内存分配失败！n);exit(overflow);s.top = s.base + s.stacksize;s.stacksize +=stackincrement;*s.top+=e;/pushstatus pop(stack &s,selemtype &e) /出栈if(stackempty(s)return error;e=*-s.top;return ok;/popstatus gettop(stack s,selemtype &e)/ 若栈不空，用 e 返回顺序栈 s 栈顶元素的值，并返回 o

39、k，否则返回 errror if(stackempty(s)return error;e = *(s.top-1);return ok;/gettop/-队列的相关函数( 供非递归层序遍历使用)-queueptr mallocqnode()/为链队列结点申请内存的函数queueptr p; /工作指针p.if(!(p=(queueptr)malloc(sizeof(qnode) /申请结点的内存空间， 若失败则提示并退出程序printf(内存分配失败，程序即将退出！n);exit(overflow);return p; /mallocqnodestatus initqueue(queue &q

40、) /初始化链队列 / 构建一个空队列 qq.front=q.rear=mallocqnode();/申请头结点的内存空间，并使队头和队尾指针同时指向它q.front-next=null;q.front-data=0;/将队长设为0return ok;/initqueuestatus destoryqueue(queue &q)/销毁队列qwhile(q.front) / 从头结点开始向后逐个释放结点内存空间 q.rear=q.front-next;free(q.front);q.front=q.rear;/whileprintf(链队列已成功销毁！n);return ok;/destoryq

41、ueuestatus queueempty(queue q)/若 q为空队列，则返回ok;否则返回errorif(q.rear=q.front) /队列为空的标志return ok;return error;/queueemptystatus enqueue(queue &q,qelemtype e)./ 插入元素 e 为 q的新的队尾元素queueptr p=mallocqnode();p-data=e;p-next=null;q.rear-next=p;q.rear=p;q.front-data+; /队长 +1return ok;/enqueuestatus dequeue(queue

42、&q,qelemtype &e) / 若队列不空 , 则删除 q的队头元素 , 用 e 返回其值 , 并返回 ok,否则返回 error if(queueempty(q)return error; queueptr p= q.front-next;e = p-data;q.front-next = p-next;if(q.rear=p)q.rear=q.front;free(p);q.front-data-; /队长 -1return ok;/dequeue8. 主函数int main(int argc,char *argv)printf(-树的应用-n);bitree t=null;/声明一棵二叉树cstree ct=null;/声明一棵普通树printf(-树的建立-n);printf(-请按树