数据结构-树的实现实验报告

1、 数据结构设计性实验报告 题目：抽象数据类型-树学 院 计算机学院 专 业 网络工程 年级班别 2013级4班 学 号 学生姓名 指导教师 成 绩 2015年 6 月 6 日 抽象数据类型：树的实现1题目采用树的二叉链表（孩子指针-兄弟指针-双亲指针）存储表示，实现抽象数据类型树。ADT Tree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R=H，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2) 若D-rootNULL，则存在D-root的一个划分D1,D2,D3

2、, ,Dm(m0)，对于任意jk(1j,km)有DjDk=NULL,且对任意的i(1im)，唯一存在数据元素xiDi有 H;(3) 对应于D-root的划分，H-,有唯一的一个划分H1，H2,Hm(m0)，对任意jk(1j,km)有HjHk=NULL，且对任意i(1im),Hi是Di上的二元关系，(Di,Hi)是一棵符合本定义的树，称为根root的子树。 基本操作P：InitTree(&T);操作结果：构造空树T。DestroyTree(&T);初始条件：树T存在。操作结果：销毁树T。CreateTree(&T,definition);初始条件：definition给出树T的定义。操作结果：按

3、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中某个结点。操作结果：返回cur_e的值。Assign(T,cur_e,value);初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值为value。Parent(T,cur_e

4、);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。LeftChild(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。RightSibling(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回“空”。InsertChild(&T,&p,I,c);初始条件：树存在，指向中某个结点，1ip指结点的度，非空树与不相交。操作结果：插入c为中指结点的第棵子树。Dele

5、teChild(&T,&p,i);初始条件：树T存在，p指向T中某个结点，1ip指结点的度。操作结果：删除中所指结点的第棵子树。TraverseTree(T,visit();初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。CSTree Search(CSTree T,TElemType cur_e);初始条件：树T存在，cur_e可能是树T中某一个结点的值。操作结果：在树T中查找值为cur_e的结点，找到返回指向这个结点的指针，否则返回空指针。这个函数的作用是为了几个基本操作而服务

6、的。void LevelOrderTraverseTree(CSTree T,void (* visit)(TElemType);初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按层次次序对T的每一个结点调用函数visit()一次且至多一次。void PreOrderTraverseTree(CSTree T,void(*visit)(TElemType);初始条件：树T存在，visit是对结点操作的应用函数。操作函数：按先序次序（先根遍历）对T的每一个结点调用函数visit()一次且至多一次。函数的功能实现是递归实现的。void PostOrderTraverseTree(C

7、STree T,void (*visit)(TElemType);初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按后根遍历对T的每一个结点调用函数visit()一次且至多一次。函数的功能实现是递归实现的。void visit_print(CSTree p);初始条件：树T存在，visit_print是对结点操作的应用函数。操作函数：对T的每一个结点调用函数visit_print()一次且至多一次。与visit函数不一样的是，visit函数只是输出一个结点的值，而visit_print还输出其结点，第一个孩子，其右兄弟和双亲的值void Print(CSTree T,void

8、(*visit)(CSTree);附加函数：用于显示树的所有内容。初始条件：树T存在；操作结果：将树T的所有结点显示出来。ADT Tree2存储结构定义树的二叉链表孩子-兄弟-双亲存储表示typedef struct CSnode char data; CSnode *firstchild,*nextsibling,*parent; CSNode,*CSTree;树的辅助队列结构定义和操作typedef struct QNode CSTree data; QNode *next;QNode,*QueuePtr; typedef struct LinkQueue QueuePtr front,r

9、ear; LinkQueue;构造一个空队列int InitQueue (LinkQueue &Q) if(!(Q.front=Q.rear=new QNode) return ERROR; Q.front-next=NULL; return OK;销毁队列Qint DestroyQueue(LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; delete Q.front; Q.front=Q.rear; return OK;将Q清为空队列int ClearQueue (LinkQueue &Q) QueuePtr p,q; Q.rear=Q.f

10、ront; p=Q.front-next; Q.front-next=NULL; while(p) q=p; p=p-next; delete q; return OK;若队列Q为空队列则返回TRUE，否则返回FALSEint QueueEmpty( LinkQueue Q) if(Q.front=Q.rear) return TRUE; else return FALSE;插入元素e为Q的新的队尾元素 int EnQueue(LinkQueue &Q, CSTree e) QueuePtr p; if(!(p=new QNode) return ERROR; p-data=e; p-next

11、=NULL; Q.rear-next=p; Q.rear=p; return OK;若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERRORint DeQueue(LinkQueue &Q,CSTree &e) QueuePtr p; if(Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; delete p; return OK;3算法设计/*操作结果: 构造空树T*/int InitTree(CSTree &T)T

12、=NULL;return OK;/*初始条件: 树T存在*/*操作结果: 销毁树T*/void DestroyTree(CSTree &T) if(T) if(T-firstchild) DestroyTree(T-firstchild); if(T-nextsibling) DestroyTree(T-nextsibling); delete T;/*初始条件：树T存在*/*操作结果：按层次次序创建树T*/int CreateTree(CSTree &T)char cMAX;CSTree p,p1,temp; LinkQueue q;InitQueue(q); printf(请输入根节点，空

13、格代表根为空:); fflush(stdin);c0=getche(); if(c0!=NIL) /非空树T=new CSNode; T-data=c0;T-nextsibling=NULL;T-parent=NULL;EnQueue(q,T);while(!QueueEmpty(q)DeQueue(q,p);printf(n请输入节点%c所有孩子的节点: ,p-data);gets(c); if(strlen(c) /树有孩子p1=p-firstchild=new CSNode; /建立长子节点temp=p; /保存该根节点 p1-parent=temp; /建立双亲域/p1-data=c0

14、; EnQueue(q,p1); /第一个孩子节点入队列for(int i=1;inextsibling=new CSNode; /建立下一个兄弟节点 p1-nextsibling-data=ci; /下一个兄弟节点赋值 p1-nextsibling-parent=temp; /建立下一个兄弟节点双亲域 EnQueue(q,p1-nextsibling); /各兄弟入队 p1=p1-nextsibling;p1-nextsibling=NULL; /最后的兄弟结点的nextsibling指针置为空 else /树无孩子只有根节点p-firstchild=NULL;else T=NULL; /树

15、空return OK;/*初始条件：树T存在*/*操作结果：将树T清为空树*/void ClearTree(CSTree &T) if(T) if(T-firstchild) DestroyTree(T-firstchild); if(T-nextsibling) DestroyTree(T-nextsibling); delete T; T=NULL;/*初始条件：树T存在*/*操作结果：若T为空树，则返回TRUE，否则返回FALSE*/int TreeEmpty(CSTree T)if(T=NULL) return TRUE;else return FALSE;/*初始条件：树T存在*/*

16、操作条件：返回T的深度*/int TreeDepth(CSTree T)CSTree p;int depth,max=0;if(!T)return 0;if(!T-firstchild)return 1;for(p=T-firstchild;p;p=p-nextsibling)depth=TreeDepth(p); /递归求深度if(depthmax) max=depth;return max+1; /返回深度要加上根节点/*初始条件: 树T存在*/*操作结果: 返回T的根*/char Root(CSTree T)if(T) return T-data;else printf(n树空，无根节点

17、!);return NIL;/*初始条件：树T存在，cur_e可能是树T中某一个结点的值。*/*操作结果：在树T中查找值为cur_e的结点，找到返回指向这个结点的指针，否则返回空指针。*/CSTree Search(CSTree T,char cur_e)LinkQueue q; CSTree a;if(T)InitQueue(q); /队列初始化EnQueue(q,T);while(!QueueEmpty(q)DeQueue(q,a);if(a-data=cur_e) return a;if(a-firstchild) EnQueue(q,a-firstchild); if(a-nextsi

18、bling) EnQueue(q,a-nextsibling); return NULL;/*初始条件：树T存在，cur_e可能是树T中某个结点*/*操作结果：返回cur_e的值*/char Value(CSTree T, char cur_e)CSTree p;if(T)p=Search(T,cur_e); if(p) return p-data;elseprintf(n在树中找不到值为%c的节点,cur_e);return NIL;elseprintf(n树空，无值为%c的节点,cur_e); return NIL;/*初始条件：树T存在，cur_e可能是T中的某个结点*/*操作结果：若c

19、ur_e是T的非根结点，则返回它的双亲，否则函数值为空*/char Parent(CSTree T,char cur_e)CSTree p;if(T)p=Search(T,cur_e); if(!p)printf(n在树中找不到值为%c的节点,cur_e); return NIL;else if(!p-parent) printf(n值为%c的节点是根节点，无双亲节点,cur_e); return NIL;else return p-parent-data; else printf(n树空，无节点);return NIL;/*初始条件: 树T存在,cur_e是树T中结点的值*/*操作结果: 改

20、cur_e为value*/int Assign(CSTree &T,char cur_e,char value) CSTree p; if(T) p=Search(T,cur_e); if(p) printf(n找到这个节点%c,赋新值为%c,cur_e,value); p-data=value; return OK; else printf(n找不到节点%c,操作无法完成,cur_e); return ERROR; else printf(n树为空，操作无法完成); return ERROR; /*初始条件：树T存在，cur_e可能是T中某个结点*/*操作结果：若cur_e是T的非叶子结点，

21、则返回它的最左孩子，否则返回函数值为空。*/char LeftChild(CSTree T,char cur_e)CSTree p;if(T)p=Search(T,cur_e);if(!p)printf(n找不到值为%c的节点,cur_e);return NIL;elseif(!p-firstchild)printf(n无左孩子);return NIL;elsereturn p-firstchild-data;elseprintf(n树空，不存在值为%c的节点,cur_e);return NULL;/*初始条件：树T存在，cur_e可能是T中的某个结点*/*操作结果：若cur_e有右兄弟，则返

22、回它的右兄弟，否则返回函数值为空*/char RightSibling(CSTree T,char cur_e)CSTree p;if(T)p=Search(T,cur_e);if(!p)printf(n找不到值为%c的节点,cur_e);return NIL;elseif(!p-nextsibling)printf(n无左孩子);return NIL;elsereturn p-nextsibling-data;elseprintf(n树空，不存在值为%c的节点,cur_e);return NIL;/*初始条件：树T存在，p指向T中某个结点，1=i=p所指结点的度+1，非空树c与T不相交*/*

23、操作结果：插入c为T中p指结点的第i棵子树*/int InsertChild(CSTree &T,CSTree p,int i,CSTree c)CSTree temp=p; /*保存根节点*/int j; if(!c)printf(n子树为空，不执行操作);return OK;if(ifirstchild&i1)printf(n输入数据矛盾，请检查);return ERROR;if(T) /T不空if(i=1) /插到第一个孩子上c-nextsibling=p-firstchild;p-firstchild=c;c-parent=p; elsep=p-firstchild;j=2;while

24、(p&jnextsibling;j+; if(j=i) /找到插入位置 c-nextsibling=p-nextsibling;p-nextsibling=c;c-parent=temp; /设置双亲节点else /找不到插入位置*/ printf(n插入节点错误); return ERROR; return OK;else /树空printf(n树空，操作不执行);return ERROR;/*初始条件：树T存在，p指向T中的某个结点，1=i=p所指结点的度*/*操作结果：删除T中p所指结点的第i棵子树*/int DeleteChild(CSTree &T,CSTree p,int i)CS

25、Tree q; int j; if(!T)printf(n树为空，不执行操作);return OK;if(ifirstchild&i1)printf(n输入数据矛盾，请检查);return ERROR;if(T) /T不空if(i=1) /删除长子q=p-firstchild;p-firstchild=q-nextsibling; /原次子现为长子 q-nextsibling=NULL;DestroyTree(q); /销毁以q为根的子树*/ else /删除非长子p=p-firstchild;j=2; while(p&jnextsibling;j+;if(j=i) /找到第i棵子数q=p-n

26、extsibling; p-nextsibling=q-nextsibling;q-nextsibling=NULL; DestroyTree(q); else / 找不到该子树printf(n删除节点错误，不执行操作);return ERROR;return OK;else /树空printf(n树空，删除错误，不执行操作);return ERROR;/*访问对结点操作的应用函数*/void visit(char value)printf(%c,value);/*初始条件：树T存在，visit是对结点操作的应用函数*/*操作函数：按先序次序（先根遍历）对T的每一个结点调用函数visit()一

27、次且至多一次*/void PreOrderTraverseTree(CSTree T,void(*visit)(char)if(T) /树不空visit(T-data); PreOrderTraverseTree(T-firstchild,visit) ; PreOrderTraverseTree(T-nextsibling,visit) ;/*初始条件：树T存在，visit是对结点操作的应用函数*/*操作结果：按后根遍历对T的每一个结点调用函数visit()一次且至多一次*/void PostOrderTraverseTree(CSTree T,void (*visit)(char)CSTr

28、ee p; if(T) /树不空if(T-firstchild) PostOrderTraverseTree(T-firstchild,visit); /后根遍历长子子树 p=T-firstchild-nextsibling; /p指向长子下一个兄弟 while(p) PostOrderTraverseTree(p,visit); /后根遍历下一个兄弟子树 p=p-nextsibling; /p指向下一个兄弟*/ visit(T-data); /最后访问根节点*/ /*初始条件：树T存在，visit是对结点操作的应用函数。*/*操作结果：按层次次序对T的每一个结点调用函数visit()一次且至

29、多一次*/void LevelOrderTraverseTree(CSTree T,void (* visit)(char)LinkQueue Q;CSTree p,q;if(T) /树不空InitQueue(Q);EnQueue(Q,T);while(!QueueEmpty(Q) /队列不空DeQueue(Q,q);visit(q-data); /访问节点if(q-firstchild) p=q-firstchild; EnQueue(Q,p); /第一个孩入队列while(p-nextsibling)p=p-nextsibling; EnQueue(Q,p); /兄弟节点入队列else /

30、树空printf(n树空，层次遍历失败!);4测试/界面函数 int menu() int choose; do system(CLS);/清屏 printf( *); printf(n *抽象数据类型: 树的孩子-兄弟-双亲存储表*); printf(n *); printf( ); printf(n 1. 创建一棵树); printf(n 2. 销毁树); printf(n 3. 将树清为空树); printf(n 4. 判断树是否为空); printf(n 5. 返回树的深度); printf(n 6. 返回树的根节点); printf(n 7. 返回树中某个节点值); printf(n

31、 8. 将树中某个节点重新赋值); printf(n 9. 求树中某节点双亲); printf(n 10. 求树中某节点最左孩子); printf(n 11. 求树中某节点右兄弟); printf(n 12. 插入一棵树); printf(n 13. 删除一棵树); printf(n 14. 先序遍历树); printf(n 15. 后序遍历树); printf(n 16. 层次遍历树); printf(n 17. 退出); printf(n *); printf(n 请输入您的选择(1-17): ); scanf(%d, &choose); system(cls); /运行前清屏 while

32、(choose17); return choose; /主函数 int main() int i; CSTree T = NULL,T1,p; char e,t; for( ; ; ) switch(menu() case 1: /创建新树 if(!T) ClearTree(T); printf(创建新树，请按提示输入); CreateTree(T); printf(树创建成功!); system(pause); break; case 2: /销毁树 DestroyTree(T); printf(树已被销毁!); system(pause); break; case 3: /将树清为空树 C

33、learTree(T); printf(树已被清空!); system(pause); break; case 4: /判断树是否为空 if(TreeEmpty(T) printf(树为空!); else printf(树不为空!); system(pause); break; case 5: /返回树的深度 printf(树的深度为:%d, TreeDepth(T); system(pause); break; case 6: /返回树的根节点 e = Root(T); if(e != NIL) printf(树的根节点为:%s, e); system(pause); break; case

34、 7: /返回树中某个节点值 printf(请输入你要得到结点的值:); t = getchar(); e = Value(T,t); if(e != NULL) printf(在树中找到节点值为:%s,e); system(pause); break; case 8: /将树中某个节点重新赋值 printf(请输入你要赋值的节点的原值:); scanf(%s, &t); printf(请输入你要改变的节点的新值:); scanf(%s, &e); if(Assign(T, t, e) printf(赋值成功); else printf(赋值失败); system(pause); break;

35、 case 9: /求树中某节点双亲 printf(请输入你要查找双亲节点的值:); scanf(%s, &t); e = Parent(T, t); if(e != NIL) printf(这个节点双亲查找为:%s, e); system(pause); break; case 10: /求树中某节点最左孩子 printf(请输入你要查找左孩子节点的值:); scanf(%s, &t); e = LeftChild(T,t); if(e != NIL) printf(节点左孩子查找为:%s, e); system(pause); break; case 11: /求树中某节点右兄弟 printf(请输入你要查找右兄弟节点的值:); scanf(%s, &t); e = RightSibling(T, t); if(e != NIL) printf(节点右兄弟查找为:%c, e); system(pause); break; case 12: /插入一棵树 printf(请按下面提示创建一棵子树用以插入!); InitTree(T1); CreateTree(T1); printf(子树创建成功，请输入要插入的节点:); scanf(%s, &t); printf(n请输入要插入的节点的第几棵子树:); scanf(%d,&i); p = Se