二叉樹（不是搜索）最大功能

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); 
}