《实现二叉树的各种遍历算法实验报告(共20页)》由会员分享，可在线阅读，更多相关《实现二叉树的各种遍历算法实验报告(共20页)（20页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上实现二叉树的各种遍历算法实验报告一 实验题目: 实现二叉树的各种遍历算法二 实验要求: 2.1:（1）输出二叉树 b（2） 输出H节点的左右孩子节点值（3） 输出二叉树b 的深度（4） 输出二叉树 b的宽度（5） 输出二叉树 b的节点个数（6） 输出二叉树 b的叶子节点个数（7） 释放二叉树 b2.2：（1）实现二叉树的先序遍历（2） 实现二叉树的中序遍历（3） 实现二叉树的后序遍历三 实验内容:3.1 树的抽象数据类型:ADTTree数据对象D：D是具有相同特性的数据元素的集合。数据关系 R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R=H，H
2、是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-rootNULL，则存在D-root的一个划分D1,D2,D3,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)
3、;初始条件：树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的值。Assi
4、gn(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有右兄弟，则返回它的右兄弟，否则返回“空”。Inse
5、rtChild(&T,&p,I,c);初始条件：树存在，指向中某个结点，1ip指结点的度，非空树与不相交。操作结果：插入c为中指结点的第棵子树。DeleteChild(&T,&p,i);初始条件：树T存在，p指向T中某个结点，1ip指结点的度。操作结果：删除中所指结点的第棵子树。TraverseTree(T,visit();初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。ADTTree3.2存储结构的定义;typedef struct node char data; struct
6、node *lchild; struct node *rchild;BTNode;3.3基本操作实现:void Insertnode(BTNode *&p,int &i,char * str) int judge = 0; if(stri=A&strilchild=NULL; p-rchild=NULL; p-data = stri; i+; if(stri=0) return ; if(stri=() i+; if(!judge) p = (BTNode *)malloc(sizeof(BTNode); p-lchild=NULL; p-rchild=NULL; Insertnode(p-l
7、child,i,str); Insertnode(p-rchild,i,str); if(stri=,|stri=) i+; return ; /* 由STR创建二叉链 */void CreateBTNode(BTNode *&b,char * str) int i = 0; Insertnode(b,i,str); /以递归形式插入数据，i 会跟着变化/* 查找e的节点指针 */BTNode * FindNode(BTNode * p, char e) if(p=NULL) return NULL; if(p-data=e) return p; else BTNode *b = FindNo
8、de(p-lchild,e); if(b!=NULL) return b; else return FindNode(p-rchild,e); /* 输出二叉树 */void DispBTNode(BTNode * b) if(b!=NULL) printf(%c,b-data); if(b-lchild!=NULL | b-rchild!=NULL) printf(（); DispBTNode(b-lchild); if(b-rchild != NULL)printf(，); DispBTNode(b-rchild); printf(）); /* 深度 */int BTNodeDepth(B
9、TNode *b) if(b=NULL) return 0; else int l = BTNodeDepth(b-lchild); int r = BTNodeDepth(b-rchild); return lr?l+1:r+1; void search(BTNode *p,int *a,int k) if(p!=NULL) ak+; search(p-lchild,a,k+1); search(p-rchild,a,k+1); /* 求二叉树的宽度 */int BTWidth(BTNode * b) int amaxx, i, kmax = 0; for(i = 0;i maxx; +i)
10、 ai = 0; int k = 0; search(b,a,k); for(i = 0;i kmax) kmax = ai; return kmax;/* 求二叉树的节点个数 */int Nodes(BTNode *b) if(b=NULL) return 0; else if(b-lchild = NULL & b-rchild = NULL) return 1; else int l = Nodes(b-lchild); int r = Nodes(b-rchild); return l + r + 1; /* 求叶子节点个数 */int leafNodes(BTNode * b) if
11、(b=NULL) return 0; else if(b-lchild = NULL & b-rchild = NULL) return 1; else int l = leafNodes(b-lchild); int r = leafNodes(b-rchild); return l + r; void DestroyBTNode(BTNode *&b) if(b!=NULL) DestroyBTNode(b-lchild); DestroyBTNode(b-rchild); free(b); 3.4解题思路：1 树的先序遍历：递归算法， 先输出根节点，再以左子树进行递归最后以右子树进行递归。 非递归算法，用栈模拟整个递归过程。2 树的中序遍历：递归算法，先以左子树进行递归，再输出根节点，最后以右子树进行递归。 非递归算法，同上。3 树的后序遍历：递归算法，先以左子树进行递归，再后以右子树进行递归，最后输出根节点。非递归算法，同上。3.5解题过程：实验源代码如下：3.5.1实现二叉树的各种基本运算#include #include #include #include #def
