实验四 二叉树的基本操作
实验课程名:数据结构
专业班级: 09计科一班 学号: ** 姓名: *****
实验时间:12.2—12.9 实验地点: k4--206 指导教师: 祁文青
一、实验目的
1、进一步掌握指针变量、动态变量的含义。
2、掌握二叉树的结构特性,以及各种存储结构的特点和适用范围。
3、掌握用指针类型描述、访问和处理二叉树的运算。
二、实验内容
1、以二叉链
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
作存储结构,试编程实现前序、中序、后序及层次顺序遍历二叉树的算法。
#include
#include
#include
#include
#define ClearBiTree DestroyBiTree
typedef struct BiTNode
{
int data;
BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void visit(int e)
{
printf("%d ",e);
}
void InitBiTree(BiTree &T)
{
T=NULL;
}
void CreateBiTree(BiTree &T)
{
int number;
scanf("%d",&number);
if(number==0)
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)
exit(OVERFLOW);
T->data=number;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void DestroyBiTree(BiTree &T)
{
if(T)
{
DestroyBiTree(T->lchild);
DestroyBiTree(T->rchild);
T=NULL;
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{
if(T)
{
Visit(T->data);
PreOrderTraverse(T->lchild,Visit);
PreOrderTraverse(T->rchild,Visit);
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{
if(T)
{
InOrderTraverse(T->lchild,Visit);
Visit(T->data);
InOrderTraverse(T->rchild,Visit);
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{
if(T)
{
PostOrderTraverse(T->lchild,Visit);
PostOrderTraverse(T->rchild,Visit);
Visit(T->data);
}
}
void main()
{
BiTree T;
InitBiTree(T);
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0\n");
CreateBiTree(T);
printf("先序递归遍历二叉树:\n");
PreOrderTraverse(T,visit);
printf("\n中序递归遍历二叉树:\n");
InOrderTraverse(T,visit);
printf("\n后序递归遍历二叉树:\n");
PostOrderTraverse(T,visit);
}
运行结果
2、以二叉链表作存储结构,试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法。
#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"
typedef int ElemType;
typedef struct BTNode
{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;
void CreateBiTree(BiTree &T)
{
int ch;
cin>>ch;
if(ch==0)
T=NULL;
else
{
if(!(T=(BTNode *)malloc(sizeof(BTNode))))
cout<<"malloc fail!";
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
int BTDepth(BiTree T)
{
if(!T)
return 0;
else
{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2)
return h1+1;
else
return h2+1;
}
}
int Leaf(BiTree T)
{
if(!T)
return 0;
else if(!T->lchild&&!T->rchild)
return 1;
else
return(Leaf(T->lchild)+Leaf(T->rchild));
}
int NodeCount(BiTree T)
{
if(!T)
return 0;
else
return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
int onesoncount(BiTree T)
{
if (T==NULL)
return(0);
else if ((T->lchild==NULL && T->rchild!=NULL) || (T->lchild!=NULL && T->rchild==NULL))
return(onesoncount(T->lchild)+onesoncount(T->rchild)+1);
else
return(onesoncount(T->lchild)+onesoncount(T->rchild));
}
int twosoncount(BiTree T)
{
if (T==NULL)
return 0;
else if (T->lchild==NULL || T->rchild==NULL)
return(twosoncount(T->lchild)+twosoncount(T->rchild));
else if (T->lchild!=NULL && T->rchild!=NULL)
return(twosoncount(T->lchild)+twosoncount(T->rchild)+1);
return 1;
}
void main()
{
BiTree T;
T=NULL;
cout<<"按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0"<data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void NRPreOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{
cout<data;
stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top]; p=p->rchild; }
} } }
int NRInOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{
stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top];cout<data; p=p->rchild; }
}
}
return 0;
}
typedef struct
{
BiTree ptr;
int tag;
}stacknode;
void NRPostOrder(BiTree bt)
{
stacknode s[MaxLength],x;
BiTree p=bt;
int top;
if(bt!=NULL){
top=0;p=bt;
do
{
while (p!=NULL)
{
s[top].ptr = p;
s[top].tag = 1;
top++;
p=p->lchild;
}
while (top>0 && s[top-1].tag==2)
{
x = s[--top];
p = x.ptr;
cout<data;
}
if (top>0)
{
s[top-1].tag =2;
p=s[top-1].ptr->rchild;
}
}while (top>0);}
}
void main()
{
BiTree T;
T=NULL;
CreateBiTree(T);
cout<<"先序遍历:";
NRPreOrder(T);
cout<
本文档为【湖北理工(黄石理工)数据结构实验 实验四 二叉树的基本操作】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。