c-有可能优化这个递归函数吗

Question

我正在努力了解这是否是删除树中节点的最快方法。

struct node *deleteNode(struct node *root, char *key)
{
// base case
if (root == NULL)
return root;
// If the key to be deleted
// is smaller than the root's
// key, then it lies in left subtree
if (strcmp(key, root->key) < 0)
root->left = deleteNode(root->left, key);
// If the key to be deleted
// is greater than the root's
// key, then it lies in right subtree
else if (strcmp(key, root->key) > 0)
root->right = deleteNode(root->right, key);
// if key is same as root's key,
// then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
// node with two children:
// Get the inorder successor
// (smallest in the right subtree)
struct node *temp = minValueNode(root->right);
// Copy the inorder
// successor's content to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}

它获取一棵树和一个单词，并从树中删除节点。我想了解的是，我什么时候才能达到"；完美的"；优化级别？我在这个代码上做了很多工作，我认为这是最好的方法。我还可以查找什么？

Answer 1

首先，deleteNode的初始参数是根，但实际上应该只将其命名为node或subtree。

您应该free是关键，strdup是节点创建的关键。

在该节点上查找值时，无法立即删除该节点。要么看左边的最大值(left-rights-rightnull节点(，要么看右边的最小值(right-lefts-leftnull节点(。

您有三个指针，根、xnull节点和xnull的另一个子树。一种删除形式被称为旋转指针。

请注意，您确实复制了密钥。在C++中，这可能比指针复制成本更高。在C语言中，复制一个指针或最多复制一个结构同样代价高昂，尽管我更喜欢指针复制。

然后你再次下降分支，这样可以优化一点；至少更直接。

struct node *deleteNode(struct node *tree, char *key)
{
// base case
if (tree == NULL)
return tree;
// If the key to be deleted
// is smaller than the tree's
// key, then it lies in left subtree
int cmp = strcmp(key, tree->key); // Thanks to RachidK
if (cmp < 0)
tree->left = deleteNode(tree->left, key);
// If the key to be deleted
// is greater than the tree's
// key, then it lies in right subtree
else if (cmp > 0)
tree->right = deleteNode(tree->right, key);
// if key is same as tree's key,
// then This is the node
// to be deleted
else
{
struct node *result;
// node with only one child or no child
if (tree->left == NULL)
{
result = tree->right;
}
else if (tree->right == NULL)
{
result = tree->left;
}
else
{
// node with two children:
// Get the inorder successor
// (smallest in the right subtree)
struct node **successor = &(tree->right);
while ((*successor)->left != NULL)
{
successor = &(*successor)->left;
}
// rotate pointers:
result = *successor;
result->left = tree->left;
*successor = result->right;
result->right = tree->right;
}
free(tree->key);
free(tree);
return result;
}
return tree;
}

我没有测试它。successor不是先是right的别名，然后是left字段的别名。