Member • Nov 3, 2008
Traversal in trees
can any one tell me how the traversal operations take place in binary trees.
Especially how the recursion takes place in such operations.:sshhh:
Member • Nov 3, 2008
Member • Nov 4, 2008
Member • Nov 6, 2008
https://en.wikipedia.org/wiki/Tree_traversal
Member • Jan 12, 2009
Member • Jan 12, 2009
{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.