一.大代价路径
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://cdkjz.cn/article/dicodp.html
