189 8069 5689

数据结构实验报告3-创新互联

一.大代价路径

1.问题分析

我们提供的服务有：成都网站制作、网站设计、微信公众号开发、网站优化、网站认证、吉阳ssl等。为上千企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的吉阳网站制作公司

采用递归算法，当一个节点的子树存在时，返回其左右子树与该节点和的大值。

2.解题思路

二叉树存储结构

typedef struct BiTNode {
	int data;			  //结点元素 
	struct BiTNode* lchild;	  //左孩子指针 
	struct BiTNode* rchild;	  //右孩子指针 
}BiTNode, *BiTree;

创建二叉树

BiTree Create(){//输入-1代表该节点为空
	int data;
	int temp;
	BiTree T;
	scanf("%d",&data);
	temp=getchar();
	if(data==-1) {
		return NULL;
	}
	else{
		T=(BiTree)malloc(sizeof(BiTNode));
		T->data=data;
		printf("输入%d的左子树：",data);
		T->lchild=Create();
		printf("输入%d的右子树：",data);
		T->rchild=Create();
		return T; 
	}
}

递归求大代价路径

int Max(int a,int b){
	return (a>b?a:b);
} 
int RouteSumMax(BiTree T){
	if(T==NULL) return 0;
	else return Max(T->data+RouteSumMax(T->lchild),T->data+RouteSumMax(T->rchild));
}
void Route(BiTree T){
	if(T){
		printf("%d ",T->data);
		if(RouteSumMax(T->lchild)>=RouteSumMax(T->rchild)){
			Route(T->lchild);
		}
		else{
			Route(T->rchild);
		}
	}
}

3.程序出现的BUG

没有出现BUG

4.实验总结：对于有关二叉树的算法，采用递归可以很有效的解决问题

5.附录-源码

#include#include#includetypedef struct BiTNode {
	int data;			  //结点元素 
	struct BiTNode* lchild;	  //左孩子指针 
	struct BiTNode* rchild;	  //右孩子指针 
}BiTNode, *BiTree;	//二叉树结点与指向二叉树结点的指针
//创建二叉树
BiTree Create(){//输入-1代表该节点为空
	int data;
	int temp;
	BiTree T;
	scanf("%d",&data);
	temp=getchar();
	if(data==-1) {
		return NULL;
	}
	else{
		T=(BiTree)malloc(sizeof(BiTNode));
		T->data=data;
		printf("输入%d的左子树：",data);
		T->lchild=Create();
		printf("输入%d的右子树：",data);
		T->rchild=Create();
		return T; 
	}
}
//大代价路径
int Max(int a,int b){
	return (a>b?a:b);
} 
int RouteSumMax(BiTree T){
	if(T==NULL) return 0;
	else return Max(T->data+RouteSumMax(T->lchild),T->data+RouteSumMax(T->rchild));
}
void Route(BiTree T){
	if(T){
		printf("%d ",T->data);
		if(RouteSumMax(T->lchild)>=RouteSumMax(T->rchild)){
			Route(T->lchild);
		}
		else{
			Route(T->rchild);
		}
	}
}
int main(){
	BiTree T;
	T=Create();
	system("cls");
	printf("大代价路径：");
	Route(T);
	printf("\n"); 
	int mcp=RouteSumMax(T);
	printf("大路径代价：%d\n",mcp);
	return 0;
}

效果展示：

输入：

输出：

二、二叉树中数据域值大于50的节点

1.问题分析

如何计算结点所在层数：对二叉树进行层序遍历，当一层的节点全部出队后，队列中剩余结点是下一层的结点，此时队列中的结点个数就是下一层的结点个数，根据每一层结点个数来确定某个结点所在层数

2.解题思路

二叉树存储结构

typedef struct bitnode{
	int data;
	int number;//结点序号
	struct bitnode *lchild;
	struct bitnode *rchild;
}bitnode,*bitree;

队列

typedef struct queue{
	bitree a[MAX];
	int front;
	int rear;
	int num;
}queue,*queueptr;

队列基本操作（初始化，判空，入队出队，队列长度）

void Init(queueptr q){
	q->front=q->rear=0;
	q->num=0;
}
int queueEmpty(queue q){
	if(q.front==q.rear) return 1;
	else return 0;
}
void enqueue(queueptr q,bitree e){
	if(q->rear>=MAX) return ;
	q->a[q->rear]=e;
	q->rear++;
	q->num++;
}
void dequeue(queueptr q,bitree *e){
	*e=q->a[q->front];
	q->front++;
	q->num--;
}
int getLengh(queueptr q){
	return q->num;
}

存储大于50结点的数组

typedef struct node{
	int levelnum;//层数
	int val;//值
	int serial;//序号
}node;

创建二叉树

bitree Create(){
	int data;
	int temp;
	bitree T;
	scanf("%d",&data);
	temp=getchar();
	if(data==-1) {
		return NULL;
	}
	else{
		T=(bitree)malloc(sizeof(bitnode));
		T->data=data;
		printf("输入%d的左子树：",data);
		T->lchild=Create();
		printf("输入%d的右子树：",data);
		T->rchild=Create();
		return T; 
	}
}

为二叉树每个结点编号

void Serial(bitree t){
	if(!t) return;
	bitree p;
	queue Q;
	queueptr q=&Q;
	int k=1;
	Init(q);
	enqueue(q,t);
	while(!queueEmpty(Q)){
			dequeue(q,&p);
			p->number=k;
			k++;
			if(p->lchild) enqueue(q,p->lchild);
			if(p->rchild) enqueue(q,p->rchild);
		}
	
}

求data域大于50的结点

