Функция двоичного дерева (не поиск) max

Question

Я получаю ошибку сегментации с моим кодом, и я не уверен, почему. Я пытаюсь найти максимальное значение в обычном двоичном дереве, которое не упорядочено.

tnode<int> *maxT(tnode<int> *t) 
{ 
    if (t == NULL) return NULL; 

    tnode<int> *left = maxT(t->left); 
    tnode<int> *right = maxT(t->right); 

    if (left->nodeValue > right->nodeValue) 
    { 
     return maxT(left); 
    } 
    if (left->nodeValue < right->nodeValue) 
    { 
     return maxT(right); 
    } 

} 

Answer 1

tnode<int> *maxT(tnode<int> *t) 
{ 
    if (t->right == NULL && t->left == NULL) //leaf node 
    return t->nodeValue; 

    else if (t->right == NULL) //no right subtree 
    return MAX(t->nodeValue, maxT(t->left)) 

    else if (t->left == NULL) //no left subtree 
    return MAX(t->nodeValue, maxT(t->right)) 

    else 
    return MAX(maxT(t->right), maxT(t->left)); 
} 

В вашем случае, что произойдет, если узел не имеет правый или левый ребенок. Затем либо node-> right == NULL или node-> left == NULL. Однако вы пытаетесь получить доступ к left-> nodeValue или right-> nodeValue.

Answer 2

Основы алгоритма довольно прямолинейны. Поскольку дерево является неупорядоченным, все узлы должны быть посещены, со следующими предпосылками:

• Нулем результатов указателя узла в нуле в качестве ответа.
• Еще один узел без детей приводит к текущему узлу
• Иной результат - это максимальный размер узла по сравнению с максимальным количеством его детей.

Учитывая, что, я уверен, что это то, что вы пытаетесь сделать:

template<typename T> 
tnode<T>* maxT(const tnode<T>* t) 
{ 
    if (!t) 
     return nullptr; 

    tnode<T>* lmax = maxT(t->left); 
    tnode<T>* rmax = maxT(t->right); 
    tnode<T>* cmax = (lmax && rmax) 
        ? ((rmax->nodeValue < lmax->nodeValue ? lmax : rmax)) 
        : (lmax ? lmax : rmax); 
    return (!cmax || (cmax->nodeValue < t->nodeValue) ? t : cmax); 
}