关于C Primer Plus第5版的二叉树的问题

//从树中删除一个项目
bool DeleteItem(const Item *pi,Tree *ptree)
{
Pair look;
look = SeekItem( pi, ptree);
//如果要删除的项目本身不存在
if(look.child == NULL)
{
return false;
}

//删除根项目
if(look.child == ptree->root)
{
    DeleteNode(&ptree->root);
}
else if(look.parent->left == look.child)
    //DeleteNode(&look.parent->left);
    DeleteNode(&(look.child));
else
    //DeleteNode(&look.parent->right);
    DeleteNode(&(look.child));
ptree->size--;
return true;

}

    DeleteNode(&look.parent->left);
    DeleteNode(&(look.child));删不干净,这是为什么

5个回答

typedef struct pair
{
Node *parent;
Node *child;
}Pair;

static Pair SeekItem(const Item *pi,const Tree *ptree)
{
Pair look;
look.parent = NULL;
look.child = ptree->root;

if(look.child == NULL)
    return look;


while(look.child != NULL)
{
    if(ToLeft(pi, &(look.child->item)))
    {
        look.parent = look.child;
        look.child = look.child->left;
    }
    else if(ToRight(pi, &(look.child->item)))
    {
        look.parent = look.child;
        look.child = look.child->right;
    }
    else
    {
        //不在左子树,也不在右子树,即找到指定节点
        break;
    }
}

return look;

}

static void DeleteNode(Node **ptr)
{
Node *temp;

printf("ptr->name = %s\n",(*ptr)->item.petname);

// 3种情况

// 1、2删除的节点没有子节点,删除的节点只有一个子节点
if((*ptr)->left == NULL)
{
    temp = *ptr;
    *ptr = (*ptr)->right;
    free(temp);
    temp->left = NULL;
    temp->right = NULL;
}
else if((*ptr)->right == NULL)
{
    temp = *ptr;
    *ptr = (*ptr)->left;
    free(temp);
    temp->left = NULL;
    temp->right = NULL;
}
else
{
    //删除的节点有两个子节点
    //右子树依附在左子树的最右的一个节点
    for(temp = (*ptr)->left;temp->right != NULL;temp = temp->right)
        continue;

    temp->right = (*ptr)->right;
    temp = (*ptr);
    (*ptr) = (*ptr)->right;
    free(temp);
}

}

用DeleteNode(&(look.child))删不干净,DeleteNode(&look.parent->left);这种的就完全没问题,这是怎么一回事

look.child==look.parent->left
但是&look.child!=&look.parent
两个指针的地址是不一样的。节点删除程序DeleteNode(Node **ptr)
使用二级指针 就是为了用形参改变实参,也就是改变look.parent->left
的指向,如果采用look.child改变的就是look.child的指向,就改错了对象。

见识浅薄,不知道说的对否,欢迎各位指导。

look.child==look.parent->left
但是&look.child!=&look.parent->left
两个指针的地址是不一样的。节点删除程序DeleteNode(Node **ptr)
使用二级指针 就是为了用形参改变实参,也就是改变look.parent->left
的指向,如果采用look.child改变的就是look.child的指向,就改错了对象。

见识浅薄,不知道说的对否,欢迎各位指正。

上面的少打了一点,重新补上。

你自己的理解基本上是正确的。
SeekItem函数作用是,找出队中相同项,然后把指向项的指针的值赋给child,把项的上一级项的指针的值赋给parient。
而DeleteNode函数本意是删除队中的项。
所以要赋给DeleteNode函数的参数应该是队中的指望项的指针的地址。
那哪个才是队中项的地址呢?
要是能画个图,我就能讲的更明白一点,可惜我不会上传图片。
先来明白child,parient都不是队中的项的指针,只是再创建了一个指针把队中项的指针值赋给了child,和parient.
parient--left是队中的指针。
实际上如果直接用DeleteNode(&child),删除的是child。
所以只能靠DeleteItem(&parient--left)来删除队中的项。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问