rama_krish627
rama_krish627
Branch Unspecified
03 Nov 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:
Prasad Ajinkya

Prasad Ajinkya

Branch Unspecified
04 Nov 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.
moksh

moksh

Branch Unspecified
06 Nov 2008
get ur self the full article here

https://en.wikipedia.org/wiki/Tree_traversal
Ashutosh_shukla

Ashutosh_shukla

Branch Unspecified
12 Jan 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
Ashutosh_shukla

Ashutosh_shukla

Branch Unspecified
12 Jan 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.

Share this content on your social channels -

Only logged in users can reply.