c - 从二叉树中获取最大值

Question

现在我是二叉树，我想从中获取最大值。考虑到它如何同时具有 string 和 int 值，它按字母顺序排序。所有插入、搜索、删除等操作都正常。现在我们只需要知道我的树就在这里。

typedef struct node 
{
    char *name;
    int count;
    struct node *l, *r; 
}*link;

我如何创建一个简单的函数来查找树中最高的 count。就像我可以在树中有 20 个节点并假设最高 count 是 10 并且有 3 个节点具有最高 count。最高 count 有多少并不重要，我只希望函数返回 10。类似这样的函数。

int maxValue(link head)
{
    //the help i need with
}

我在网上查找并尝试了一些示例，例如 inorder 和所有不同的函数，但其​​中大多数只是按顺序放置从左节点到最右节点的所有值，所以它并没有真正帮助我找到最大数量在树中，因为我的不是从最小到最大的数字组织的。

Answer 1

这个想法是首先计算给定节点的子树的最大值，maxLeft 和 maxRight，然后返回 max(currVal, maxLeft , maxRight)，其中currVal为当前节点中的值。

下面是您如何在代码中直接表达这一点:

int maxValue(link head)
{
    assert(head != NULL);
    int currVal = head->count;
    if (head->l != NULL) // compute max of the left subtree
        currVal = max(currVal, maxValue(head->l));
    if (head->r != NULL) // compute max of the right subtree
        currVal = max(currVal, maxValue(head->r));
    return currVal;
}

例如，max 可以是一个简单的宏

#define max(x, y) (x) > (y) ? (x) : (y)