数据结构实验报告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://wjwzjz.com/article/dicodp.html

新网创想网站建设，新征程启航

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

其他资讯