实验报告(二叉树)

1、仲恺农业工程学院实验报告纸信息科学与技术（院、系） 计算机 专业 144 班 数据结构与算法 课学号201420224417 姓名刘智龙 实验日期 2015.12.8 教师评定 一、实验目的1、掌握二叉树的特点，以及的二叉链表存储结构。2、熟练掌握二叉树的各种操作，如建立、遍历、查找和输出。3、利用已经掌握的知识进行实际应用。二、实验环境1) 硬件：每个学生需配备计算机一台，操作系统：Windows2000/XP。2) 软件：visual c+6.0。三、实验题目和实验内容实验题目：二叉树操作及应用实验内容：1、基本题：教材实验7.1、实验7.2、实验7.3的（1）和（2）2、附加题：实验7.

2、6、实验7.8、四、实验项目的程序结构（包含的各个文件中的函数调用功能描述、程序中的函数调用关系图）(可写可不写) exp2-1.cpp文件main algo2-1.cpp文件InitListListInsert五、实验数据和实验结果（程序运行结果的截图）实验7.1结果：实验7.2结果：实验7.3结果：六、附录（程序代码）实验7.1源代码：#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;/数据元素s

3、truct node *lchild;/指向左孩子struct node *rchild;/指向右孩子 BTNode;void CreateBTNode(BTNode *&b,char *str)/由str串创建二叉链BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/建立的二叉树初始时为空ch=strj;while (ch!='0')/str未扫描完时循环 switch(ch) case '(':top+;Sttop=p;k=1; break;/为左节点case ')'

4、:top-;break;case ',':k=2; break; /为右节点default:p=(BTNode *)malloc(sizeof(BTNode);p->data=ch;p->lchild=p->rchild=NULL; if (b=NULL) /p指向二叉树的根节点b=p;else /已建立二叉树根节点switch(k) case 1:Sttop->lchild=p;break;case 2:Sttop->rchild=p;break;j+;ch=strj;BTNode *FindNode(BTNode *b,ElemType x)/

5、返回data域为x的节点指针BTNode *p;if (b=NULL) return NULL;else if (b->data=x) return b;elsep=FindNode(b->lchild,x);if (p!=NULL) return p;else return FindNode(b->rchild,x);BTNode *LchildNode(BTNode *p)/返回*p节点的左孩子节点指针 return p->lchild;BTNode *RchildNode(BTNode *p)/返回*p节点的右孩子节点指针 return p->rchild;

6、int BTNodeDepth(BTNode *b)/求二叉树b的深度 int lchilddep,rchilddep; if (b=NULL) return(0); /空树的高度为0 else lchilddep=BTNodeDepth(b->lchild);/求左子树的高度为lchilddep rchilddep=BTNodeDepth(b->rchild);/求右子树的高度为rchilddepreturn (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1); void DispBTNode(BTNode *b)/以括号表

7、示法输出二叉树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 BTWidth(BTNode *b) /求二叉树b的宽度struct int lno;/节点的层次编号BTNode *

8、p;/节点指针 QuMaxSize;/定义顺序非循环队列int front,rear;/定义队首和队尾指针int lnum,max,i,n;front=rear=0;/置队列为空队 if (b!=NULL) rear+;Qurear.p=b;/根节点指针入队Qurear.lno=1;/根节点的层次编号为1while (rear!=front)/队列不为空front+;b=Qufront.p;/队头出队lnum=Qufront.lno;if (b->lchild!=NULL)/左孩子入队rear+;Qurear.p=b->lchild;Qurear.lno=lnum+1;if (b-

9、>rchild!=NULL)/右孩子入队rear+;Qurear.p=b->rchild;Qurear.lno=lnum+1;max=0;lnum=1;i=1;while (i<=rear)n=0;while (i<=rear && Qui.lno=lnum) n+;i+;lnum=Qui.lno;if (n>max) max=n;return max;elsereturn 0;int Nodes(BTNode *b)/求二叉树b的节点个数int num1,num2; if (b=NULL) return 0; else if (b->lch

10、ild=NULL && b->rchild=NULL) return 1; else num1=Nodes(b->lchild); num2=Nodes(b->rchild); return (num1+num2+1);int LeafNodes(BTNode *b)/求二叉树b的叶子节点个数int num1,num2; if (b=NULL) return 0; else if (b->lchild=NULL && b->rchild=NULL) return 1; else num1=LeafNodes(b->lchild

11、); num2=LeafNodes(b->rchild); return (num1+num2);void DestroyBTNode(BTNode *&b)if (b!=NULL)DestroyBTNode(b->lchild);DestroyBTNode(b->rchild);free(b);void main()BTNode *b,*p,*lp,*rp;CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)");printf("二叉树的基本运算如下:n");printf("

