CrazyEngineers
  • rama_krish627
    rama_krish627

    MemberNov 3, 2008

    Traversal in trees

    Hi,
    can any one tell me how the traversal operations take place in binary trees.
    Especially how the recursion takes place in such operations.:sshhh:
    Replies
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies
  • Prasad Ajinkya

    MemberNov 4, 2008

    Rama,
    1. Depth first
    1.a. L-C-R (Left Center Right)
    1.b. C-L-R (Center Left Right)
    2. Breadth first
    3. Best first
    4. Heuristic algorithm

    Suggest you pick up a good book on Algorithms / Searches / Trees.
    Are you sure? This action cannot be undone.
    Cancel
  • moksh

    MemberNov 6, 2008

    get ur self the full article here

    https://en.wikipedia.org/wiki/Tree_traversal
    Are you sure? This action cannot be undone.
    Cancel
  • Ashutosh_shukla

    MemberJan 12, 2009

    Hey traversal in binary trees.
    There are three traversals:
    1)Preorder
    2)Inorder
    3)Postorder
    In preorder you have to use the node left and then right
    In inorder you have to use left node and then right
    In postorder you have to use left right and then node
    Are you sure? This action cannot be undone.
    Cancel
  • Ashutosh_shukla

    MemberJan 12, 2009

    I forgot to paste my code in PASCAL in last post This code creates the tree and then displays them in all 3 orders
    {Program to perform basic operations on Binary Search Tree}
    PROGRAM BST(input,output);
    CONST n=20;
    TYPE nodeptr=^node;
         node=RECORD
         info:integer;
         left:nodeptr;
         right:nodeptr;
         END;
    VAR root,p,temp,y:nodeptr;
        i,item,ch:integer;
    FUNCTION search(x:integer;VAR n:nodeptr):boolean;
    VAR q,r:nodeptr;
        flag:boolean;
    BEGIN
         flag:=true;
         r:=root;
         q:=r;
         WHILE (flag) DO
         BEGIN
              IF (q^.info=x) OR (q=NIL) THEN
                 flag:=false
              ELSE
              BEGIN
                   n:=q;
                   IF (x>q^.info) THEN
                      q:=q^.right
                   ELSE
                       q:=q^.left;
              END;
         END;
         IF (q<>NIL) THEN
            search:=(NOT flag)
         ELSE
             search:=flag;
    END;
    PROCEDURE insert;
    BEGIN
         write('Enter the element to be inserted : ');
         readln(item);
         new(p);
         p^.info:=item;
         p^.left:=NIL;
         p^.right:=NIL;
         IF (root=NIL) THEN
            root:=p
         ELSE
         BEGIN
              IF (search(item,temp)) THEN
                 writeln('Element already present.')
              ELSE
              BEGIN
                   IF (item<temp^.info) THEN
                   BEGIN
                        p^.left:=temp^.left;
                        temp^.left:=p;
                   END
                   ELSE
                   BEGIN
                        p^.right:=temp^.right;
                        temp^.right:=p;
                   END;
              END;
         END;
    END;
    PROCEDURE delete(VAR root:nodeptr;val : integer);
    VAR p,q,r,ns,ps:nodeptr;
    BEGIN
         p:=root;
         q:=NIL;
         WHILE ((p<>NIL) AND (p^.info<>val)) DO
         BEGIN
              q:=p;
              IF (val<p^.info) THEN
                 p:=p^.left
              ELSE
                  p:=p^.right;
         END;
         IF (p=NIL) THEN
            writeln('Element not found')
         ELSE
         BEGIN
              IF ((p^.left<>NIL) AND (p^.right<>NIL)) THEN
              BEGIN
                   IF (p^.right<>NIL) THEN
                   BEGIN
                        ns:=p^.right;
                        WHILE (ns^.left<>NIL)DO
                              ns:=ns^.left;
                   END;
                   IF (q^.right<>NIL) THEN
                   BEGIN
                        ps:=q^.right;
                        WHILE (ps^.left<>NIL) DO
                              ps:=ps^.left;
                   END;
                   delete(root,ns^.info);
                   IF (q<>NIL) THEN
                      IF (p=q^.left) THEN
                         q^.left:=ns
                      ELSE
                          q^.right:=ns
                   ELSE
                       root:=ns;
                   ns^.left:=p^.left;
                   ns^.right:=p^.right;
              END
              ELSE
              BEGIN
                   IF (p^.left=NIL) THEN
                      r:=p^.right
                   ELSE
                       r:=p^.left;
                   IF (q<>NIL) THEN
                      IF (p=q^.left) THEN
                         q^.left:=r
                      ELSE
                          q^.right:=r
                   ELSE
                       root:=r;
              END;
         END;
    END;
    PROCEDURE preorder(p:nodeptr);
    BEGIN
         IF (root<>NIL) THEN
         BEGIN
              write(p^.info:3);
              IF (p^.left<>NIL) THEN
                 inorder(p^.left);
              IF (p^.right<>NIL) THEN
                 inorder(p^.right);
         END
         ELSE
             writeln('Tree contains nothing you fool!!!!');
    END;
    PROCEDURE inorder(p:nodeptr);
    BEGIN
         IF (root<>NIL) THEN
         BEGIN
              IF (p^.left<>NIL) THEN
                 inorder(p^.left);
              write(p^.info:3);
              IF (p^.right<>NIL) THEN
                 inorder(p^.right);
         END
         ELSE
             writeln('Tree contains nothing you fool!!!!');
    END;
    PROCEDURE postorder(p:nodeptr);
    BEGIN
         IF (root<>NIL) THEN
         BEGIN
              IF (p^.left<>NIL) THEN
                 inorder(p^.left);
              IF (p^.right<>NIL) THEN
                 inorder(p^.right);
              write(p^.info:3);
         END
         ELSE
             writeln('Tree contains nothing you fool!!!!');
    END;
    BEGIN
         ch:=0;
         root:=NIL;
         REPEAT
               writeln;
               writeln('MENU');
               writeln('1-Insertion');
               writeln('2-Deletion');
               writeln('3-Display');
               writeln('4-Exit');
               write('Enter your choice:');
               readln(ch);
               CASE ch OF
               1 : insert;
               2 : BEGIN
                   write('Enter the node to be deleted : ');
                   readln(item);
                   delete(root,item);
                   END;
               3 : inorder(root);
                    writeln('That was inorder');
                    preorder(root);
                    writeln('That was preorder');
                    postorder(root);
                    writeln('That was postorder');
         END;
         UNTIL (ch=4);
    END.
    
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register