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

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为空集，则称为空树； &#

2、160;           若D仅含有一个数据元素，则R为空集，否则R=H，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；  (2)  若D-rootNULL，则存在D-root的一个划分D1,D2,D3, ,Dm(m>0)，对于任意jk(1j,km)有DjDk=NULL,且对任意的i(1im)，唯一存在数据元素xiDi有<root,xi>H; (3) 

3、对应于D-root的划分，H-<root,xi>,<root,xm>有唯一的一个划分H1，H2,Hm(m>0)，对任意jk(1j,km)有HjHk=NULL，且对任意i(1im),Hi是Di上的二元关系，(Di,Hi)是一棵符合本定义的树，称为根root的子树。基本操作P： InitTree(&T); 操作结果：构造空树T。 DestroyTree(&T); 初始条件：树T存在。 操作结果：销毁树T。 CreateTree(&T,definition); 初始条件：def

4、inition给出树T的定义。 操作结果：按definition构造树T。 ClearTree(&T); 初始条件：树T存在。 操作结果：将树T清为空树。 TreeEmpty(T); 初始条件：树T存在。 操作结果：若T为空树，则返回TRUE，否则返回FALSE。 TreeDepth(T); 初始条件：树T存在。 操作结果：返回的深度。 Root(T); 初始条件：树T存在。 操作结果：返回T的根。 Value(T,cur_e); 初始条

5、件：树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的非叶子结点，则

6、返回它的最左孩子，否则返回“空”。 RightSibling(T,cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回“空”。 InsertChild(&T,&p,I,c); 初始条件：树存在，指向中某个结点，1ip指结点的度，非空树与不相交。 操作结果：插入c为中指结点的第棵子树。DeleteChild(&T,&p,i); 初始条件：树T存在，p指向T中某个结点，1ip指结点的度。 操作结果：删除中所指结点的第棵

7、子树。 TraverseTree(T,visit(); 初始条件：树T存在，visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。 ADT Tree 3.2存储结构的定义;typedef struct node char data; struct node *lchild; struct node *rchild;BTNode;3.3基本操作实现:void Insertnode(BTNode *&p,int &i,char * s

8、tr) int judge = 0; if(stri>='A'&&stri<='Z') judge+; p = (BTNode *)malloc(sizeof(BTNode); p->lchild=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

9、; p->rchild=NULL; Insertnode(p->lchild,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

10、(p=NULL) return NULL; if(p->data=e) return p; else BTNode *b = FindNode(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("（&quo

11、t;); 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->lchild); int r = BTNodeDepth(b->rchild); return l>r?l+1:r+1; void search(BTNode

12、*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 < maxx; +i) if(ai>kmax) kmax = ai; return kmax;/* 求二叉树的节点个数 */int Node

13、s(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

14、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); 3.4解题思路：1 树的先序遍历：递归算法， 先输出根节点，再以左子树进行递归最后以右子树进行递归。 非递归算法，用栈模拟整个递归过程。2 树的中序遍历：递归算法，先以左子

15、树进行递归，再输出根节点，最后以右子树进行递归。 非递归算法，同上。3 树的后序遍历：递归算法，先以左子树进行递归，再后以右子树进行递归，最后输出根节点。非递归算法，同上。3.5解题过程：实验源代码如下：3.5.1实现二叉树的各种基本运算#include <iostream>#include <cstdio>#include <algorithm>#include <malloc.h>#define maxx 100using namespace std;typedef struct node char data; struct node *lc

16、hild; struct node *rchild;BTNode;void Insertnode(BTNode *&p,int &i,char * str) int judge = 0; if(stri>='A'&&stri<='Z') judge+; p = (BTNode *)malloc(sizeof(BTNode); p->lchild=NULL; p->rchild=NULL; p->data = stri; i+; if(stri='0') return ; if(stri

17、='(') 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=')') i+; return ; /* 由STR创建二叉链 */void CreateBTNode(BTNode *&b,char * str) int i = 0; Insertnode

18、(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 FindNode(p->rchild,e); /* 输出二叉树 */void DispBTNode(BTNode * b) if(b!=NULL) printf("%

19、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->lch

20、ild); int r = BTNodeDepth(b->rchild); return l>r?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

21、 = 0;i < maxx; +i) if(ai>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(BTNod

22、e * b) if(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); int

23、 main( ) BTNode *root, *p, *lp, *rp; CreateBTNode(root,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)"); printf("二叉树：n"); printf("（1）输出二叉树："); DispBTNode(root); puts(""); printf("（2）H节点："); p = FindNode(root,'H'); if(p!=NULL) lp = p->lchild; if(lp != NU

24、LL) printf("左孩子为 %c ",lp->data); else printf("无左孩子"); rp = p->rchild; if(rp != NULL) printf("右孩子为 %c ",rp->data); else printf("无右孩子"); puts(""); printf("（3）二叉树的深度： %dn",BTNodeDepth(root); printf("（4）二叉树的宽带： %dn",BTWidth(r

25、oot); printf("（5）二叉树的节点数:%dn",Nodes(root); printf("（6）二叉树的叶子节点个数：%dn",leafNodes(root); printf("（7）释放二叉树n"); DestroyBTNode(root); return 0;3.5.2二叉树的三序遍历#include <stdio.h>#include <malloc.h>#define maxsize 100typedef char Elemtype;typedef struct nodeElemtype d

26、ata;struct node *lchild;struct node *rchild;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;el

27、sep=(BTnode *)malloc(sizeof(BTnode);p->data = ch;p->lchild = p->rchild = NULL;if(b = NULL)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->rchil

28、d);void InOrder(BTnode *p)if(p!=NULL)InOrder(p->lchild);printf(" %c",p->data);InOrder(p->rchild);void PostOrder(BTnode *p)if(p!=NULL)PostOrder(p->lchild);PostOrder(p->rchild);printf(" %c",p->data);void PreOrder1(BTnode *p)BTnode *stmaxsize, *b;int top = -1;if(p

29、!= 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)BTnode *stmaxsize, *b;int top = -1;if(p != NULL)b = p;while(top>-1 |

30、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 = NULL;flag = 1;while(top

31、 != -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(",");DispBTnode(p->rchild);printf(")");void TravLevel(BTnode *b)BTno