Получение максимального значения из двоичного дерева

Question

Прямо сейчас я бинарное дерево, и я хочу получить максимальное значение из него. Учитывая, как он имеет как значения строки, так и значения int, он упорядочивается по алфавиту. Все исправляет все вставки, поиск, удаление и т. Д. На данный момент все, что нам нужно знать, это то, что здесь у меня есть дерево.

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

Как я могу сделать простую функцию, которая находит то, что является самым высоким count в дереве. Как и я могу иметь 20 узлов в дереве и предположим, что самый высокий count равен 10, и есть 3 узла с самым высоким count. Неважно, сколько из них имеет 10 самых высоких count, я просто хочу, чтобы функция возвращалась. 10. Функция вроде.

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

Я посмотрел в Интернете и попробовал некоторые примеры, как в заказовМои и все разные Funtions, но большинство из них просто расставил все значения из левого узла наиболее правого в порядке, так что действительно не поможет мне найти максимальное число в дереве, потому что моя не организована от минимального до наибольшего числа.

Answer 1

Рекурсия - ваш друг в этом случае. Ваша функция сравнивает значение самого себя, максимум левой стороны и максимум правой стороны и возвращает наибольшее значение.

int maxValue(link head) 
{ 
    if(head == NULL){ 
     return -1; 
    } 
    int me = head->count; 
    int l = maxValue(head->l); 
    int r = maxValue(head->r); 
    if(me >= l && me >= r) { 
     return me; 
    } else if(l >= me && l >= r){ 
     return l; 
    } else { 
     return r; 
    } 
} 

Примечание

Этот код не так вообще, как можно было бы написать ее. Он будет работать только так, как ожидалось, если count всегда больше нуля в дереве и если функция не вызывается в NULL-объекте в начале, с тех пор будет возвращен -1. Лучше использовать решение @blazs на практике.

Answer 2

Идея заключается в том, чтобы сначала вычислить максимальные значения поддеревьев, 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) 

Answer 3

Чтобы найти максимальное значение в дереве, код не может принять преимущество в алфавитном порядке. Вместо этого нужно пройти все дерево. Это включает в себя проверку текущего узла, а затем максимум каждого из двух детей, слева и справа.

Классическое усовершенствование ходьбы по двоичному дереву состоит в том, чтобы только отменить на одной ноге (например, левую сторону) и петли на другом (справа). Такое разворачивание цикла иногда может быть идентифицировано интеллектуальным компилятором, который рекурсирует на обеих ногах. Здесь, ниже, это делается явно.

Этот код возвращает INT_MIN, если оригинал head == NULL.

int maxValue(link head) { 
    int max = INT_MIN; 
    while (head) { 
    if (head.count > max) { 
     max = head.count; 
    } 
    int left_max = maxValue(head.left); 
    if (left_max > max) { 
     max = left_max; 
    } 
    head = head.right; 
    } 
    return max; 
} 

Стиль: Я бы предпочел видеть ЬурейеЕ без * как в ниже.

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