那我试图绕到我的头二叉树提取码

Question

我已经预先写好的代码：

int maxExtract(node **tree) 
{ 
    node *prev = NULL; 
    node *curr = *tree; 
    int ret; 

    if(curr == NULL) 
    { 
     printf("Tree is empty!\n"); 
     exit(-1); 
    } 
    while(curr->right != NULL) 
    { 
     prev = curr; 
     curr = curr->right; 
    } 

    ret = curr->data; 
    if(prev != NULL) 
     prev->right = curr->left; 
    else if(curr == *tree) 
     *tree = curr->left; 
    free(curr); 
    return ret; 
} 

我明白，除了else if (curr == *tree)条件的一切。我认为这是说如果最大节点最终成为根。但是，如果想在提取旧的根后将树的右侧和左侧连接到新的根，那么是否需要在else之后更改更多的连接？

Answer 1

我认为这是说如果最大节点最终成为根。

也就是说正是这意味着什么，如果是这样的话，那么就可以什么该节点的右边，因为，如果有，最高会在某处（右）子树，不在根。

因此，让我们考虑的树根源在哪里是最大（和A1/A2是任意的子树，包括空的）：

 MAX 
    /
    x 
/\ 
A1 A2 

为了获取最大价值，你想留下什么用很简单：

x 
/\ 
A1 A2 

所以，你要执行的操作是使x树的新根 - 这是在你的代码行完成：

*tree = curr->left; 

---

我可能会写略有不同，以明确地处理不同的情况下，而不是依赖于事情发生，或者根据代码的中间各项决定没有发生。我的意思是：

int maxExtract (node **tree) { 
    // Handle empty tree as error. 

    if (*tree == NULL) { 
     printf ("Tree is empty!\n"); 
     exit (-1); 
    } 

    // Handle root is max, i.e., has no right subtree. 

    if ((*tree)->right == NULL) { 
     node *nodeToDelete = *tree;  // Save root for deletion. 
     int retVal = nodeToDelete->data; // Get data to return. 
     *tree = nodeToDelete->left;  // Set new root. 
     free (nodeToDelete);    // Delete old root. 
     return retVal;     // Return old root value. 
    } 

    // Locate max and its previous. 

    node *prev = *tree; 
    node *curr = (*tree)->right; 
    while (curr->right != NULL) { 
     prev = curr; 
     curr = curr->right; 
    } 

    // Max has no right sub-tree but it MAY have a left one 
    // which needs to be transferred as-is to the right of prev. 

    int retVal = curr->data; // Get data to return. 
    node *nodeToDelete = curr; // Save root for deletion. 
    prev->right = curr->left; // Transfer left sub-tree (or null). 
    free (nodeToDelete);  // Delete old max. 
    return retVal;    // Return old max value.