二叉树和结构

Question

我有一个二叉树，其中每个节点是一个结构。该结构有一个字符串和一个数字。我需要找到最大的数字。我试过

int search_max(link h){ 
    int max = 0; 
    if (h->item->acc == max) 
     return max; 
    if (h->item->acc > max){ 
     max = h->item->acc; 
     return search_max(h->l); 
     return search_max(h->r); 
    } 
    else { 
     return search_max(h->l); 
     return search_max(h->r); 
    } 
} 

但它给出了分段错误。 link h是树的头部的链接，并且acc不能为0.

Answer 1

基本上你正在做的前序遍历，但是最大的轨道是有问题的。对于每次递归，您应该检查并返回当前及其两个孩子中的最大节点。你也没有检查节点是否为NULL，这就是你看到崩溃的原因，因为树的叶子节点的子节点是空节点。试试这个：

int search_max(link h) { 
    if (h == NULL) return INT_MIN; 
    int max = h->item->acc; 

    int maxl = search_max(h->l); 
    if (max < maxl) 
     max = maxl; 

    int maxr = search_max(h->r); 
    if (max < maxr) 
     max = maxr; 

    return max; 
} 

Answer 2

您不能从连续两次函数中，函数将首先退出return。

还有没有检查树的末尾，在下一次迭代时h->l或h->r变为NULL或未初始化，具体取决于您如何创建它。这给出了分段错误。

Answer 3

#define MY_MAX(a,b) (a) > (b) ? (a) : (b) 
typedef struct link 
{ 
    int acc; 
    struct link *l, *r; 
} link_t; 

int search_max(link_t *h, int max) 
{ 
    if (h == NULL) return max; 
    if (h->acc > max) max = h->acc; 
    max = MY_MAX(search_max(h->l, max), search_max(h->r, max)); 
    return max; 
} 
int main(void) { 
    link_t root = { 1, 0, 0 }; 
    link_t l1 = { 2, 0, 0 }; 
    link_t l2 = { 3, 0, 0 }; 

    link_t l11 = { 5, 0, 0 }; 
    link_t l12 = { 1, 0, 0 }; 
    link_t l21 = { 9, 0, 0 }; 
    link_t l211 = { 13, 0, 0 }; 
    link_t l212 = { 0, 0, 0 }; 
    root.l = &l1; 
    root.r = &l2; 
    l1.l = &l11; 
    l1.r = &l12; 
    l2.l = &l21; 
    l21.l = &l211; 
    l21.r = &l212; 
    printf("max [%d]", search_max(&root,0)); 

    return 0; 
} 

https://ideone.com/PKbM0M

Answer 4

你需要添加另一个参数currmax的功能。这将存储最大值的当前值以进行比较。

int search_max(link h, int currmax){ 
    int max; 
    if (h == NULL) 
     return currmax; 
    else if (h->item->acc > currmax){ 
     currmax = h->item->acc; 

    max = search_max(h->l,currmax); 
    if (max > currmax) 
     currmax = max; 

    max = search_max(h->r, currmax); 
    if (max > currmax) 
     currmax = max; 

    return currmax; 
}