C语言 在破译我的老师伪代码时遇到问题

Question

我正在为类和这个函数做二叉搜索树作业，我需要遵循教授的伪代码。不幸的是，我不确定一个具体的细节，她拒绝澄清。

伪代码的链接在这里： https://i.stack.imgur.com/Rit7e.jpg

SUBROUTINE insert(current, parent, node)
IF current is null
IF parent is null
root = node
ELSE
ID node.value < parent.value
parent.left = node
ELSE
parent.right = node
END IF
RETURN true
END IF
ELSE IF node.value = current.=value
RETURN false
ELSE IF ode.value < current.value
insert(current.left, current, node)
ELSE
insert(current.right, current, node)
END IF
END SUBROUTINE

代替node，我尝试了似乎大多数允许的变量，包括当前、父变量(甚至值，这不起作用。震惊。

bool recursiveInsert(Node* current, Node* parent, double value)
{
if (current == NULL)
{
if (parent == NULL)
{
}
else
{
if (current->value < parent->value)
{
parent->left = current;
}
else
{
parent->right = current;
}
return true;
}
}
else if(parent->value == current->value)
{
return false;
}
else if (parent->value < current->value)
{
insert(current->left, current->value, current);
}
else
{
insert(current->right, current->value, current);
}   
}

我希望输出将值添加到二叉搜索树并返回 true，但程序目前只是在我到达需要"节点"的部分时抛出错误。

Answer 1

伪代码上下文中的node是一个先前分配的节点，其中包含要插入到树中的数据。初始调用者分配它(这既毫无意义，也从未在 RW 代码中完成)。实际上，除非您正在考虑一个库，可能会将节点从一棵树移动到另一棵树中，并且您希望避免设置/拆卸节点本身的费用，否则实际执行此模式的可能性极小。

关于算法，它相当简单，虽然不是很漂亮：

1. 如果current和parent都为 null，则表示这必须是某个全局指针root跟踪的树中的第一个节点。因此，root直接分配传入节点。

2. 否则，如果current为空，但parent不是if，则表示parent是树中的某个潜在叶子(意味着它有一个左、一个右或两个都包含的空指针)，并且你已经落在了空指针上。插入需要与父值进行比较，以了解是将节点挂起在左侧还是右侧。请注意，这是低效的，因为您已经进行了此比较(这就是您最初到达这里的方式)。

3. 否则，如果current不为空，我们只需检查值是否相等或更小(如果两者都不为真，则假设更大)，并在必要时进入左或右的子树。在这种情况下，current.left或current.right成为递归current，而current成为相同递归调用的parent。

就是这样。这就是该算法的工作原理。坦率地说，这是边缘的。

要使用参数列表(最终参数采用值而不是节点)实现此算法，您只需确保节点分配仅在实际挂起时才发生，并且只有这样(有两种这样的情况。

bool recursiveInsert(Node* current, Node* parent, double value)
{
bool result = false;
if (current == NULL)
{
if (parent == NULL)
{
root = malloc(sizeof *root);
root->value = value;
root->left = root->right = NULL;
}
else
{
Node *p = malloc(sizeof *p);
p->value = value;
p->left = p->right = NULL;
if (value < parent->value)
{
parent->left = p;
}
else
{
parent->right = p;
}
result = true;
}
}
else if (value < parent->value)
result = recursiveInsert(current->left, current, value);
else if (parent->value < value)
result = recursiveInsert(current->right, current, value);
return result;
}

将值插入树中时，调用将如下所示：

recursiveInsert(root, NULL, value);

它不漂亮，但它有效。它依赖于全球root的存在可能是该算法最糟糕的部分。多重比较可能是

第二名。

---

不同的方法

理想情况下，树的根作为参数传入。此外，我们可以像现在一样使算法递归，但不再依赖于某些全局root。最后，我们可以将参数计数减少到两个：指针的地址(最初是根指针的地址)和要插入的值。唱一个指针到指针，因为树访问方法使这个算法优雅，无论是否使用递归。下面提供了两者：

递归插入

bool treeInsert(Node **pp, double value)
{
bool result = false;
if (!*pp)
{
*pp = malloc(sizeof **pp);
(*pp)->value = value;
(*pp)->left = (*pp)->right = NULL;
result = true;
}
else if (value < (*pp)->value)
{
result = recursiveInsert(&(*pp)->left, value);
}
else if ((*pp)->value < value)
{
result = recursiveInsert(&(*pp)->right, value);
}
return result;
}

迭代插入

bool treeInsert(Node **pp, double value)
{
bool result = false;
while (*pp)
{
if (value < (*pp)->value)
pp = &(*pp)->left;
else if ((*pp)->value < value)
pp = &(*pp)->right;
else break;
}
if (!*pp)
{
*pp = malloc(sizeof **pp);
(*pp)->value = value;
(*pp)->left = (*pp)->right = NULL;
result = true;
}
return result;
}

在任一情况下，您都可以通过传递根指针的地址(因此是指向指针的指针)来调用，其中空尝试由 NULL 根表示：

treeInsert(&root, value);

任何一个功能都将完成手头的任务。我将错误强化 asa 任务留给您(检查您的 mallocs)。

Answer 2

正如你提到的，这是一个在二叉搜索树中插入节点的函数。参数如下

1. parent是正在检查的节点的父节点。这将与树的根一起调用。

2. current是正在检查的父节点的左侧或右侧。首次调用函数时，如果当前节点的值小于 root，则应使用root->left，如果值大于root，则应使用root->right。如果root为空，则current也应NULL

   if (root == NULL)
   {
   ret = recursiveInsert(NULL, NULL, node);
   } 
   else if (root->value < node->value)     
   {
   ret = recursiveInsert(root->left, root, node);
   }
   else if (root-> value > node->value)
   {
   ret = recursiveInsert(root->right, root, node);
   }
   else 
   {
   //same value, handle error
   }
   

3. node是要添加到树中的新节点。此节点的内存分配应在调用recursiveinsert之前完成，并应指定值。

现在让我们看看您编写的代码。

第一个错误是将第三个参数作为double。这应该是之前应该已经分配过的node类型的参数。

从条件检查

ELSE IF node.value = current.=value
RETURN false

似乎node->value是整数类型。

考虑到所有这些因素，更新的代码如下。

Node* root = NULL;  //global variable
...
bool recursiveInsert(Node* current, Node* parent, Node* node)
{
if (current == NULL)
{
if (parent == NULL)
{
root = node;
}
else
{
if (current->value < parent->value)
{
parent->left = node;
}
else
{
parent->right = node;
}
return true;
}
}
else if(node->value == current->value)
{
return false;
}
else if (parent->value < current->value)
{
recursiveInsert(current->left, current, node);
}
else
{
recursiveInsert(current->right, current, node);
}   
}