2024年树和二叉树实验报告

树和二叉树试验报告课程数据结构试验名称树和二叉树系别____计算机学院专业班级__软件134_____姓名__徐雅欣____学号_00406134试验日期：年6月7日试验目标:掌握二叉树，二叉树排序数的概念及存储措施。掌握二叉树的遍历算法纯熟掌握编写实现树的各种运算的算法试验内容（－）试验题目一：建立一棵二叉树并中序遍历（填空）1.要点分析：中序遍历的遍历规则是（前中后），既先访问左子树，在访问目前节点，最后访问右子树。2.程序源代码：#include<stdio.h>#include<malloc.h>structnode{ chardata; structnode*lchild,*rchild;}bnode;typedefstructnode*blink;blinkadd(blinkbt,charch){ if(bt==NULL) { bt=(blink)malloc(sizeof(bnode)); bt->data=ch; bt->lchild=bt->rchild=NULL; } elseif(ch<bt->data) bt->lchild=add(bt->lchild,ch); else bt->rchild=add(bt->rchild,ch);returnbt;}voidinorder(blinkbt){ if(bt) { inorder(bt->lchild); printf("%2c",bt->data);inorder(bt->rchild); }}main(){ blinkroot=NULL; inti,n; charx; scanf("%d",&n); for(i=0;i<=n;i++) { x=getchar(); root=add(root,x); } inorder(root); printf("\n");}3.试验成果：（二）试验题目2：编写程序，求二叉树的节点数和叶子树。1.要点分析：.定理：二叉树假如有v0个叶子节点，那么就有v0-1个度为二的节点就是v0-1=v2

定理：二叉树有N个节点N=v0+v1+v2即节点总数等于度为0，1，2的节点的和。2.程序源代码：#include<stdio.h>

#include<malloc.h>

#defineERROR0

#defineOK1

#defineOVERFLOW-2

#defineTRUE1

typedefintStatus;

typedefcharTElemType;typedefstructBiTNode

{TElemTypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

intcount=0;

StatusCreateBiTree(BiTree*T)

{

charch;

scanf("%c",&ch);

if(ch=='')(*T)=NULL;

else{

if(!((*T)=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);

(*T)->data=ch;

CreateBiTree(&((*T)->lchild));

CreateBiTree(&((*T)->rchild));

}

returnOK;

}

StatusCountleaf(BiTreeT)

{if(T)

{if((!T->lchild)&&(!T->rchild))count++;

Countleaf(T->lchild);

Countleaf(T->rchild);

}

returncount;

}

StatusDepth(BiTreeT)

{intdepthval,depthleft=0,depthright=0;

if(!T)depthval=0;

else

{depthleft=Depth(T->lchild);

depthright=Depth(T->rchild);

depthval=1+(depthleft>depthright?depthleft:depthright);

}

returndepthval;

}

StatusPreorder(BiTreeT)

{if(T)

{printf("%c",T->data);

Preorder(T->lchild);

Preorder(T->rchild);

}

}

StatusInOrderTraverse（BiTreeT，Status

（*Visit）（TElemTypee））{

StackS；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;

}

}

returnOK;

}

voidmain()

{BiTreeT;

printf("pleaseinputaTree:");

CreateBiTree(&T);

printf("theTreeis:");

Preorder(T);

printf("\n");

InOrderTraverse（T）；

printf("\n");

printf("thenumberofleavesis:");

printf("%d",Countleaf(T));

printf("\n");

printf("theDepthofthetreeis:");

printf("%d",Depth(T));

getch();

}3.试验成果：（三）试验题目3：编写程序，实现按层次遍历二叉树。1.要点分析：定义：1、满二叉树：一棵深度为k且有2的k次方减1个结点的二叉树称为满二叉树2、完全二叉树：假如有深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。性质：1、二叉树的第i层上至多有2的i-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=<n)有：

(1)假如i=1,则结点i是二叉树的根,无双亲;假如i>1,则双亲PARENT(i)是结点[i/2]

(2)假如2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子LCHILD(i)是结点2i

