树和二叉树试验报告

1、树和二叉树实验报告树和二叉树实验报告课程_ 实验名称树和二叉树系别_计算机学院_专业班级_软件134_姓名_徐雅欣_ _学号_201300406134实验日期：2014年6月7日一.实验目的：（一）掌握二叉树，二叉树排序数的概念及存储方法。（二）掌握二叉树的遍历算法（三）熟练掌握编写实现树的各种运算的算法二.实验内容（）实验题目一：建立一棵二叉树并中序遍历（填空）1.要点分析：中序遍历的遍历规则是（前 中后），既先访问左子树，在访问当前节点，最后 访问右子树。2.程序源代码：#i nclude#i ncludestruct nodechar data;struct node *lchild,*

2、rchild;bno de;typedef struct node *bli nk; bli nk add(bli nkbt,char ch) if(bt=NULL)bt=(bli nk)malloc(sizeof(b no de); bt-data=ch;bt-lchild=bt-rchild=NULL;else if(chdata)bt-lchild=add(bt-lchild,ch);else bt-rchild=add(bt-rchild,ch);return bt;void in order(bli nk bt) if(bt)in order(bt-lchild);prin tf(%

3、2c,bt-data);ino rder(bt-rchild);mai n()blink root=NULL;int i,n;char x;sea nf(%d,&n); for(i=0;i=n ;i+) x=getchar(); root=add(root,x);ino rder(root); prin tf(n);3.实验结果：（二）实验题目2:编写程序，求二叉树的节点 数和叶子树。1.要点分析：.定理：二叉树如果有v0个 叶子 节点，那么就有v0-1个度为二的节点 就是v0-仁v2定理：二叉树有N个节点N=v0+v1+v2即节点总数等于度为0，1，2的节点的和。2.程序源代码：#in cl

4、ude#in clude#defi ne ERROR 0#defi ne OK 1#defi ne OVERFLOW -2#defi ne TRUE 1typedef int Status; typedef char TElemType; typedefstruct BiTNode TElemType data;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;int coun t=0;Status CreateBiTree(BiTree *T)char ch;sca nf(%c,&ch);if(ch= ) (*T)=NULL;else if(!(

5、*T)=(BiTNode*)malloc(sizeof(BiTNode )exit(OVERFLOW);(*T)-data=ch;CreateBiTree(&(*T)-lchild);CreateBiTree(&(*T)-rchild);return OK;Status Cou ntleaf(BiTree T)if(T) if(!T-lchild)&(!T-rchild) count+;Cou ntleaf(T-lchild);Countleaf(T-rchild );retur n count;Status Depth(BiTree T) int depthval,depthleft=O,d

6、epthright=O;if(!T) depthval=0;else depthleft=Depth(T-lchild);depthright=Depth(T-rchild);depthval=1+(depthleftdepthright?depthleft:depthright);retur n depthval;Status Preorder(BiTree T ) if(T) printf(%c ,T-data);Preorder(T-lchild );Preorder(T-rchild );Status InOrderTraverse(BiTree T,Status(*Visit)(TE

7、lemType e)Stack S;InitStack(S);p=T;while(p=!StackEmpty(S)if(p)Push(S,p);p=p-lchild;else Pop(S,p);if(!Visit(p-data) returnERROR;p=p-rchild;retur n OK;void mai n() BiTree T;prin tf(please in put a Tree:);CreateBiTree(&T);prin tf(the Tree is:);Preorder(T);prin tf(n);In OrderTraverse(T);prin tf(n);prin

8、tf(the nu mber of leaves is:);prin tf(%d,Cou ntleaf(T);prin tf(n);prin tf(the Depth of the tree is:);prin tf(%d,Depth(T); getch();3.实验结果：(三)实验题目3:编写程序，实现按层次遍 历二叉树。1.要点分析：定义：1、满二叉树：一棵深度为k且有2的k次方减1个结点的二叉树称为满二叉树2、完全二叉树：如果有深度为k的，有n个结 点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点-对应时，称之为完全二叉树。性质：1、二叉树的第i层上至多有2的i

9、-1次方个结点(i=1)。2、深度为k的二叉树至多有2的k次方减1个 结点(k=1)。3、对任何一棵二叉树T,如果其终端结点数为n0度为2的结点数为n2,则n0=n2+1。4、 具有n个结点的完全二叉树的深度为以2为 底n的对数取下限加1。5、如果对一棵有n个结点的完全二叉树的结点 按层序编号，则对任一结点i(1=i=1,则双亲PARENT(i)是结点i/2如果2in,则结点i无左孩子(结点i为叶子结 点);否则其左孩子LCHILD(i)是结点2i如果2i+1n,则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1.存储结构：顺序存储结构(数组方式)，链式存 储结构(二叉链表)2.程

10、序源代码：#include#in clude#i nclude#defi ne MAXSIZE 50typedef char DataType;struct nodeDataType data;struct node *lchild;struct node *rchild;BitNode;typedef struct node *BiTree;void CreateBiTree(BiTree *T)DataType ch;ch=getchar();if(ch=#*T=NULL;else*T=(BiTree)malloc(sizeof(BitNode); if(!(*T)exit(-1);(*T

11、)-data=ch;CreateBiTree(&(*T)-lchild);CreateBiTree(&(*T)-rchild);void LayerOrder(BiTree T)BiTree queueMAXSIZE;/BitNode *p;BiTree p;int fron t,rear;fron t=rear=-1;rear+;queuerear=T;while(fro nt!=rear)fron t=(fro nt+1)%MAXSIZE; p=queuefr on t;prin tf(%2c,p-data);if(p-lchild匸NULL)rear=(rea叶1)%MAXSIZE;qu

12、euerear=p-lchild;if(p-rchild!=NULL)rear=(rea叶1)%MAXSIZE;queuerear=p-rchild;pri ntf(n “);void mai n()BiTree T=NULL;printf(创建一颗二叉树#表示空:n)；CreateBiTree(&T);prin tf(n);printf(二叉数层次遍历为:n);LayerOrder(T);3.实 验 结 果（四）实验题目4:编写程序，对二叉树进行 先序遍历，并打印层号。1.要点分析：从二叉树的递归定义可知，一 棵非空的二叉树由根结点及左、右子树这三个基 本部分组成。因此，在任一给定结点上，可

13、以按 某种次序执行三个操作：（1） 访问结点本身（N），（2） 遍历该结点的左子树（L），（3） 遍历该结点的右子树（R）。根据遍历的原则：先左后右，对于先序遍历， 顾名思义就是先访问根节点，再访问左子树，最 后访问右子树，2.程序源代码：#include#in clude#i nclude#defi ne MAXSIZE 50typedef char DataType;struct nodeDataType data;struct n ode *lchild; /指向左孩子结点struct n ode *rchild; /指向右孩子结点int level;BitNode;typedef st

14、ruct node *BiTree;void CreateBiTree(BiTree *T) DataType ch; ch=getchar(); if(ch=#)*T=NULL; else*T=(BiTree)malloc(sizeof(BitNode);/生成根节点if(!(*T)exit(-1);(*T)-data=ch;CreateBiTree(&(*T)-lchild);/构造左子树CreateBiTree(&(*T)-rchild);/构造右子树void PreOrder(BiTree T,i nt level) /先序遍历的递归实现if(T)printf(%2c %2dn,T-d

15、ata,level);PreOrder(T-lchild,+level);PreOrder(T-rchild,level);void mai n()BiTree T=NULL;int lev=1;printf(创建一颗二叉树:n);CreateBiTree(&T);prin tf(n);prin tf(二叉数先序遍历及各点对应的层号为:n);getchar();PreOrder(T,lev);3.实验结果:（五）实验题目5:编写程序，实现二叉树的 先序，中序，后序遍历，并求深度。1.要点分析：了解先序，中序，后序。2.程序源代码：#include#in clude#in clude#defi

16、ne MAXSIZE 50 typedef char DataType; structnodeDataType data;struct n ode *lchild; /指向左孩子结点struct n ode *rchild; /指向右孩子结点BitNode;typedef struct node *BiTree;void CreateBiTree(BiTree *T)DataType ch; ch=getchar(); if(ch=#)*T=NULL; else *T=(BiTree)malloc(sizeof(BitNode);/生成根节点if(!(*T)exit(-1);(*T)-data

17、=ch;CreateBiTree(&(*T)-lchild);/构造左子树CreateBiTree(&( *T)-rchild);/构造右子树void PreOrder(BiTree T) /先序遍历的递归实现if(T)printf(%2c,T-data);PreOrder仃-lchild);PreOrder (T-rchild);void In Order(BiTree T) /中序遍历的递归实现if(T)In Order(T-lchild); prin tf(%2c,T-data);In Order(T-rchild);void PostOrder(BiTree T) /归实现if(T)P

18、ostOrder(T-lchild);PostOrder(T-rchild);prin tf(%2c,T-data);BiTree FindNode(BiTreeDataType e) /查找节点BiTree p;if(T=NULL)return NULL;后序遍历的递else if(T-data=e)return T;elsep=F in dNode(T-lchild,e);if(p!=NULL) return p;elsereturn Fin dNode(T-rchild,e);int BitTreeDepth(BiTree T)int lchildepth,rchildepth; if(

19、T=NULL)return 0;elselchildepth=BitTreeDepth(T-lchild);rchildepth=BitTreeDepth(T-rchild);if(lchildepthrchildepth)retur n(lchildepth+1);elseretur n( rchildepth+1);void mai n()BiTree T=NULL,root;int h;DataType e;printf(创建一颗二叉树表示子树为空n);CreateBiTree(&T);prin tf(n);printf(二叉数的先序遍历为：n);PreOrder(T);prin tf(

20、n);printf(二叉数的中序遍历为:n);In Order(T);prin tf(n);printf(二叉数的后序遍历为:n);PostOrder(T);prin tf(n);h=BitTreeDepth(T);printf(这课二叉数的深度为%d: ,h);getchar();printf(nn输入要查找节点：);sca nf(%c, &e);e=getchar();root=F in dNode(T,e);h=BitTreeDepth(root);printf(n以住吉点为根的子树深度为%d:,e,h);prin tf(n);3.实验结果：（六）实验题目6:编写递归算法，求二叉树 中以

21、元素值为x的结点为根的子树的深度。1.要点分析：递归过程一般通过函数或子过程来实现。递归 方法：在函数或子过程的内部，直接或者间接 地调用自己的算法。递归算法所体现的“重复” 一般有三个要求：一是每次调用在规模上都有所缩小（通常是 减半）；二是相邻两次重复之间有紧密的联系，前一 次要为后一次做准备（通常前一次的输出就作为 后一次的输入）；三是在问题的规模极小时必须用直接给出解 答而不再进行递归调用，因而每次递归调用都是 有条件的(以规模未达到直接解答的大小为条 件)，无条件递归调用将会成为死循环而不能正 常结束。2.程序源代码：#i nclude stdio.h#include stdlib.

22、h#include string.h#defi ne null 0struct nodechar data;struct node *lchild;struct node *rchild;/先序，中序建树struct node *create(char *pre,char *ord,i nt n)struct node * head;int ordsit;head=null;if(n data=*pre; head-lchild=head-rchild=null;ordsit=0;while(ordordsit!=*pre)ordsit+;head-lchild=create(pre+1,ord,ordsit);head-rchild=create(pre+ordsit+1,ord+ordsit+1, n-ordsit-1); return head;/中序递归遍历void in order(struct node *head)if(!head)return;elsein order(hea