BINARY SEARCH TREE

BINARY SEARCH TREE

Aim

To write a C program to implement a stack using binary search tree.

Algorithm

1.                  [Include all the necessary header files.]

2.                  [Declare the structure with all necessary variables.]

3.                  Read x;

4.                  Call INORDER().

5.                  Call PREORDER().

6.                  Call POSTORDER().

7.                  Call display().

8.                   

Algorithm For INSERT(P,X)

1.         If (pßNULL)

             Create P

P<-dataßx.

P->lchild ßPàrchildßNULL

Else

2.1              while(TEMP!=NULL)

2.2              Temp2ßTemp1

2.3              If(temp1àdataàx)

2.4              Else Temp1ßTemp1àrchild

2.5              [End of while structure]         

2.6              If(temp2àdataàx)

2.7              Temp 2ßTemp2àlchild

2.8              Temp 2àdataßx

2.9              Temp2àdataßslchildßtemp2àrchild Null

2.10          Else

2.11          Temp 2àTemp2ßTemp2àrchildßnull

2.12          Temp2àdataßx

2.13          Temp 2àlchildßTemp 2àrchildßnull

2.14          [Return P]

Algorithm For INORDER(p)

1.If(p!=Null)

2. CALL INORDER (pàxdhild)

3. WRITE(Dàdata)

4.CALL INORDER (pàrchild)

5. [End the function]

Algorithm for PREORDER

1.                  If (pl=NULL)

2.                  WRITE (PàData)

3.                  CALL PREORDER (PàlCHILD)

4.                  CALL PREORDER (Pà Rchild)

5.                  [END OF FUNTION]

Algorithm for POSTORDER

1.                  If (P!=NULL)

2.                  Call POSTORDER (Pàlchild)

3.                  Call POSTORDER (Pàrchild)

4.                  Write (Pàdata)

5.                  [End of function]

Algorithm for COUNT

If (P==NULL)

1.                  Return 0

2.                  Else

3.                  [Return (1+count(Pàlchild)+call count(Pàrchild)) ]

4.                  Algorithm for postorder

Algorithm for DISPLAY

If (T!=NULL)

1.                  Xß(lm+rm)/2

2.                  Call goto xy (x,4*y)

3.                  Write (t--.data)

4.                  Call display (tàlchild, lm,x, l+1)

5.                  Call display (tàrchild, x, rm,l+1)

6.                  [END THE FUNCTION}

Algorithm for SEARCH

1. while(temp!=NULL)

2. If (tempàdataßt)

     [Return temp]

    3.If (Tempàdata>x)

                  Tempßtempàlchild

   4. ELSE

         Tempßtempàrchild

  5. [RETURN NULL]