问题描述

关于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));删不干净，这是为什么

解决方案

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;

}

解决方案二：

《C Primer Plus（第5版）中文版》第7章编程练习第5题
C Primer Plus(第5版)中文版
C Primer Plus(第5版)的笔记

解决方案三：

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

printf("ptr->name = %s
",(*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);这种的就完全没问题，这是怎么一回事