Traversal in trees

Replies

• 

  Prasad Ajinkya

  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

  get ur self the full article here
  
  

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

• 

  Ashutosh_shukla

  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

  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 (itemNIL) AND (p^.info<>val)) DO
       BEGIN
            q:=p;
            IF (valNIL) 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.