C使用遞歸錯誤的AVL樹搜索

Question

我無法搜索節點中最大的通用向量，並返回該節點的地址。我認爲我的邏輯是合理的，但它沒有任何跡象表明爲什麼會一直失敗。任何幫助，將不勝感激。

struct vector 
{   
    int size; 
    int capacity; 
    Item* data; 
}; 
typedef struct vector GenericVector;  
typedef struct Node Tree; 

struct Node 
{  
    Tree* left; 
    Tree* right; 
    GenericVector* data; 
    int height; 
}; 

void* find_largest_bin(void* root) 
{  
    Tree* pRoot = (Tree*)root; 
    if (pRoot == NULL) 
     return NULL; 
    Tree* left = pRoot->left; 
    Tree* right = pRoot->right; 

    left= find_largest_bin(pRoot->left); 
    right = find_largest_bin(pRoot->right); 

    //if there is only one leg 
    if (right == NULL && left->data->size > pRoot->data->size) 
     return left; 
    else if (right == NULL && left->data->size < pRoot->data->size) 
     return pRoot; 
    else if (left == NULL && right->data->size > pRoot->data->size) 
     return right; 
    else if (left == NULL && right->data->size < pRoot->data->size) 
     return pRoot; 
    //if there are two legs 
    else if (left->data->size > pRoot->data->size && left->data->size > right->data->size) 
     return left; 
    else if (right->data->size > pRoot->data->size && right->data->size > left->data->size) 
     return right; 
    else 
     return pRoot; 
} 

Answer 1

當這第一個條件發生：

if (right == NULL && left->data->size > pRoot->data->size) 
     return left; 

這可能是左邊也爲空。這意味着left-> data會解引用空指針，並可能導致崩潰。發生這種情況是因爲你正在檢查右邊是NULL，然後假設左邊沒有。不要假設。相反，檢查左邊是不是空的，然後測試左邊，檢查右邊不是空的然後測試正確。

另外，一般來說，用許多返回語句創建函數是一個壞習慣。通常（但並非總是），最好允許條件落入最終的return語句。這有助於簡化邏輯和可讀性。通過在每個子句中放置一個return語句，您迫使自己爲每個可能的（左，右）x（空，更大，更小）排列寫入條件，而不是通過單獨處理每個個案來構造結果。

例如，嘗試使用此版本，該版本的操作次數較少，可以說是更具可讀性。請注意，我們測試left不是null，然後查找更大的左邊;我們檢查正確的不是null，然後尋找一個更大的權利。無論我們的largest_so_far變量中剩下的是最大的，所以我們將其返回。因爲我們單獨處理每個節點（這個，左邊，右邊），並且我們將largest_so_far累加到一個變量中，所以我們只需處理每個案例一次。

Node* find_largest_bin(Node* curNode) 
{  
    if (curNode == NULL) { return NULL; } 

    Node* largest_so_far = curNode; 

    // look for a larger node on the lefthand side 
    Node* left_largest = find_largest_bin(curNode->left);  
    if (left_largest != NULL && 
      left_largest->data->size > largest_so_far->data->size) { 
     largest_so_far = left_largest; 
    } 

    // look for a larger node on the righthand side 
    Node* right_largest = find_largest_bin(curNode->right); 
    if (right_largest != NULL && 
      right_largest->data->size > largest_so_far->data->size) { 
     largest_so_far = right_largest; 
    } 

    return largest_so_far; 
}