我有一个名为TreeNode的结构,带有一个int键,左右和父 . 我试图用我的DeleteNode函数从树中删除一个节点,但它无法正常工作 . 我应该用我的DeleteNode函数中的删除节点替换左子树的最大值 . 我的移植和max函数是DeleteNode的辅助函数 . 我的问题是我不知道在我的DeleteNode函数中我应该将我所处的节点值与我通过函数传递的值进行比较 . 我在我的代码中用星号评论,我很困惑该怎么做 . 任何帮助将不胜感激!
void transplant(TreeNode* u, TreeNode* v) //swaps u with v
{
if (u->parent == NULL) //if u was root, make v new root
u->parent = v;
else if (u == u->parent->left) //if u is smaller than it's parent
u->parent->left = v; //set v to the left child of parent of u. Swap them at left, really
else
u->parent->right = v; //otherwise swap them at right
if (v != NULL) //reassign parents to double link
v->parent = u->parent;
}
TreeNode* maximum(TreeNode* n)
{
while (n->left != NULL)
n = n->left;
return n;
}
void deleteNode(TreeNode *node, int key)
{
if (node->left == NULL) //if there is no left child
transplant(node, node->right); //swap
else if (node->right == NULL) //if there is no right child
transplant(node, node->left); //swap
else
{
if(node->key == key){ //****This if comparison must be wrong***
TreeNode* temp = maximum(node->right); //make temp the max on right
if (temp->parent != node ) //if it is more than one chain down
{
transplant(temp, temp->right); //swap temp and it's right branch
temp->right = node->right; //set right branch to nodes right
temp->parent->right = temp; //set temp to the right child
}
transplant(node, temp); // transplant
temp->left = node->left; //get nodes left branch
temp->left->parent = temp; //replace
}
}
}
1 回答
首先,你需要处理三个案例:(直接来自维基百科 . 当我使用数据结构时对我很好)
有三种可能的情况需要考虑:
删除没有子节点的节点(叶子):只需从树中删除节点即可 .
删除具有一个子节点的节点:删除节点并将其替换为其子节点 .
删除具有两个子节点的节点:调用要删除的节点N.不要删除N.而是选择其有序后继节点或其有序前导节点R.将R的值复制到N,然后递归在R上调用delete直到达到前两种情况之一 .
从广义上讲,有孩子的节点更难删除 . 与所有二叉树一样,节点的有序后继是其右子树的最左边的子节点,节点的有序前导是左子树的最右边的子节点 . 在任何一种情况下,该节点将具有零个或一个子节点 . 根据上述两个简单案例中的一个删除它 .
由于最大值(node-> right),您似乎正在尝试实现有序后继选项 .
既然我们确定了你可能的病例,那么真正需要移植的唯一病例就是第三例,我认为有两个孩子 .
情况1:只需在叶节点上调用delete .
案例2:
这里,del是要删除的节点(在这种情况下del有一个正确的子节点) . 我刚刚快速写了这篇文章 . 第一个if语句检查del是否是其父节点的左子节点,然后通过将其父节点指向其子节点从指针方程中“移除”自身,反之亦然 . 第二个if是相同的,但是检查del是否是其父节点的正确子节点 . 最后,删除节点 .
案例3:
就是这样 .