实现二叉树的各种遍历算法实验报告

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是如下二元关系：(1)在D

2、中存在唯一的称为根的数据元素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);初始条件：树T存在。操作

3、结果：销毁树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,va

4、lue);初始条件：树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

5、,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 node *lchild;

6、 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-lchild,i,str);

7、 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 = FindNode(p-lchild,e

8、); 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(BTNode *b) if(

9、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) ai = 0; int

10、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(b=NULL) retu

11、rn 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 树的先序遍历：递归算法， 先输出根节点，再以左子树进行递归最后以右子树进行递归。 非递归算法，用栈模拟整

12、个递归过程。2 树的中序遍历：递归算法，先以左子树进行递归，再输出根节点，最后以右子树进行递归。 非递归算法，同上。3 树的后序遍历：递归算法，先以左子树进行递归，再后以右子树进行递归，最后输出根节点。非递归算法，同上。3.5解题过程：实验源代码如下：3.5.1实现二叉树的各种基本运算#include #include #include #include #define maxx 100using namespace std;typedef struct node char data; struct node *lchild; struct node *rchild;BTNode;void I

13、nsertnode(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-lchild,i,str); Insertnode(p-rchild,i,str); if(stri=,|stri=

14、) 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 = FindNode(p-lchild,e); if(b!=NULL) return b; else return FindNod

15、e(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(BTNode *b) if(b=NULL) return 0; else int l = BTNodeDepth(b

16、-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) ai = 0; int k = 0; search(b,a,k); for(i = 0;i kmax) kmax

17、 = 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(b=NULL) return 0; else if(b-lchild = NULL & b-rchild = N

18、ULL) 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); int main( ) BTNode *root, *p, *lp, *rp; CreateBTNode(root,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I); printf(二叉树：n);

19、printf(（1）输出二叉树：); DispBTNode(root); puts(); printf(（2）H节点：); p = FindNode(root,H); if(p!=NULL) lp = p-lchild; if(lp != NULL) printf(左孩子为 %c ,lp-data); else printf(无左孩子); rp = p-rchild; if(rp != NULL) printf(右孩子为 %c ,rp-data); else printf(无右孩子); puts(); printf(（3）二叉树的深度： %dn,BTNodeDepth(root); print

20、f(（4）二叉树的宽带： %dn,BTWidth(root); printf(（5）二叉树的节点数:%dn,Nodes(root); printf(（6）二叉树的叶子节点个数：%dn,leafNodes(root); printf(（7）释放二叉树n); DestroyBTNode(root); return 0;3.5.2二叉树的三序遍历#include #include #define maxsize 100typedef char Elemtype;typedef struct nodeElemtype data;struct node *lchild;struct node *rchi

21、ld;BTnode;void CreateBTnode(BTnode *&b,char *str)BTnode *stmaxsize, *p = NULL;int top = - 1, k, j = 0;char ch;b = NULL;ch = strj;while(ch!=0)if(ch = ()top+;sttop = p;k = 1;else if(ch = )top-;else if(ch = ,)k = 2;elsep=(BTnode *)malloc(sizeof(BTnode);p-data = ch;p-lchild = p-rchild = NULL;if(b = NULL

22、)b = p;elseif(k = 1)sttop-lchild = p;else if(k = 2)sttop-rchild = p;j+;ch = strj;void PreOrder(BTnode *p)if(p!=NULL)printf( %c,p-data);PreOrder(p-lchild);PreOrder(p-rchild);void InOrder(BTnode *p)if(p!=NULL)InOrder(p-lchild);printf( %c,p-data);InOrder(p-rchild);void PostOrder(BTnode *p)if(p!=NULL)Po

23、stOrder(p-lchild);PostOrder(p-rchild);printf( %c,p-data);void PreOrder1(BTnode *p)BTnode *stmaxsize, *b;int top = -1;if(p != NULL)top+;sttop = p;while(top -1)b = sttop;top-;printf( %c,b-data);if(b-rchild != NULL)st+top = b-rchild;if(b-lchild !=NULL)st+top = b-lchild;printf(n);void InOrder1(BTnode *p

24、)BTnode *stmaxsize, *b;int top = -1;if(p != NULL)b = p;while(top-1 | b != NULL)while(b != NULL)st+top = b;b = b-lchild;if(top-1)b = sttop-;printf( %c,b-data);b=b-rchild;printf(n);void PostOrder1(BTnode *p)BTnode *stmaxsize, *b;int top = -1,flag;if(p != NULL)dowhile(p != NULL)st+top = p;p=p-lchild;b

25、= NULL;flag = 1;while(top != -1 & flag)p = sttop;if(p-rchild = b)printf( %c,p-data);top-;b = p;elsep = p-rchild;flag = 0;while(top-1);printf(n);void DestroyBTNode(BTnode *p)if(p!=NULL)DestroyBTNode(p-lchild);DestroyBTNode(p-rchild);free(p);void DispBTnode(BTnode *p)if(p != NULL)printf(%c,p-data);if(p-lchild != NULL | p-rchild != NULL)printf();DispBTnode(p-lchild);if(p-rchild != NULL) printf(,);