2023年树和二叉树实验报告

树和二叉树实验报告课程一数据结构实验名称树和二叉树系别.计算机学院专业班级软件134姓名.徐雅欣学号实验日期：2023年6月7日实验目的：（-）掌握二叉树,二叉树排序数的概念及存储方法。（二）掌握二叉树的遍历算法（三）纯熟掌握编写实现树的各种运算的算法二.实验内容（-）实验题目一:建立一棵二叉树并中序遍历（填空）.要点分析：中序遍历的遍历规则是（前中后），既先访问左子树，在访问当前节点,最后访问右子树。.程序源代码：#include<stdio.h>#include<ma11oc.h>struetnode（»chardata;structnode*lchild,*rchild;}bnode;typedefstructnode*blink;blinkadd（blinkbt,charch）{®if(bt==NULL)

■C:\Users\Administrator\Desktop\程序\shiyanwu\Debug逐次遍历.exe"创建一颗二叉树＜纷表示空:二叉数层次遍历为：ABCDEPressanykeytocontinue口X(四)实验题目4：编写程序，对二叉树进行先序遍历,并打印层号。口X】.要点分析：从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种顺序执行三个操作：(1)访问结点自身(N),(2)遍历该结点的左子树(L),(3)遍历该结点的右子树(R)。根据遍历的原则：先左后右，对于先序遍历，顾名思义就是先访问根节点，再访问左子树，最后访问右子树,2.程序源代码：#include<stdio.h>include<std1ib.h>include<mal1oc.h>defineMAXSIZE50typedefcharDataType；structnodeDataTypedata;structnode*lchiId;〃指向左孩子结点structnode*rchild；//指向右孩子结点nt1evel;}BitNode;typedefstructnode*BiTree;voidCreateBiTree(BiTree*T)(eDataTypech;ch=getchar();♦if(ch=='#')o*T=NULL;®else{*T=(BiTree)mal1oc(sizeof(BitNode))；〃生成根节点aif(!(*T))•exit(-1)；。(*T)->data=ch;CrcateBiTree(&(*T)->lchild);//构造左子树CreateBiTree(&(*T)->rchild);//构造右子树}voidPreOrder(BiTreeT,int1eve1)//先序遍历的递归实现Mf(T)。(,sprintf(“为2c%2d\n〃，T->data,1eve1);»PreOrder(T->lchi1d,++level)；PreOrder(T—>rchild,leve1);)voidmainO(密订reeT=NULL;6intlev=1;printf("创建一颗二叉树:\n")；«CreateBiTree(&T);叩rintf('\n");printf("二叉数先序遍历及各点相应的层号为：\n〃);ogetchar();PreOrder〕,lev);3.实验结果:IL-H°IxB二叉数先序遍历及各点对应的层号为：■B2C2D3E3c:IPressanykeytocontinue（五）实验题目5：编写程序,实现二叉树的先序，中序，后序遍历，并求深度0.要点分析：了解先序，中序，后序。.程序源代码：#include<stdio.h>include<std1ib.h>include<malloc.h>#defineMAXSIZE50typedefcharDataType;structnodeDataTypedata;structnode*lchild;//指向左孩子结点ostructnode*rchi1d;〃指向右孩子结点}BitNode;typedefstructnode*BiTree；voidCreateBiTree(BiTree*T)DataTypech;ch=getchar();f(ch=='#')o*T=NULL;else»*T=(BiTree)malloc(sizeof(BitNode));//生成根节点aif(!(*T))。exit(-1);a(*T)—>data=ch;CreateBiTree(&(*T)->lchild)；//构造左子树CreateBiTree(&(*T)->rchild);〃构造右子树})voidPreOrder(BiTreeT)〃先序遍历的递归实现(f(T)(0。printfC%2c",T->data)；3PreOrder(T->1child);PreOrder(T—>rchiid)；voidInOi*der(BiTreeT)//中序遍历的递归实现oif(T)。(InOrder(T->lchiId);printf(“/2c”,T->data)；InOrder(T->rchiId);。})voidPostOrder(BiTreeT)〃后序遍历的递归实现(if(T)(。PostOrdcr(T—>lchi1d);PostOrder(T—>rchild);aprintf("%2cM,T->data);}BiTreeFindNode(BiTreeT,DataTypee)〃查找节点(BiTreep；oifgNULL)returnNULL：elseif(T->data==e)returnT;史Ise(»p=FindNode(T->lchi1d,e);~if(p!=NULL)。«>returnp;。else。oreturnFindNode(T—>rchild,e)；。})intBitTreeDepth(BiTreeT)(int1childepth,rchildepth;式f(T==NULL)^return0;e1se{1chiIdepth=BitTrceDcpth(T—>lchild);rchi1deplh=BitTreeDepth(T->rchi1d)；。if(Ichildepth>rchildepth)8return(lchiIdepth+1);oe1sereturn(rchildepth+1)；voidmain()(BiTreeT=NULL,root：ointh;®DataTypee;叩rintf(〃创建一颗二又树＜#＞表达子树为空：\n");eCreateBiTree(&T)；叩rintf("\n");oprintf("二叉数的先序遍历为:\n")；PreOrder(T);printf('\n");®printf("二叉数的中序遍历为:\n");•InOrder(T);printf("\n");叩rintf(〃二叉数的后序遍历为：\n〃)；©PostOrder(T);®printf(〃\n〃);®h=BitTreeDepth(T);printf("这课二义数的深度为%d:”,h)；egetchar()；"rintf(”\n\n输入要查找节点：〃)；“/scanf&e);e=getchar();root=FindNode(T,e);h=BitTreeDepth(root);PrintfC\n以%c结点为根的子树深度为%d:",e,h）;3.实验结果:'C:\Users\Administrator\Desktop\程序\shiyanwu\Debug选序、中序、，看序且求深度.exe"创建一颗二叉树“）表示子树为空:ABttltCDttttEtttt二叉数的先序遍历为：ABCDE二叉数的巾序遍历为：BADCE二叉数的后序遍历为：BDECA这课二叉数的深度为3：输入要查找节点：（六）实验题目6:编写递归算法,求二叉树中以元素值为x的结点为根的子树的深度。1.要点分析:递归过程•般通过函数或子过程来实现。递归方法:在函数或子过程的内逆,直接或者间接地调用自己的算法。递归算法所体现的“反复”•般有三个规定：一是每次调用在规模上都有所缩小（通常是减半）；二是相邻两次反复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）;三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达成直接解答的大小为条件)，无条件递归调用将会成为死循环而不能止常结束。2.程序源代码：#include"stdio.h"#include'stdlib.h"#inc1ude"string,h'a#definenul1Onstructnode(chardata；astructnode*lchild;astructnode*rchild；);aa//先序，中序建树astructnode*create(char*pre,char*ord,intn)a{structnode*head；Aintordsit;ahead=nul1；if(n<=0)(returnnu11;a}ae1se(head=(structnode*)malloc(sizeof(structnode))；Ahead->data=*pre;Ahead—>lchild二head—>rchiId二null;aordsit=0;while(ord[ordsit]!=*pre){7)rdsil++;a}head—>Ichiid=create(pre+1,ord»ordsit);ead—>rchild=create(pre+ordsit+1,ord+ordsit+1,n-ordsit-1);returnhead：。bt=(blink)ma11oc(sizeof(bnode));bt->data=ch;«»bt->lchi1d=bt—>rchild=NULL;}oelseif(ch<bt->data)~bt->lchild=add(bt—>1child,ch);else<4)t->rchild=add(bt->rchild,ch);returnbt；)voidinorder(blinkbt){if(bt)。(。inorder(bt—>Ichi1d);printfC%2c",bt—>data);inorder(bt->rchild);0})main()(blinkroot=NULL;inti,n；charx;seanf("%d*,&n);for(i=0;i<=n;i4-+)//中序递归遍历Avoidinorder(structnode*head){aif(!head)Areturn;acIsea(Ainorder(head->lchiId)；printf("%c",head->data);inorder(head->rchi1d)；a}}中序非递归遍历voidinorderi(structnode*head)(structnode*p;structnode*stack[20]；inttop=0;ap=head;while(p|11op!=0){Awhile(p){Astack[top++]=p;p=p->lchiId;}Ap=stack[-top];printf(飞c”,p->data);ap=p->rchild;}A}a〃主函数Aintmain()a{astructnode*head；acharpre[30],ord[30]；intn；agets(pre);gets(ord);an=str1en(pre);Ahead=create(pre,ord,n);Ainorder(head);

