资源描述：
《实现二叉树的各种遍历算法实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、.实现二叉树的各种遍历算法实验报告一实验题目:实现二叉树的各种遍历算法二实验要求:2.1:（1）输出二叉树b（2）输出H节点的左右孩子节点值（3）输出二叉树b的深度（4）输出二叉树b的宽度（5）输出二叉树b的节点个数（6）输出二叉树b的叶子节点个数（7）释放二叉树b2.2：（1）实现二叉树的先序遍历（2）实现二叉树的中序遍历（3）实现二叉树的后序遍历三实验内容:3.1树的抽象数据类型:ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R={H}，H
2、是如下二元关系： (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上的二元关系
3、，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。基本操作P： word范文.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
4、(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); 初始条
5、件：树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指结点的度＋１，非空树ｃ与Ｔ不相交。 word范文.操作结果：插入c为Ｔ中ｐ指结点的第ｉ棵子树。DeleteChild(&T,&p,i); 初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点
6、的度。 操作结果：删除Ｔ中ｐ所指结点的第ｉ棵子树。 TraverseTree(T,visit()); 初始条件：树T存在，visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。 }ADT Tree 3.2存储结构的定义;typedefstructnode{chardata;structnode*lchild;structnode*rchild;}BTNode;3.3基本操作实现:voidInsertnode(BTNode*&p,int&i,char*str){intjudge=0;
7、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]==' '){return;}if(str[i]=='('){word范文.i++;if(!judge){p=(BTNode*)malloc(sizeof(BTNode));p->lchild=NULL;p->rchild=NULL;}Insertnode(p->lchild,i,
