一．需求分析树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观来看，树是以分支关系定义的内部结构。树的结构在客观世界广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得广泛应用，如在编译程序中，可用树来表示源程序的语法结构，又如在数据库系统中，树形结构也是信息的重要组织形式之一。二．实验目的对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。三．实验环境 1、硬件：PC机 2、软件：Microsoft Visual C++ 6.0 四．设计说明本程序采用树的二叉链表（孩子指针-兄弟指针-双亲指针）存储表示，以下是树的结构定义和基本操作： ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3, …,Dm(m>0)，对于任意j≠k(1≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有∈H; (3) 对应于D-{root}的划分，H-{,…,}有唯一的一个划分H1，H2,…,Hm(m>0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL，且对任意i(1≤i≤m),Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。基本操作P： InitTree(&T); 操作结果：构造空树T。 DestroyTree(&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中某个结点。操作结果：返回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存在，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()一次且至多一次。一旦visit()失败，则操作失败。 CSTree Search(CSTree T,TElemType cur_e); 初始条件：树T存在，cur_e可能是树T中某一个结点的值。操作结果：在树T中查找值为cur_e的结点，找到返回指向这个结点的指针，否则返回空指针。这个函数的作用是为了几个基本操作而服务的。 void LevelOrderTraverseTree(CSTree T,void (* visit)(TElemType)); 初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按层次次序对T的每一个结点调用函数visit()一次且至多一次。 void PreOrderTraverseTree(CSTree T,void(*visit)(TElemType)); 初始条件：树T存在，visit是对结点操作的应用函数。操作函数：按先序次序（先根遍历）对T的每一个结点调用函数visit()一次且至多一次。函数的功能实现是递归实现的。 void PostOrderTraverseTree(CSTree 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 (*visit)(CSTree)); 附加函数：用于显示树的所有内容。初始条件：树T存在；操作结果：将树T的所有结点显示出来。 }ADT Tree 五．数据处理树型数据存储样本：转化后树的二叉链表存储：以下为数据样本测试：  操作：判断树书否为空？结果：不为空 返回树T的深度？结果： 4 返回树T的根结点？结果： A 返回树F结点的值？结果： F 将树根节点重新赋值为W ? 结果：A<—>W 求出结点A的双亲? 结果： W 求出结点A的第一个孩子结点? 结果： D 求出G的第一个兄弟结点? 结果： H 插入子树C至A中第2科子树？结果： 删除树结点为R的第三颗子树？结果： 多种遍历方式遍历树前序遍历树： W-A-D-X-Y-Z-E-B 层次序遍历树： W-A-B-D-X-E-Y-Z 后序遍历树： D-Y-Z-X-E-A-B-W 以下为运行EXE程序测试过程：选择1：选择14: 选择15：选择16：选择4：选择5：选择6：选择7：选择8：选择9：选择10：选择11：选择12：选择13：选择14：选择15：选择16：选择2：六．程序清单解读 /**************************抽象数据类型树-源码*********************************/ #include #include using namespace std; const int TRUE=1; const int FALSE=0; const int OK=1; const int ERROR=0; const int OVERFLOW=1; const int MAX=30; const char NIL=' '; /*****************树的二叉链表孩子-兄弟-双亲存储表示***************************/ 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,rear; /*队头、队尾指针*/ }LinkQueue; /*******************************队列定义**************************************/ /*构造一个空队列*/ int InitQueue (LinkQueue &Q) { if(!(Q.front=Q.rear=new QNode)) exit(OVERFLOW); Q.front->next=NULL; return OK; } /*销毁队列Q*/ int 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.front; p=Q.front->next; Q.front->next=NULL; while(p){ q=p; p=p->next; delete q; } return OK; } /*若队列Q为空队列则返回TRUE，否则返回FALSE*/ int 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)) exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; } /*若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/ int 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; } /*****************************************************************************/ /***********************树的二叉链表孩子-兄弟-双亲存储定义*********************/ /*操作结果: 构造空树T*/ int InitTree(CSTree &T) { T=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 c[MAX]; CSTree p,p1,temp; LinkQueue q; InitQueue(q); cout<<"请输入根节点，空格代表跟为空:"; fflush(stdin); c[0]=getche(); if(c[0]!=NIL) /*非空树*/ { T=new CSNode; T->data=c[0]; T->nextsibling=NULL; T->parent=NULL; EnQueue(q,T); while(!QueueEmpty(q)) { DeQueue(q,p); cout<<"\n请输入"<data<<"所有孩子的节点: "; gets(c); if(strlen(c)) /*树有孩子*/ { p1=p->firstchild=new CSNode; /*建立长子节点*/ temp=p; /*保存该根节点*/ p1->parent=temp; /*建立双亲域*/ p1->data=c[0]; EnQueue(q,p1); /*第一个孩子节点入队列*/ for(int i=1;inextsibling=new CSNode; /*建立下一个兄弟节点*/ p1->nextsibling->data=c[i]; /* 下一个兄弟节点赋值*/ p1->nextsibling->parent=temp; /*建立下一个兄弟节点双亲域*/ EnQueue(q,p1->nextsibling); /*各兄弟入队*/ p1=p1->nextsibling; } p1->nextsibling=NULL; /*最后的兄弟结点的nextsibling指针置为空*/ } else /*树无孩子只有根节点*/ { p->firstchild=NULL; } } } else T=NULL; /*空树*/ 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存在*/ /*操作条件：返回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(depth>max) max=depth; } return max+1; /*返回深度要加上根节点*/ } /*初始条件: 树T存在*/ /*操作结果: 返回T的根*/ char Root(CSTree T) { if(T) return T->data; else { cout<<"\n树空，无根节点!"; 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->nextsibling) 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; else { cout<<"\n在树中找不到值为"<parent) { cout<<"\n值为"<parent->data; } else { cout<<"\n树空，无节点"; return NIL; } } /*初始条件: 树T存在,cur_e是树T中结点的值*/ /*操作结果: 改cur_e为value*/ int Assign(CSTree &T,char cur_e,char value) { CSTree p; if(T) { p=Search(T,cur_e); if(p) { cout<<"\n找到节点"<data=value; return OK; } else { cout<<"\n找不到节点"<firstchild) { cout<<"\n无左孩子"; return NIL; } else { return p->firstchild->data; } } } else { cout<<"\n树空，不存在值为"<nextsibling) { cout<<"\n无兄弟"; return NIL; } else { return p->nextsibling->data; } } } else { cout<<"\n树空，不存在值为"<firstchild&&i>1) { cout<<"\n输入数据矛盾，请检查"; return ERROR; } if(T) /*T不空*/ { if(i==1) /*插到第一个孩子上*/ { c->nextsibling=p->firstchild; p->firstchild=c; c->parent=p; } else { p=p->firstchild; j=2; while(p&&jnextsibling; j++; } if(j==i) /*找到插入位置*/ { c->nextsibling=p->nextsibling; p->nextsibling=c; c->parent=temp; /*设置双亲节点*/ } else /*找不到插入位置*/ { cout<<"\n插入节点错误"; return ERROR; } } return OK; } else /*树空*/ { cout<<"\n树空，操作不执行"; return ERROR; } } /*初始条件：树T存在，p指向T中的某个结点，1<=i<=p所指结点的度*/ /*操作结果：删除T中p所指结点的第i棵子树*/ int DeleteChild(CSTree &T,CSTree p,int i) { CSTree q; int j; if(!T) { cout<<"\n树为空，不执行操作"; return OK; } if(i<1) { cout<<"\n插入地址选择出错，不执行操作"; return ERROR; } if(!p) { cout<<"\n在树中找不到指向节点，不执行操作"; return ERROR; } if(!p->firstchild&&i>1) { cout<<"\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->nextsibling; p->nextsibling=q->nextsibling; q->nextsibling=NULL; DestroyTree(q); } else /* 找不到该子树*/ { cout<<"\n删除节点错误，不执行操作"; return ERROR; } } return OK; } else /*树空*/ { cout<<"\n树空，删除错误，不执行操作"; return ERROR; } } /*访问对结点操作的应用函数*/ void visit(char value) { cout<data); PreOrderTraverseTree(T->firstchild,visit) ; PreOrderTraverseTree(T->nextsibling,visit) ; } } /*初始条件：树T存在，visit是对结点操作的应用函数*/ /*操作结果：按后根遍历对T的每一个结点调用函数visit()一次且至多一次*/ void PostOrderTraverseTree(CSTree T,void (*visit)(char)) { CSTree 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()一次且至多一次*/ 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 /*树空*/ { cout<<"\n树空，层次遍历失败!"; } } /********************************************************************/ /******************************界面函数******************************/ int menu() { int choose; do { system("cls");/*清屏*/ cout<<"\t *******************************************"<>choose; system("cls"); /*运行前清屏*/ } while(choose<1||choose>17); return choose; } /****************************主函数*******************************/ int main() { int i; CSTree T=NULL,T1,p; char e,e1; for(;;) { switch(menu()) { case 1: /*创建新树*/ if(!T)ClearTree(T); cout<<"创建新树，请按提示输入"<>e1; e=Value(T,e1); if(e!=NIL) cout<<"在树中找到节点值为:"<>e1; cout<<"请输入你要改变的节点的新值:"; cin>>e; if(Assign(T,e1,e)) cout<<"赋值成功"<>e1; e=Parent(T,e1); if(e!=NIL)cout<>e1; e=LeftChild(T,e1); if(e!=NIL)cout<>e1; e=RightSibling(T,e1); if(e!=NIL)cout<>e1; cout<<"\n请输入要插入的节点的第几棵子树:"; cin>>i; p=Search(T,e1); if(InsertChild(T,p,i,T1))cout<<"\n插入成功!"; system("pause"); break; case 13: /*删除一棵树*/ cout<<"\n请输入要删除树的节点:"; cin>>e1; cout<<"\n请输入要删除树节点的第几棵子树:"; cin>>i; p=Search(T,e1); if(DeleteChild(T,p,i)) cout<<"\n删除成功!"; system("pause"); break; case 14: /*先序遍历树*/ if(T) { cout<<"\n树的先序遍历为："; PreOrderTraverseTree(T,visit); } else cout<<"\n树为空，先序遍历失败! "; system("pause"); break; case 15: /*后序遍历树*/ if(T) { cout<<"\n树的后序遍历为："; PostOrderTraverseTree(T,visit); } else cout<<"\n树为空，后序遍历失败! "; system("pause"); break; case 16: /*层次遍历树*/ if(T) { cout<<"\n树的层次遍历为："; LevelOrderTraverseTree(T,visit); } system("pause"); break; case 17: /*退出*/ system("pause"); exit(0); } } return 0; } /************************************结束*************************************/ 七．实验总结本次综合性实验我选择了实现一个较为完整的抽象数据-树结构的基本操作的和数据测试的题目，虽然课本有二叉树的部分类似定义，但对于实现一个基本完整的树存储结构的定义和操作还是相当繁琐，幸亏在自己努力和同学的指点下经历了设计-编码-调试...等阶段的重复，尽管最终程序依旧存在不少BUG，但基本实现了程序的预期功能。通过了这次实验，我基本我掌握了队列的和树的数据结构的设计和实现，初步认识到如何把所学的数据结构与现实编程结合起来，如何设计出更优异算法的程序，更重要的是学会了如何安排和调试一个比较大型的综合程序，总的来说受益匪浅：首先，设计一个数据结构必须清楚明确数据对象、数据关系和基本操作的关系，做好了这一步还得把数据结构与主程序之间函数调用的关系和用途进一步明确，否则程序会逻辑混乱。其次，完成一个程序，语法细节固然重要，但是每一部的算法设计亦需要明确，对此，每写一个函数都必须认真清楚地考虑每一个细节，是否在某种情况会出现BUG？最有每一个函数都确保正确清醒，整体程序才能正常运行。再次，更重要的是编制一个较大型的程序让我体会到什么叫“编写程序用了3天，调试程序却用了一个星期！“编程是算法和整体的设计情况，编程起初如果能形成一种系统的观念，则在程序的实现中将能做到胸有成竹，从而能轻松的完成程序的实现。调试，最重要的是过程。在调试过程中，只有对程序中的细节和出错的处理进行细细的推敲和考虑，才能完善程序的整体功能。整体上编程，细节上调试，这样才能更好的完成一个程序。

“数据结构实验”实验报告