printf("\n");inorder1(head);aprintf("\n");a}3.实验结果:在运用程序设计求解问题实现功能时,我们一方面要对问题进行分析，将所要实现的功能分解成若干子功能来实现,这就需要对设计方法不断优化。队以同一问题，解决的方法很多，但寻求一个简朴的方法,一个可以用简朴的计算机语言语句实验的方法，才是问题额求解方法设计的关键。就像本次课程设计中实现二叉树树桩输出时,有很多方法来拟定二叉树结点和数组的相应关系，但适合计算机的简朴方法才是最佳最重要的。◎X=getcheir():groot=add(root,x);)inorder(root);•printf("\n")：)3.实验结果：皿事丁m7VpE»「二I-口x8ephqsbmaabehmpqsPressanykeytocontinue（二）实验题目2:编写程序,求二叉树的节点数和叶子树。.要点分析：.定理：二叉树假如有vO个叶子节点，那么就有v0-1个度为二的节点就是v0-l=v2a定理:二叉树有N个节点N=v0+vl+v2即节点总数等于度为0,1,2的节点的和。.程序源代码:#include<stdio.h>#inc1ude<ma1loc.h>阖defineERROR0^defineOK1#defineOVERFLOW-2#defineTRUE1typcdefintStatus；AtypedefcharTEIcmType；typedefstructBiTNode{TElemTypedata;structBiTNode*Ichi1d,*rchi1d;(BiTNode,*BiTree：Mntcount=0；AStatusCreateBiTree(BiTree*T){charch；Ascanf("%c”,&ch);if(ch==,')(*T)=NULL；ac1so)Aif(!((*T)=(BiTNode*)ma11oc(sizeof(BiTNode))))^exit(OVERFLOW);^(*T)->data=ch;^CreateBiTree(&((*T)->1chi1d));^CreateBiTree(&((*T)->rchild));}returnOK；}aStatusCountleaf(BiTreeT)(if(T){if((!T->lchild)&&(!T->rchiId))count++；aCountleaf(T->lchi1d)；aCountleaf(T->rchild)；A)Areturncount;)StatusDepth(BiTreeT){intdepthval,depthleft=0,depthright=0；Aif(!T)depthva1=0；Ae1se{depthleft=Depth(T->lchiId)；Mepthright=Depth(T->rchi1d)；depthval=l+(depth1eft>depthright?depthleft:depthright)；a}returndepthva1;}aStatusPreordcr(BiTrecT)a{if(T)a{printf(“猊"，T->data);Preorder(T->1child);Preorder(T->rchild)；a})StatusInOrderTraverse(BiTreeT,Status(*Visit)(TE1emTypee))(aStackS；InitStack(S);p=T；Awhile(p=!StackEmpty(S)){Mf(p){Push(S,p)；p=p—>lchild;}else{Pop(S,p);if(!Visit(p->data))returnERROR；Ap=p->rchi1(1；a}a}returnOK;}Avoidmain(){BiTreeT；Aprintf("pleaseinputaTree：/，);CreateBiTree(&T);printf("theTreeis:")；reorder(T)printfInOrderTraverse(T)；printf("\n")；Aprintf("thenumberofleavesis:〃)printfCountleaf(T));Pprintf("theDepthofthetreeis:〃)；printfDepth(T));petch();△}3.实验结果:'C:\Users\Administrator\Desktop\^/?\shiyanwu\Debug\^i5^»^WlH^^.exe'按照先序字符创建一颗二叉树〈以1t号表示空工ABDttttGHttttIttttCEttttFtttt这舜二叉科的节点鳌髻：9这楝二叉树的叶子数皂5Pressanykeytocontinue(三)实验题目3：编写程序，实现按层次遍历二叉树。.要点分析:定义：1、满二叉树：一棵深度为k且有2的k次方减I个结点的二叉树称为满二叉树2、完全二叉树:假如有深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一相应时，称之为完全二叉树。性质：I、二叉树的第i层上至多有2的i—1次方个结点(i>=1)。2、深度为k的二叉树至多有2的k次方减1个结点(k>=l)。、对任何一棵二叉树T,假如其终端结点数为nO,度为2的结点数为n2，则n0=n2+1。4、具有n个结点的完全二叉树的深度为以2为底n的对数取下限加1。5a、假如对一棵有n个结点的完全二叉树的结点按层序编号，则对任•结点i(gvi=vn)有：1(a)假如i=l,则结点i是二叉树的根，无双亲；假如i>l,则双亲PARENT(i)是结点［i/2卜(2)假如2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子LCHILD(i)是结点2i⑶假如2i+l>n,则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+l.存储结构:顺序存储结构（数组方式），链式存储结构（二叉链表）.程序源代码:#include<stdio.h>#include<stdlib.h>include<mal1oc.h>defineMAXS