計算節點值的最大總和並計算給出總和的特定路徑[C]

-2

好吧，我在這裏有一個有趣的問題。我得到的任務說我應該計算給定樹從根到葉的最大總和。在這種情況下，這是14.那麼，問題是，我還需要計算該確切路徑的長度，並稍微返回它，因爲我需要將總和除以該路徑長度。它確實聽起來很複雜，起初我認爲這很容易，但是我不能找到一種方法來通過特定路徑對節點進行計數。也許整個功能count()錯誤地組裝，因爲它沒有留下任何我需要完成的特定任務的空間。如果有更多的問題，請隨時寫下來，我需要這個答案。謝謝！計算節點值的最大總和並計算給出總和的特定路徑[C]

#include <stdio.h> 
#include <stdlib.h> 

struct tree{ 
    int i; 
    struct tree *left; 
    struct tree *right; 
}; 
int count(struct tree *root); 
int max(int,int); 
int main() 
{ 
    struct tree *p=NULL, *q=NULL, *r=NULL, *t=NULL; 

    //1 
    p=(struct tree *)malloc(sizeof(struct tree)); 
    if(p==NULL) exit(1); 
    p->i=1; 
    p->left=NULL; 
    p->right=NULL; 

    //2 
    q=(struct tree *)malloc(sizeof(struct tree)); 
    if(q==NULL) exit(1); 
    q->i=2; 
    q->left=NULL; 
    q->right=NULL; 
    p->left=q; 

    //3 
    r=(struct tree *)malloc(sizeof(struct tree)); 
    if(r==NULL) exit(1); 
    r->i=3; 
    r->left=NULL; 
    r->right=NULL; 
    p->right=r; 

    t=q; 

    //4 
    q=(struct tree *)malloc(sizeof(struct tree)); 
    if(q==NULL) exit(1); 
    q->i=4; 
    q->left=NULL; 
    q->right=NULL; 
    t->left=q; 

    //5 
    q=(struct tree *)malloc(sizeof(struct tree)); 
    if(q==NULL) exit(1); 
    q->i=5; 
    q->left=NULL; 
    q->right=NULL; 
    t->right=q; 

    t=q; 

    //6 
    q=(struct tree *)malloc(sizeof(struct tree)); 
    if(q==NULL) exit(1); 
    q->i=6; 
    q->left=NULL; 
    q->right=NULL; 
    t->left=q; 

    //7 
    q=(struct tree *)malloc(sizeof(struct tree)); 
    if(q==NULL) exit(1); 
    q->i=7; 
    q->left=NULL; 
    q->right=NULL; 
    r->right=q; 
    printf("The sum is %d!",count(p)); 
} 
int count(struct tree *root){ 
    if(root->left!=NULL && root->right!=NULL){ 
     return root->i+max(count(root->left),count(root->right)); 
    } 
    else if(root->left==NULL && root->right!=NULL){ 
     return root->i+count(root->right); 
    } 
    else if(root->left!=NULL && root->right==NULL){ 
     return root->i+count(root->left); 
    } 
    else{ 
     return root->i; 
    } 
} 
int max(int a, int b){ 
    if(a>b){ 
     return a; 
    } 
    else{ 
     return b; 
    } 
}

來源

2017-01-03 Slavko Kovačević

「它確實聽起來很複雜」 - 它也沒有聽起來那樣，也不是。但是，我們不是「做我的作業」網站。見[問]。你的具體**問題是什麼？你有什麼嘗試？ – Olaf

我嘗試了一切，但它不會工作，我明白爲什麼它不 - 我找不到解決方案。問題很簡單 - 這個函數給了我從根到葉的最高總和，但我不知道如何計算這些特定的節點。 –

爲什麼不傳遞一個額外的參數'int * pathlen'到'count（）'來保存這個（子）路徑的長度？當你降下樹枝並且離開時，你將它設置爲1.當你向上爬回時，你從副路徑中取出透鏡並增加1. – Gerhardh

我不想改變一切，但只是調整你的代碼...

typedef struct { 
    int len; 
    int sum; 
} path_t; 

path_t count(struct tree *root) { 
    path_t a = { .len = 0, .sum = 0}; 
    path_t b = { .len = 0, .sum = 0}; 
    path_t ret; 

    if (root == NULL) 
     return a; // empty sub-tree 

    a = count(root->left); 
    b = count(root->right); 

    if (a.sum > b.sum) { 
     ret.sum = a.sum: 
     ret.len = a.len; 
    } else { 
     ret.sum = b.sum: 
     ret.len = b.len; 
    } 
    ret.sum += root->i; 
    ret.len ++; 
    return ret; 
}

可能需要照顧的一些細節：初始化的.sum 0可能是不夠的，如果樹可以持有負數。我只需要b。您可能需要根據路徑長度來決定，或者始終選擇a而不是b。

來源

2017-01-03 13:38:34 Gerhardh

計算節點值的最大總和並計算給出總和的特定路徑[C]

回答

相關問題