數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告3-創(chuàng)新互聯(lián)

一.大代價(jià)路徑

1.問題分析

我們提供的服務(wù)有：成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、吉陽ssl等。為上千企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的吉陽網(wǎng)站制作公司

采用遞歸算法，當(dāng)一個(gè)節(jié)點(diǎn)的子樹存在時(shí)，返回其左右子樹與該節(jié)點(diǎn)和的大值。

2.解題思路

二叉樹存儲結(jié)構(gòu)

typedef struct BiTNode {
	int data;			  //結(jié)點(diǎn)元素 
	struct BiTNode* lchild;	  //左孩子指針 
	struct BiTNode* rchild;	  //右孩子指針 
}BiTNode, *BiTree;	

創(chuàng)建二叉樹

BiTree Create(){//輸入-1代表該節(jié)點(diǎn)為空
	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; 
	}
}

遞歸求大代價(jià)路徑

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.程序出現(xiàn)的BUG

沒有出現(xiàn)BUG

4.實(shí)驗(yàn)總結(jié)：對于有關(guān)二叉樹的算法，采用遞歸可以很有效的解決問題

5.附錄-源碼

#include#include#includetypedef struct BiTNode {
	int data;			  //結(jié)點(diǎn)元素 
	struct BiTNode* lchild;	  //左孩子指針 
	struct BiTNode* rchild;	  //右孩子指針 
}BiTNode, *BiTree;	//二叉樹結(jié)點(diǎn)與指向二叉樹結(jié)點(diǎn)的指針
//創(chuàng)建二叉樹
BiTree Create(){//輸入-1代表該節(jié)點(diǎn)為空
	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; 
	}
}
//大代價(jià)路徑
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("大代價(jià)路徑：");
	Route(T);
	printf("\n"); 
	int mcp=RouteSumMax(T);
	printf("大路徑代價(jià)：%d\n",mcp);
	return 0;
}

效果展示：

輸入：

輸出：

二、二叉樹中數(shù)據(jù)域值大于50的節(jié)點(diǎn)

1.問題分析

如何計(jì)算結(jié)點(diǎn)所在層數(shù)：對二叉樹進(jìn)行層序遍歷，當(dāng)一層的節(jié)點(diǎn)全部出隊(duì)后，隊(duì)列中剩余結(jié)點(diǎn)是下一層的結(jié)點(diǎn)，此時(shí)隊(duì)列中的結(jié)點(diǎn)個(gè)數(shù)就是下一層的結(jié)點(diǎn)個(gè)數(shù)，根據(jù)每一層結(jié)點(diǎn)個(gè)數(shù)來確定某個(gè)結(jié)點(diǎn)所在層數(shù)

2.解題思路

二叉樹存儲結(jié)構(gòu)

typedef struct bitnode{
	int data;
	int number;//結(jié)點(diǎn)序號
	struct bitnode *lchild;
	struct bitnode *rchild;
}bitnode,*bitree;

隊(duì)列

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

隊(duì)列基本操作（初始化，判空，入隊(duì)出隊(duì)，隊(duì)列長度）

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結(jié)點(diǎn)的數(shù)組

typedef struct node{
	int levelnum;//層數(shù)
	int val;//值
	int serial;//序號
}node;

創(chuàng)建二叉樹

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; 
	}
}

為二叉樹每個(gè)結(jié)點(diǎn)編號

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的結(jié)點(diǎn)

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.出現(xiàn)的BUG及解決方法

BUG：輸出的序號不正確，如多輸出一些序號且該序號為奇怪的數(shù)字

解決方法：原因是因?yàn)閙orethan數(shù)組未初始化，將數(shù)組初始化即可

4.實(shí)驗(yàn)總結(jié)：本實(shí)驗(yàn)本質(zhì)上還是二叉樹的層次遍歷，通過本實(shí)驗(yàn)讓我學(xué)會了確定某個(gè)結(jié)點(diǎn)在二叉樹中的層數(shù)的方法

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;
//隊(duì)列基本操作
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;
}
//創(chuàng)建二叉樹
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

實(shí)驗(yàn)效果

輸入：

輸出：

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告3-創(chuàng)新互聯(lián)
文章分享：http://bm7419.com/article18/dicodp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動網(wǎng)站建設(shè)、定制網(wǎng)站、標(biāo)簽優(yōu)化、搜索引擎優(yōu)化、網(wǎng)站排名、網(wǎng)站設(shè)計(jì)公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)