12、 (1)输出二叉树:");DispBTNode(b);printf("n");printf(" (2)H节点:");p=FindNode(b,'H');if (p!=NULL)lp=LchildNode(p);if (lp!=NULL) printf("左孩子为%c ",lp->data);elseprintf("无左孩子 ");rp=RchildNode(p);if (rp!=NULL)printf("右孩子为%c",rp->data);elseprint

13、f("无右孩子 ");printf("n");printf(" (3)二叉树b的深度:%dn",BTNodeDepth(b);printf(" (4)二叉树b的宽度:%dn",BTWidth(b);printf(" (5)二叉树b的节点个数:%dn",Nodes(b);printf(" (6)二叉树b的叶子节点个数:%dn",LeafNodes(b);printf(" (7)释放二叉树bn");DestroyBTNode(b);实验7.2源代码：#incl

14、ude <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;/数据元素struct node *lchild;/指向左孩子struct node *rchild;/指向右孩子 BTNode;void CreateBTNode(BTNode *&b,char *str)/由str串创建二叉链BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/建立的

15、二叉树初始时为空ch=strj;while (ch!='0')/str未扫描完时循环 switch(ch) case '(':top+;Sttop=p;k=1; break;/为左节点case ')':top-;break;case ',':k=2; break; /为右节点default:p=(BTNode *)malloc(sizeof(BTNode);p->data=ch;p->lchild=p->rchild=NULL; if (b=NULL) /p指向二叉树的根节点b=p;else /已建立二叉树根节点

16、switch(k) case 1:Sttop->lchild=p;break;case 2:Sttop->rchild=p;break;j+;ch=strj;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(",&q

17、uot;);DispBTNode(b->rchild);printf(")");void DestroyBTNode(BTNode *&b)if (b!=NULL)DestroyBTNode(b->lchild);DestroyBTNode(b->rchild);free(b);void PreOrder(BTNode *b) /先序遍历的递归算法if (b!=NULL) printf("%c ",b->data);/访问根节点PreOrder(b->lchild);/递归访问左子树PreOrder(b->rc

18、hild);/递归访问右子树void PreOrder1(BTNode *b)BTNode *StMaxSize,*p; int top=-1; if (b!=NULL) top+;/根节点入栈 Sttop=b; while (top>-1)/栈不为空时循环 p=Sttop;/退栈并访问该节点 top-; printf("%c ",p->data); if (p->rchild!=NULL)/右孩子入栈 top+; Sttop=p->rchild; if (p->lchild!=NULL)/左孩子入栈 top+; Sttop=p->lch

19、ild;printf("n");void InOrder(BTNode *b) /中序遍历的递归算法if (b!=NULL) InOrder(b->lchild);/递归访问左子树printf("%c ",b->data);/访问根节点InOrder(b->rchild);/递归访问右子树void InOrder1(BTNode *b)BTNode *StMaxSize,*p;int top=-1;if (b!=NULL)p=b;while (top>-1 | p!=NULL)while (p!=NULL)top+;Sttop=p

20、;p=p->lchild;if (top>-1)p=Sttop;top-;printf("%c ",p->data);p=p->rchild;printf("n");void PostOrder(BTNode *b) /后序遍历的递归算法if (b!=NULL) PostOrder(b->lchild);/递归访问左子树PostOrder(b->rchild);/递归访问右子树printf("%c ",b->data);/访问根节点void PostOrder1(BTNode *b)BTNod

21、e *StMaxSize;BTNode *p;int flag,top=-1;/栈指针置初值if (b!=NULL)dowhile (b!=NULL)/将t的所有左节点入栈top+;Sttop=b;b=b->lchild;p=NULL;/p指向当前节点的前一个已访问的节点flag=1;while (top!=-1 && flag)b=Sttop;/取出当前的栈顶元素if (b->rchild=p)/右子树不存在或已被访问,访问之printf("%c ",b->data);/访问*b节点top-;p=b;/p指向则被访问的节点elseb=b-

22、>rchild;/t指向右子树flag=0; while (top!=-1);printf("n"); void TravLevel(BTNode *b)BTNode *QuMaxSize;/定义循环队列int front,rear;/定义队首和队尾指针front=rear=0;/置队列为空队列 if (b!=NULL) printf("%c ",b->data); rear+;/节点指针进入队列Qurear=b; while (rear!=front)/队列不为空 front=(front+1)%MaxSize;b=Qufront;/队头出

23、队列if (b->lchild!=NULL)/输出左孩子,并入队列printf("%c ",b->lchild->data);rear=(rear+1)%MaxSize;Qurear=b->lchild;if (b->rchild!=NULL)/输出右孩子,并入队列printf("%c ",b->rchild->data);rear=(rear+1)%MaxSize;Qurear=b->rchild; printf("n");void main()BTNode *b;CreateBTNo

24、de(b,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)"); printf("二叉树b:");DispBTNode(b);printf("n");printf("层次遍历序列:");TravLevel(b);printf("先序遍历序列:n");printf(" 递归算法:");PreOrder(b);printf("n");printf(" 非递归算法:");PreOrder1(b);printf("中序

25、遍历序列:n");printf(" 递归算法:");InOrder(b);printf("n");printf(" 非递归算法:");InOrder1(b);printf("后序遍历序列:n");printf(" 递归算法:");PostOrder(b);printf("n");printf(" 非递归算法:");PostOrder1(b);DestroyBTNode(b); 实验7.3源代码：#include <stdio.h>#i

26、nclude <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;/数据元素struct node *lchild;/指向左孩子struct node *rchild;/指向右孩子 BTNode;void CreateBTNode(BTNode *&b,char *str)/由str串创建二叉链BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/建立的二叉树初始时为空ch=strj;while

27、 (ch!='0')/str未扫描完时循环 switch(ch) case '(':top+;Sttop=p;k=1; break;/为左节点case ')':top-;break;case ',':k=2; break; /为右节点default:p=(BTNode *)malloc(sizeof(BTNode);p->data=ch;p->lchild=p->rchild=NULL; if (b=NULL) /p指向二叉树的根节点b=p;else /已建立二叉树根节点switch(k) case 1:Stto

28、p->lchild=p;break;case 2:Sttop->rchild=p;break;j+;ch=strj;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-&g

29、t;rchild);printf(")");void DestroyBTNode(BTNode *&b)if (b!=NULL)DestroyBTNode(b->lchild);DestroyBTNode(b->rchild);free(b);void AllPath(BTNode *b)struct snode BTNode *node;/存放当前节点指针 int parent;/存放双亲节点在队列中的位置 QuMaxSize;/定义顺序队列int front,rear,p;/定义队头和队尾指针 front=rear=-1;/置队列为空队列rear+;

30、 Qurear.node=b;/根节点指针进入队列Qurear.parent=-1;/根节点没有双亲节点 while (front<rear)/队列不为空 front+;b=Qufront.node;/队头出队列if (b->lchild=NULL && b->rchild=NULL)/*b为叶子节点printf(" %c到根节点逆路径:",b->data);p=front;while (Qup.parent!=-1)printf("%c ",Qup.node->data);p=Qup.parent;prin

31、tf("%cn",Qup.node->data);if (b->lchild!=NULL)/左孩子入队列rear+;Qurear.node=b->lchild;Qurear.parent=front;if (b->rchild!=NULL)/右孩子入队列rear+;Qurear.node=b->rchild;Qurear.parent=front; void AllPath1(BTNode *b,ElemType path,int pathlen)int i;if (b!=NULL)if (b->lchild=NULL &&

32、; b->rchild=NULL)/*b为叶子节点printf(" %c到根节点逆路径: %c ",b->data,b->data);for (i=pathlen-1;i>=0;i-)printf("%c ",pathi);printf("n");elsepathpathlen=b->data;/将当前节点放入路径中pathlen+;/路径长度增1AllPath1(b->lchild,path,pathlen);/递归扫描左子树AllPath1(b->rchild,path,pathlen);/递归扫描右子树pathlen-;/恢复环境void LongPath(BTNode *b,ElemType path,int pathlen,ElemType longpath,int &longpathlen)int i;if (b=NULL