文档介绍:实现二叉树的各种遍历算法实验报告一实验题目:实现二叉树的各种遍历算法二实验要求::<1):<1)实现二叉树的先序遍历实现二叉树的中序遍历实现二叉树的后序遍历三实验内容::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有<root,xi>∈H。 b5E2RGbCAP(3> 对应于D-{root}的划分,H-{<root,xi>,„,<root,xm>}有唯一的一个划分H1,H2,„,Hm(m>0>,对任意j≠k(1≤j,k≤m>有Hj∩Hk=NULL,且对任意i(1≤i≤m>,Hi是Di上的二元关系,(Di,{Hi}>是一棵符合本定义的树,称为根root的子树。p1EanqFDPw基本操作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存在。 操作结果:返回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>。 初始条件:树T存在,p指向T中某个结点,1≤i≤p指结点的度+1,非空树c与T不相交。 操作结果:插入c为T中p指结点的第i棵子树。DeleteChild(&T,&p,i>。 初始条件:树T存在,p指向T中某个结点,1≤i≤p指结点的度。 操作结果:删除T中p所指结点的第i棵子树。 TraverseTree(T,visit(>>。 初始条件:树T存在,visit是对结点操作的应用函数。 操作结果:按某种次序对T的每个结点调用函数visit(>一次且至多一次。一旦visit(>失败,则操作失败。 DXDiTa9E3d}ADT Tree 。typedefstructnode{chardata。structnode*lchild。structnode*rchild。}BTNode。:voidInsertnode(BTNode*&p,int&i,char*str>{intjudge=0。if(str[i]>='A'&&str[i]<='Z'>{judge++。p=(BTNode*>malloc(sizeof(BTNode>>。p->lchild=NULL。p->rchild=NULL。p->data=str[i]。i++。}if(str[i]=='\0'>{return。}if(str[i]=='('>{i++。if(!judge>{p=(BTNode*>malloc(sizeof(BTNode>>。p->lchild=NULL。p->rchild=NULL。}Insertnode(p->lchild,i,str>。Insertnode(