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:

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)
3. Best first
4. Heuristic algorithm

Suggest you pick up a good book on Algorithms / Searches / Trees.

moksh

Branch Unspecified
06 Nov 2008

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

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

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 : ');
new(p);
p^.info:=item;
p^.left:=NIL;
p^.right:=NIL;
IF (root=NIL) THEN
root:=p
ELSE
BEGIN
IF (search(item,temp)) THEN
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
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('1-Insertion');
writeln('2-Deletion');
writeln('3-Display');
writeln('4-Exit');
CASE ch OF
1 : insert;
2 : BEGIN
write('Enter the node to be deleted : ');
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.