文档介绍:蚈实现二叉树的各种遍历算法实验报告薄蚂一实验题目:实现二叉树的各种遍历算法莈二实验要求::(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; 肈(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的子树。膇基本操作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()失败,则操作失败。 羂}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-