二叉树基本操作实验报告Word格式.docx
- 文档编号:4475664
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:11
- 大小:64.13KB
二叉树基本操作实验报告Word格式.docx
《二叉树基本操作实验报告Word格式.docx》由会员分享,可在线阅读,更多相关《二叉树基本操作实验报告Word格式.docx(11页珍藏版)》请在冰点文库上搜索。
以括号表示法输出一棵二叉树。
3>
查找结点FindNode(*b,x):
在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针。
4>
求高度BTNodeDepth(*b):
求二叉树b的高度。
若二叉树为空,则其高度为0;
否则,其高度等于左子树与右子树中的最大高度加l。
5>
求二叉树的结点个数NodesCount(BTNode*b)
6>
先序遍历的递归算法:
voidPreOrder(BTNode*b)
7>
中序遍历的递归算法:
voidInOrder(BTNode*b)
8>
后序遍历递归算法:
voidPostOrder(BTNode*b)
9>
层次遍历算法voidLevelOrder(BTNode*b)
2、基本要求
实现以上9个函数。
主函数中实现以下功能:
创建下图中的树b
输出二叉树b
找到’H’节点,输出其左右孩子值
输出b的高度
输出b的节点个数
输出b的四种遍历顺序
3、程序编写
上图转化为二叉树括号表示法为A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
程序:
#include<
stdio.h>
malloc.h>
#defineMaxSize100
typedefcharElemType;
typedefstructnode
{
ElemTypedata;
/*数据元素*/
structnode*lchild;
/*指向左孩子*/
structnode*rchild;
/*指向右孩子*/
}BTNode;
voidCreateBTNode(BTNode*&
b,char*str);
//创建
BTNode*FindNode(BTNode*b,ElemTypex);
//查找节点
intBTNodeHeight(BTNode*b);
//求高度
voidDispBTNode(BTNode*b);
//输出
intNodesCount(BTNode*b);
//二叉树的结点个数
voidPreOrder(BTNode*b);
//先序遍历递归
voidInOrder(BTNode*b);
//中序遍历递归
voidPostOrder(BTNode*b);
//后序遍历递归
voidLevelOrder(BTNode*b);
//层次遍历
b,char*str){
BTNode*St[MaxSize],*p=NULL;
inttop=-1,k,j=0;
charch;
b=NULL;
ch=str[j];
while(ch!
='
\0'
){
switch(ch){
case'
('
:
top++;
St[top]=p;
k=1;
break;
)'
top--;
'
k=2;
default:
p=(BTNode*)malloc(sizeof(BTNode));
p->
data=ch;
p->
lchild=p->
rchild=NULL;
if(b==NULL)
b=p;
else{
switch(k){
case1:
St[top]->
lchild=p;
case2:
rchild=p;
}
}
}
j++;
ch=str[j];
}
}
//输出
voidDispBTNode(BTNode*b){
if(b!
=NULL){
printf("
%c"
b->
data);
if(b->
lchild!
=NULL||b->
rchild!
printf("
("
);
DispBTNode(b->
lchild);
if(b->
=NULL)
printf("
"
rchild);
)"
BTNode*FindNode(BTNode*b,ElemTypex){
BTNode*p;
if(b==NULL)
returnb;
elseif(b->
data==x)
else{
p=FindNode(b->
lchild,x);
if(p!
returnp;
else
returnFindNode(b->
rchild,x);
//求高度
intBTNodeHeight(BTNode*b){
intlchildh,rchildh;
if(b==NULL)
return(0);
else{
lchildh=BTNodeHeight(b->
rchildh=BTNodeHeight(b->
return(lchildh>
rchildh)?
(lchildh+1):
(rchildh+1);
//二叉树的结点个数
intNodesCount(BTNode*b){
return0;
returnNodesCount(b->
lchild)+NodesCount(b->
rchild)+1;
//先序遍历递归
voidPreOrder(BTNode*b){
PreOrder(b->
//中序遍历递归
voidInOrder(BTNode*b){
InOrder(b->
//后序遍历递归
voidPostOrder(BTNode*b){
PostOrder(b->
//层次遍历
voidLevelOrder(BTNode*b){
BTNode*p;
BTNode*qu[MaxSize];
intfront,rear;
front=rear=-1;
rear++;
qu[rear]=b;
while(front!
=rear){
front=(front+1)%MaxSize;
p=qu[front];
p->
if(p->
rear=(rear+1)%MaxSize;
qu[rear]=p->
lchild;
rchild;
voidmain()
BTNode*b,*p,*lp,*rp;
charstr[]="
A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"
;
//根据树形图改写成的
//二叉树括号表示法的字符串*str
//charstr[100];
scanf("
%s"
&
str);
//自行输入括号表示的二叉树
CreateBTNode(b,str);
//创建树b
printf("
\n"
输出二叉树:
"
//输出二叉树b
DispBTNode(b);
'
H'
结点:
//找到'
节点,输出其左右孩子值
p=FindNode(b,'
if(p!
=NULL){
printf("
左孩子节点的值"
lchild->
printf("
右孩子节点的值"
rchild->
//此处输出p的左右孩子节点的值
二叉树b的深度:
%d\n"
BTNodeHeight(b));
//输出b的高度
二叉树b的结点个数:
NodesCount(b));
//输出b的节点个数
先序遍历序列:
//输出b的四种遍历顺序
算法:
PreOrder(b);
中序遍历序列:
InOrder(b);
后序遍历序列:
PostOrder(b);
层次遍历序列:
LevelOrder(b);
四、实验心得与小结
通过本次实验,我熟悉二叉树的基本知识内容,对课本的知识有了更加深刻的理解与掌握掌握。
通过查阅资料以及XX一些前人的程序设计,我学到了很多原来在课堂上掌握不到的东西,这次是我的第一次完成了二叉树的实现以及实际应用。
加深了对二叉树的理解,。
本次实验还运用到了递归的使用,是非常新的体验,原来都是停留在概念上的运用递归处理,这次运用到了实际的实验编程中,受益匪浅。
这次实验,让我明白了一个道理,实践出真知,只有通过自己的双手实践,才能更好的理解知识与运用。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 基本 操作 实验 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)