二叉树和结构

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是树头的link，acc不能为0。

Answer 1

您不能从一个函数连续两次 return，函数首先会退出 return。

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

Answer 2

#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 3

基本上你是先序遍历，但是最大值的轨迹是有问题的。对于每个递归，您应该检查 return 当前及其两个子节点中的最大节点。此外，您没有检查节点是否为 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 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;
}

二叉树和结构

Binary trees and struct

c

binary-tree

struct