void GetMorethan50(bitree t){
	int total[100];
	node morethan[100]; 
	for(int j=0;j<100;j++){
		total[j]=0;
	}
	bitree p;
	queue Q;
	queueptr q=&Q;
	Init(q);
	enqueue(q,t);
	int level=1;
	int num=1;
	int i,j;
	for(j=0;j<100;j++){
		morethan[j].levelnum=0;
		morethan[j].serial=0;
		morethan[j].val=0;
	}
	j=0;
	while(!queueEmpty(Q)){
		for(i=1;i<=num;i++){
			dequeue(q,&p);
			if(p->data>50) {
				total[level]++;
				morethan[j].levelnum=level;
				morethan[j].serial=p->number;
				morethan[j].val=p->data;
				j++;
			}
			if(p->lchild) enqueue(q,p->lchild);
			if(p->rchild) enqueue(q,p->rchild);
		}
		num=getLengh(q);
		level++;
	}
	for(i=1;i

3.出现的BUG及解决方法

BUG：输出的序号不正确，如多输出一些序号且该序号为奇怪的数字

解决方法：原因是因为morethan数组未初始化，将数组初始化即可

4.实验总结：本实验本质上还是二叉树的层次遍历，通过本实验让我学会了确定某个结点在二叉树中的层数的方法

5.附录-源码

#include#include#define MAX 100
typedef struct bitnode{
	int data;
	int number;
	struct bitnode *lchild;
	struct bitnode *rchild;
}bitnode,*bitree;
typedef struct queue{
	bitree a[MAX];
	int front;
	int rear;
	int num;
}queue,*queueptr;
typedef struct node{
	int levelnum;
	int val;
	int serial;
}node;
//队列基本操作
void Init(queueptr q){
	q->front=q->rear=0;
	q->num=0;
}
int queueEmpty(queue q){
	if(q.front==q.rear) return 1;
	else return 0;
}
void enqueue(queueptr q,bitree e){
	if(q->rear>=MAX) return ;
	q->a[q->rear]=e;
	q->rear++;
	q->num++;
}
void dequeue(queueptr q,bitree *e){
	*e=q->a[q->front];
	q->front++;
	q->num--;
}
int getLengh(queueptr q){
	return q->num;
}
//创建二叉树
bitree Create(){
	int data;
	int temp;
	bitree T;
	scanf("%d",&data);
	temp=getchar();
	if(data==-1) {
		return NULL;
	}
	else{
		T=(bitree)malloc(sizeof(bitnode));
		T->data=data;
		printf("输入%d的左子树：",data);
		T->lchild=Create();
		printf("输入%d的右子树：",data);
		T->rchild=Create();
		return T; 
	}
}
void Serial(bitree t){
	if(!t) return;
	bitree p;
	queue Q;
	queueptr q=&Q;
	int k=1;
	Init(q);
	enqueue(q,t);
	while(!queueEmpty(Q)){
			dequeue(q,&p);
			p->number=k;
			k++;
			if(p->lchild) enqueue(q,p->lchild);
			if(p->rchild) enqueue(q,p->rchild);
		}
	
}
void GetMorethan50(bitree t){
	int total[100];
	node morethan[100]; 
	for(int j=0;j<100;j++){
		total[j]=0;
	}
	bitree p;
	queue Q;
	queueptr q=&Q;
	Init(q);
	enqueue(q,t);
	int level=1;
	int num=1;
	int i,j;
	for(j=0;j<100;j++){
		morethan[j].levelnum=0;
		morethan[j].serial=0;
		morethan[j].val=0;
	}
	j=0;
	while(!queueEmpty(Q)){
		for(i=1;i<=num;i++){
			dequeue(q,&p);
			if(p->data>50) {
				total[level]++;
				morethan[j].levelnum=level;
				morethan[j].serial=p->number;
				morethan[j].val=p->data;
				j++;
			}
			if(p->lchild) enqueue(q,p->lchild);
			if(p->rchild) enqueue(q,p->rchild);
		}
		num=getLengh(q);
		level++;
	}
	for(i=1;i

实验效果

输入：

输出：

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


网页标题：数据结构实验报告3-创新互联
网站URL：http://cdxtjz.cn/article/dicodp.html

其他资讯

联系我们

您好HELLO!
感谢您来到成都网站建设公司，若您有合作意向，请您为我们留言或使用以下方式联系我们， 我们将尽快给你回复，并为您提供真诚的设计服务，谢谢。
  • 电话：028- 86922220 18980695689
  • 商务合作邮箱：631063699@qq.com
  • 合作QQ： 532337155
  • 成都网站设计地址：成都市青羊区锣锅巷31号五金站写字楼6楼

小谭建站工作室

成都小谭网站建设公司拥有多年以上互联网从业经验的团队，始终保持务实的风格，以"帮助客户成功"为已任，专注于提供对客户有价值的服务。 我们已为众企业及上市公司提供专业的网站建设服务。我们不只是一家网站建设的网络公司；我们对营销、技术、管理都有自己独特见解，小谭建站采取“创意+综合+营销”一体化的方式为您提供更专业的服务！

小谭观点

相对传统的成都网站建设公司而言，小谭是互联网中的网站品牌策划，我们精于企业品牌与互联网相结合的整体战略服务。
我们始终认为，网站必须注入企业基因，真正使网站成为企业vi的一部分，让整个网站品牌策划体系变的深入而持久。
友情链接： 宜宾做网站   成都展柜设计   企业网站改版   手机网站制作   成都网站改版公司   成都广告制作   手提袋印刷制作   h5响应式网站   资阳做网站   西云机房   
© Copyright 2023 小谭建站工作室All Rights Reserved.  成都网站建设 / 成都网站建设 / 响应式网站建设 / 成都服务器租用