(3)假如2i+1>n,则结点i无右孩子;否则其右孩子RCHILD(i)是结点2i+1.存储结构：次序存储结构（数组方式），链式存储结构（二叉链表）2.程序源代码：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineMAXSIZE50typedefcharDataType;structnode{ DataTypedata; structnode*lchild; structnode*rchild;}BitNode;typedefstructnode*BiTree;voidCreateBiTree(BiTree*T){ DataTypech; 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); }}voidLayerOrder(BiTreeT){ BiTreequeue[MAXSIZE]; //BitNode*p; BiTreep; intfront,rear; front=rear=-1; rear++; queue[rear]=T; while(front!=rear) { front=(front+1)%MAXSIZE; p=queue[front]; printf("%2c",p->data); if(p->lchild!=NULL) { rear=(rear+1)%MAXSIZE; queue[rear]=p->lchild; } if(p->rchild!=NULL) { rear=(rear+1)%MAXSIZE; queue[rear]=p->rchild; } } printf("\n");}voidmain(){ BiTreeT=NULL; printf("创建一颗二叉树<#>表示空:\n"); CreateBiTree(&T); printf("\n"); printf("二叉数层次遍历为:\n"); LayerOrder(T);}3.试验成果：（四）试验题目4：编写程序，对二叉树进行先序遍历，并打印层号。1.要点分析：从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，能够按某种次序执行三个操作：（1）访问结点自身(N)，（2）遍历该结点的左子树(L)，（3）遍历该结点的右子树(R)。依照遍历的标准：先左后右，对于先序遍历，顾名思义就是先访问根节点，再访问左子树，最后访问右子树，2.程序源代码：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineMAXSIZE50typedefcharDataType;structnode{ DataTypedata; structnode*lchild;//指向左孩子结点 structnode*rchild;//指向右孩子结点 intlevel;}BitNode;typedefstructnode*BiTree;voidCreateBiTree(BiTree*T){ DataTypech; 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);//结构右子树 }}voidPreOrder(BiTreeT,intlevel)//先序遍历的递归实现{ if(T) { printf("%2c%2d\n",T->data,level); PreOrder(T->lchild,++level);PreOrder(T->rchild,level); }}voidmain(){ BiTreeT=NULL; intlev=1; printf("创建一颗二叉树:\n"); CreateBiTree(&T); printf("\n"); printf("二叉数先序遍历及各点对应的层号为:\n"); getchar(); PreOrder(T,lev);}3.试验成果：（五）试验题目5：编写程序，实现二叉树的先序，中序，后序遍历，并求深度。1.要点分析：了解先序，中序，后序。2.程序源代码：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineMAXSIZE50typedefcharDataType;structnode{ DataTypedata; structnode*lchild;//指向左孩子结点 structnode*rchild;//指向右孩子结点}BitNode;typedefstructnode*BiTree;voidCreateBiTree(BiTree*T){ DataTypech; 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);//结构右子树 }}voidPreOrder(BiTreeT)//先序遍历的递归实现{ if(T) { printf("%2c",T->data); PreOrder(T->lchild);PreOrder(T->rchild); }}voidInOrder(BiTreeT)//中序遍历的递归实现{ if(T) { InOrder(T->lchild); printf("%2c",T->data);InOrder(T->rchild); }}voidPostOrder(BiTreeT)//后序遍历的递归实现{ if(T) { PostOrder(T->lchild);PostOrder(T->rchild); printf("%2c",T->data); }}BiTreeFindNode(BiTreeT,DataTypee)//查找节点{ BiTreep; if(T==NULL) returnNULL; elseif(T->data==e) returnT; else { p=FindNode(T->lchild,e); if(p!=NULL) returnp; else returnFindNode(T->rchild,e); }}intBitTreeDepth(BiTreeT){ intlchildepth,rchildepth; if(T==NULL) return0; else { lchildepth=BitTreeDepth(T->lchild); rchildepth=BitTreeDepth(T->rchild); if(lchildepth>rchildepth) return(lchildepth+1); else return(rchildepth+1); }}voidmain(){ BiTreeT=NULL,root; inth; DataTypee; printf("创建一颗二叉树<#>表示子树为空:\n"); CreateBiTree(&T); printf("\n"); printf("二叉数的先序遍历为:\n"); PreOrder(T); printf("\n"); printf("二叉数的中序遍历为:\n"); InOrder(T); printf("\n"); printf("二叉数的后序遍历为:\n"); PostOrder(T); printf("\n"); h=BitTreeDepth(T);printf("这课二叉数的深度为%d:",h); getchar(); printf("\n\n输入要查找节点:"); //scanf("%c",&e); e=getchar();root=FindNode(T,e);h=BitTreeDepth(root); printf("\n以%c结点为根的子树深度为%d:",e,h);printf("\n");}3.试验成果：（六）试验题目6：编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。1.要点分析：递归过程一般通过函数或子过程来实现。递归措施：在函数或子过程的内部，直接或者间接地调用自己的算法。递归算法所体现的“重复”一般有三个要求：一是每次调用在规模上都有所缩小(一般是减半)；二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(一般前一次的输出就作为后一次的输入)；三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达成直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。2.程序源代码：#include"stdio.h"

#include"stdlib.h"

#include"string.h"

#definenull0

structnode

{

chardata;

structnode*lchild;

structnode*rchild;

};

//先序，中序建树

structnode*create(char*pre,char*ord,intn)

{

structnode*head;

intordsit;

head=null;

if(n<=0)

{

returnnull;

}

else

{

head=(structnode*)malloc(sizeof(structnode));

head->data=*pre;

head->lchild=head->rchild=null;

ordsit=0;

while(ord[ordsit]!=*pre)

{

ordsit++;

}

head->lchild=create(pre+1,ord,ordsit);

head->rchild=create(pre+ordsi