Binary tree Algorithm

Discussion in 'C++' started by Aris, Dec 3, 2005.

  1. Aris

    Aris Guest

    Hello!
    This is my problem.
    I'm trying to make an inorder traversal algorithm for
    a binary tree, not a recursive one, but using a stack.
    Till now I got this:

    void traverse(tree * p)
    {
    l: if(p==0) goto s;
    push(p);
    p=p->l; goto l;
    r: visit(p);
    p=p->r;
    goto l;
    s: if(top==0) goto x;
    p=pop(); goto r;
    x: ;
    }

    we call this function this way : traverse(root);
    My question is :
    how can I eliminate goto's?
    Everything I've tryed is a mess.
    I'll be greatfull if you help me.
    Aris, Dec 3, 2005
    #1
    1. Advertising

  2. Aris

    Mike Wahler Guest

    "Aris" <> wrote in message
    news:dmt2lt$988$...
    > Hello!
    > This is my problem.
    > I'm trying to make an inorder traversal algorithm for
    > a binary tree, not a recursive one, but using a stack.
    > Till now I got this:
    >
    > void traverse(tree * p)
    > {
    > l: if(p==0) goto s;
    > push(p);
    > p=p->l; goto l;
    > r: visit(p);
    > p=p->r;
    > goto l;
    > s: if(top==0) goto x;
    > p=pop(); goto r;
    > x: ;
    > }
    >
    > we call this function this way : traverse(root);
    > My question is :
    > how can I eliminate goto's?


    do
    {
    while(p)
    {
    push(p);
    p=p->l;
    }

    if(top)
    {
    p = pop();
    visit(p);
    p = p->r;
    }
    } while(top);

    Or something like that (not tested).

    -Mike
    Mike Wahler, Dec 3, 2005
    #2
    1. Advertising

  3. * Aris:
    > Hello!
    > This is my problem.
    > I'm trying to make an inorder traversal algorithm for
    > a binary tree, not a recursive one, but using a stack.
    > Till now I got this:
    >
    > void traverse(tree * p)
    > {
    > l: if(p==0) goto s;
    > push(p);
    > p=p->l; goto l;
    > r: visit(p);
    > p=p->r;
    > goto l;
    > s: if(top==0) goto x;
    > p=pop(); goto r;
    > x: ;
    > }
    >
    > we call this function this way : traverse(root);
    > My question is :
    > how can I eliminate goto's?
    > Everything I've tryed is a mess.
    > I'll be greatfull if you help me.


    I will assume that this is not HOMEWORK. But if it is then an answer
    can still be helpful to others. Essentially, transform the code to
    something less awful one small step at a time, preserving the code's
    effect _exactly_ at each small step.

    Let's start with the first label, 'l'. The 'if' there effects a jump
    over the following code. So rearrange:

    void traverse(tree * p)
    {
    l: if( p != 0 ) // if(p==0) goto s;
    {
    push(p);
    p = p->l; goto l;
    }
    s: if( top == 0) goto x;
    p = pop(); goto r;
    r: visit(p);
    p = p->r;
    goto l;
    x: ;
    }

    Now you have loop there, so express that as a loop:

    void traverse(tree * p)
    {
    l: while( p != 0 )
    {
    push(p);
    p = p->l;
    }
    s: if( top == 0) goto x;
    p = pop(); goto r;
    r: visit(p);
    p = p->r;
    goto l;
    x: ;
    }

    The 'goto r' has no effect and so can be eliminated, along with the
    labels 's' and 'r' which are then no longer referenced:

    void traverse(tree * p)
    {
    l: while( p != 0 )
    {
    push(p);
    p = p->l;
    }
    if( top == 0 ) goto x;
    p = pop();
    visit(p);
    p = p->r;
    goto l;
    x: ;
    }

    That last goto is an outer loop, an infinite one which the goto in the
    middle breaks out of:

    void traverse(tree * p)
    {
    for( ;; )
    {
    while( p != 0 )
    {
    push(p);
    p = p->l;
    }
    if( top == 0 ) goto x;
    p = pop();
    visit(p);
    p = p->r;
    }
    x: ;
    }

    Finally replace the single remaining break-out-of goto with a break:

    void traverse(tree * p)
    {
    for( ;; )
    {
    while( p != 0 )
    {
    push(p);
    p = p->l;
    }
    if( top == 0 ) { break; }
    p = pop();
    visit(p);
    p = p->r;
    }
    }

    Now you can start to reason about correctness, e.g., what's that 'top'
    in there? Is it perhaps a global modified by 'visit'? If so, then
    that's evil and should be fixed, and if not so, then you have
    non-working code.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, Dec 3, 2005
    #3
  4. Aris

    Aris Guest

    very good!

    Not only a good answer but the way to face this problems
    in the future.
    Gratefull!
    Aris, Dec 4, 2005
    #4
  5. A good introduction how to handle trees (and other data structures) can be
    found in the free eBook "C++Course". Trees are discussed here:

    http://www.vias.org/cppcourse/chap21_01.html

    Regards,

    Hans


    =====================================
    Hans Lohninger
    EPINA GmbH - Software Development Lohninger
    www.lohninger.com
    mailto:eek:
    fax: +43-2233-541945
    ======================================

    "Aris" <> wrote in message
    news:dmt2lt$988$...
    > Hello!
    > This is my problem.
    > I'm trying to make an inorder traversal algorithm for
    > a binary tree, not a recursive one, but using a stack.
    > Till now I got this:
    >
    > void traverse(tree * p)
    > {
    > l: if(p==0) goto s;
    > push(p);
    > p=p->l; goto l;
    > r: visit(p);
    > p=p->r;
    > goto l;
    > s: if(top==0) goto x;
    > p=pop(); goto r;
    > x: ;
    > }
    >
    > we call this function this way : traverse(root);
    > My question is :
    > how can I eliminate goto's?
    > Everything I've tryed is a mess.
    > I'll be greatfull if you help me.
    >
    >
    >
    >
    Hans Lohninger, Dec 4, 2005
    #5
  6. Re: very good!

    Aris wrote:
    > Not only a good answer but the way to face this problems
    > in the future.
    > Gratefull!


    Just a note: it would be useful (or maybe simply more pleasant
    to whoever gave you that answer), to have quoted the message
    you replied to...
    Victor Bazarov, Dec 5, 2005
    #6
  7. Aris

    Aris Guest

    what's happening in this code?

    Hello!
    Im trying to implement a queue
    using a linked list.
    I've made that code
    and I expected my Degueue()
    function to return the value of the
    key of the node I constructed.
    But It does not.
    In fact it returns "Empty Queue"
    what am I doing wrong?


    #include <stdlib.h>
    #include <stdio.h>

    typedef struct Queue * link;
    struct Queue
    {
    link head;
    link tail;
    link next;
    int key;
    };

    void Enqueue(link Head,link Tail,int data)
    {
    link ptr=(struct Queue*)malloc(sizeof(struct Queue));
    ptr->key=data;
    if(Head==0) Head= ptr; else Tail->next=ptr;
    Tail=ptr;
    }

    int Dequeue(link Head,int data)
    {
    link temp;
    if(Head!=0){
    data=Head->key;
    temp=Head;
    Head=Head->next;
    }

    else
    {
    printf("Empty Queue\n"); return 0;
    }

    free(temp);
    return data;
    }

    int main()
    {
    link head=0;
    link tail=0;

    Enqueue(head,tail,1);

    int x=Dequeue(head,x);
    printf("%d\n",x);



    return 0;

    }
    Aris, Dec 7, 2005
    #7
  8. Aris

    Jeff Flinn Guest

    "Hans Lohninger" <> wrote in message
    news:4392ebff$0$28520$...
    >A good introduction how to handle trees (and other data structures) can be
    >found in the free eBook "C++Course". Trees are discussed here:
    >
    > http://www.vias.org/cppcourse/chap21_01.html
    >


    Except it's not really C++ is it.

    Jeff
    Jeff Flinn, Dec 7, 2005
    #8
  9. Aris

    Michael Wild Guest

    Jeff Flinn wrote:
    > "Hans Lohninger" <> wrote in message
    > news:4392ebff$0$28520$...
    >> A good introduction how to handle trees (and other data structures) can be
    >> found in the free eBook "C++Course". Trees are discussed here:
    >>
    >> http://www.vias.org/cppcourse/chap21_01.html
    >>

    >
    > Except it's not really C++ is it.
    >
    > Jeff
    >
    >
    >


    Since when does c++ have interfaces? (see
    http://www.vias.org/cppcourse/chap21_08.html) rather looks like java to
    me...

    - michael
    Michael Wild, Dec 7, 2005
    #9
  10. Aris

    Ron Natalie Guest

    Re: what's happening in this code?

    Aris wrote:
    > Hello!
    > Im trying to implement a queue
    > using a linked list.


    You know C++ already provides queues and linked list
    as part of the language?

    Further the code while syntactcally C++ is pretty
    poor C++ design.

    > void Enqueue(link Head,link Tail,int data)
    > {
    > link ptr=(struct Queue*)malloc(sizeof(struct Queue));


    > int main()
    > {
    > link head=0;
    > link tail=0;
    >
    > Enqueue(head,tail,1);


    head and tail are still null pointers here. You are passing
    by value. All Enqueue does is malloc stuff that gets lost.
    Ron Natalie, Dec 8, 2005
    #10
  11. Aris

    red floyd Guest

    Re: what's happening in this code?

    Ron Natalie wrote:
    > Aris wrote:
    >
    >> Hello!
    >> Im trying to implement a queue
    >> using a linked list.

    >
    >
    > You know C++ already provides queues and linked list
    > as part of the language?


    He may know it, but maybe he wants to implement it himself so that he
    can understand the concept or possible underlying data structures
    better.

    However, for production code, go with the Standard Library containers.
    red floyd, Dec 8, 2005
    #11
    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. C-man
    Replies:
    2
    Views:
    861
    Dietmar Kuehl
    Mar 4, 2004
  2. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,090
  3. Ravi
    Replies:
    6
    Views:
    1,600
    Richard Tobin
    Aug 22, 2005
  4. sharan
    Replies:
    4
    Views:
    674
    CBFalconer
    Oct 30, 2007
  5. Bogdan
    Replies:
    4
    Views:
    2,013
    Alf P. Steinbach /Usenet
    Oct 19, 2010
Loading...

Share This Page