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