About tree -- some code in C Primer - I don't understand

Discussion in 'C Programming' started by xianwei, Sep 19, 2007.

  1. xianwei

    xianwei Guest

    First,

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

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

    if (pTree->root == 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;
    }


    bool DeleteItem(const Item *pi, Tree *pTree)
    {
    Pair look;

    look = SeekItem(pi, pTree);
    if (look.child == NULL)
    {
    return false;
    }
    else if (look.parent == NULL)
    {
    DeleteNode(&pTree->root);
    }
    else if (look.parent->left == look.child)
    {
    DeleteNode(&look.parent->left);
    }
    else
    {
    DeleteNode(&look.parent->right);
    }

    return true;
    }

    I don't know why the upper code use

    else if (look.parent->left == look.child)
    {
    DeleteNode(&look.parent->left);
    }
    else
    {
    DeleteNode(&look.parent->right);
    }
    I think use
    else
    {
    DeleteNode(&look.child);
    }
    have the some effect.
    The C primer is a all-known book, so I know is my wrong, but I don't
    wrong
    where it is.~~please point

    then, second
    static void DeleteNode(Node **ptr)
    {
    Node *temp;
    puts((*ptr)->item.petName);
    if ((*ptr)->left == NULL)
    {
    temp = *ptr;
    *ptr = (*ptr)->right;
    free(temp);
    }
    else if ((*ptr)->right == NULL)
    {
    temp = *ptr;
    *ptr = (*ptr)->left;
    free(temp);
    }
    else
    {
    ......
    ......
    }
    }

    I don't think the if else if clause will delete the node,and keep
    the tree "alive", ~
    if child_node->left == NULL
    you must let the parent node, left field point the child_node-
    >right,

    but the above don't do this, so I doubtful
    My English is so poor, I can't express clearly why I think the code
    is wrong~~,
    but I try my best :(

    The C primer is a all-known book, so I know somewhere is my wrong,
    but I don't know where it is.~~please point
    xianwei, Sep 19, 2007
    #1
    1. Advertising

  2. xianwei <> writes:

    > First,
    >
    > typedef struct pair {
    > Node *parent;
    > Node *child;
    > } Pair;
    >
    > static Pair SeekItem(cosnt Item *pI, const Tree *pTree)
    > {
    > Pair look;

    <snip function body>
    > return look;
    > }
    >
    >
    > bool DeleteItem(const Item *pi, Tree *pTree)
    > {
    > Pair look;
    > look = SeekItem(pi, pTree);
    > if (look.child == NULL)
    > {
    > return false;
    > }
    > else if (look.parent == NULL)
    > {
    > DeleteNode(&pTree->root);
    > }
    > else if (look.parent->left == look.child)
    > {
    > DeleteNode(&look.parent->left);
    > }
    > else
    > {
    > DeleteNode(&look.parent->right);
    > }
    >
    > return true;
    > }
    >
    > I don't know why the upper code use
    >
    > else if (look.parent->left == look.child)
    > {
    > DeleteNode(&look.parent->left);
    > }
    > else
    > {
    > DeleteNode(&look.parent->right);
    > }
    > I think use
    > else
    > {
    > DeleteNode(&look.child);
    > }
    > have the some effect.
    > The C primer is a all-known book, so I know is my wrong, but I
    > don't wrong


    DeleteNode is given a pointer to the Node, presumably so it may modify
    the data held there. look is a local variable, so &look.child refers
    to an object that will vanish soon (when DeleteItem returns) so any
    modifications to it will not be modification to the tree itself.

    From this sample, I am not overly impressed with the code in this
    book, but your change would change the program's meaning. I think the
    program could probably be written more clearly, though.

    > where it is.~~please point
    >
    > then, second
    > static void DeleteNode(Node **ptr)
    > {
    > Node *temp;
    > puts((*ptr)->item.petName);
    > if ((*ptr)->left == NULL)
    > {
    > temp = *ptr;
    > *ptr = (*ptr)->right;
    > free(temp);
    > }
    > else if ((*ptr)->right == NULL)
    > {
    > temp = *ptr;
    > *ptr = (*ptr)->left;
    > free(temp);
    > }
    > else
    > {
    > ......
    > ......
    > }
    > }
    >
    > I don't think the if else if clause will delete the node,and keep
    > the tree "alive", ~
    > if child_node->left == NULL
    > you must let the parent node, left field point the child_node-
    >>right,

    > but the above don't do this, so I doubtful


    I not sure what problem you are seeing. I can't see any obvious
    problem with the code, but I am missing all the types and the "big
    picture" about what the code is for.

    > My English is so poor, I can't express clearly why I think the code
    > is wrong~~,
    > but I try my best :(
    >
    > The C primer is a all-known book, so I know somewhere is my wrong,


    You mean "well-known". Not all well-known books are good. Some are
    well-known for being bad. I don't know this one.

    --
    Ben.
    Ben Bacarisse, Sep 19, 2007
    #2
    1. Advertising

  3. xianwei

    xianwei Guest

    On 9 20 , 12 10 , Ben Bacarisse <> wrote:
    > xianwei <> writes:
    > > First,

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

    >
    > > static Pair SeekItem(cosnt Item *pI, const Tree *pTree)
    > > {
    > > Pair look;

    >
    > <snip function body>
    >
    >
    >
    >
    >
    > > return look;
    > > }

    >
    > > bool DeleteItem(const Item *pi, Tree *pTree)
    > > {
    > > Pair look;
    > > look = SeekItem(pi, pTree);
    > > if (look.child == NULL)
    > > {
    > > return false;
    > > }
    > > else if (look.parent == NULL)
    > > {
    > > DeleteNode(&pTree->root);
    > > }
    > > else if (look.parent->left == look.child)
    > > {
    > > DeleteNode(&look.parent->left);
    > > }
    > > else
    > > {
    > > DeleteNode(&look.parent->right);
    > > }

    >
    > > return true;
    > > }

    >
    > > I don't know why the upper code use

    >
    > > else if (look.parent->left == look.child)
    > > {
    > > DeleteNode(&look.parent->left);
    > > }
    > > else
    > > {
    > > DeleteNode(&look.parent->right);
    > > }
    > > I think use
    > > else
    > > {
    > > DeleteNode(&look.child);
    > > }
    > > have the some effect.
    > > The C primer is a all-known book, so I know is my wrong, but I
    > > don't wrong

    >
    > DeleteNode is given a pointer to the Node, presumably so it may modify
    > the data held there. look is a local variable, so &look.child refers
    > to an object that will vanish soon (when DeleteItem returns) so any
    > modifications to it will not be modification to the tree itself.
    >
    > From this sample, I am not overly impressed with the code in this
    > book, but your change would change the program's meaning. I think the
    > program could probably be written more clearly, though.
    >
    >
    >
    >
    >
    > > where it is.~~please point

    >
    > > then, second
    > > static void DeleteNode(Node **ptr)
    > > {
    > > Node *temp;
    > > puts((*ptr)->item.petName);
    > > if ((*ptr)->left == NULL)
    > > {
    > > temp = *ptr;
    > > *ptr = (*ptr)->right;
    > > free(temp);
    > > }
    > > else if ((*ptr)->right == NULL)
    > > {
    > > temp = *ptr;
    > > *ptr = (*ptr)->left;
    > > free(temp);
    > > }
    > > else
    > > {
    > > ......
    > > ......
    > > }
    > > }

    >
    > > I don't think the if else if clause will delete the node,and keep
    > > the tree "alive", ~
    > > if child_node->left == NULL
    > > you must let the parent node, left field point the child_node-
    > >>right,

    > > but the above don't do this, so I doubtful

    >
    > I not sure what problem you are seeing. I can't see any obvious
    > problem with the code, but I am missing all the types and the "big
    > picture" about what the code is for.


    thanks, yesterday I spent some times, The C primer book is right,
    I have some miss understand about Node **(pointer to pointer)~~~.
    thank you enthusiasm.Someone is right, I should need read the source
    code again and again.
    >
    > > My English is so poor, I can't express clearly why I think the code
    > > is wrong~~,
    > > but I try my best :(

    >
    > > The C primer is a all-known book, so I know somewhere is my wrong,

    >
    > You mean "well-known". Not all well-known books are good. Some are
    > well-known for being bad. I don't know this one.

    Thank you recommendation.And I think C Primer is a good book~~,but it
    is true that not all "well-known" book are good.~~:)
    xianwei, Sep 20, 2007
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. JS
    Replies:
    8
    Views:
    431
    Sven Heyll
    Mar 17, 2005
  2. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,110
  3. Simon
    Replies:
    9
    Views:
    313
    Default User
    Jul 18, 2006
  4. Peyman
    Replies:
    4
    Views:
    580
    mlimber
    Oct 31, 2006
  5. Matthew Wilson
    Replies:
    4
    Views:
    269
    Tim Roberts
    Jan 22, 2008
Loading...

Share This Page