Thread: binary search trees in C

  1. #1
    Registered User
    Join Date
    Feb 2002
    Posts
    9

    binary search trees in C

    hey ca anyone help?
    i've got this program done out but now i need to write it out using strings and file handling,but i can't change it ,cause everytime i try it messes up on me ,
    anyway when using strings and files the program should read in string from a file,insert the strings into a binary search tree and on exiting the contents should be written back to the file,
    the user should then be able to search the tree for a string and display the data in a final binary search tree

    __________________________________________________ _
    //////////////////////////////////////////////////////////////////////////////////
    #include<stdio.h>
    #include<stdlib.h> //for dynamic memory allocation functions
    #include<conio.h>

    //structures

    typedef struct treenode
    {
    int value;
    struct treenode *left;
    struct treenode *right;
    }treenode;

    struct treenode *root;

    int count=0, arrcount=0, comp=0;
    int *array;

    void intree(int i)
    {
    root=(struct treenode *)malloc(sizeof(struct treenode));
    root->value=i;
    root->left=NULL;
    root->right=NULL;

    count++;
    }

    void add2tree(struct treenode *t,int i)
    {
    struct treenode *p;

    if((i>t->value)&&(t->right==NULL))
    {
    p=(struct treenode *)malloc(sizeof(struct treenode));
    p->value=i;
    p->left=NULL;
    p->right=NULL;
    t->right=p;

    return;
    }
    if((i<t->value)&&(t->left==NULL))
    {
    p=(struct treenode *)malloc(sizeof(struct treenode));
    p->value=i;
    p->left=NULL;
    p->right=NULL;
    t->left=p;

    return;
    }
    if(i>t->value)add2tree(t->right,i);
    else if(i<t->value)add2tree(t->left,i);
    }

    void inorder(struct treenode *t) // inorder traversal of the tree
    {
    if(t==NULL) return;
    inorder(t->left);
    printf("\nnumber %d",t->value);
    inorder(t->right);
    }

    //set arrcount (global) to 0 before calling this function

    void print2array(struct treenode *t)
    {
    if(t==NULL) return;
    print2array(t->left);
    array[arrcount]=t->value;
    arrcount++;
    print2array(t->right);
    }

    //set arrcount(global) to 0 before calling this function

    void getnum(struct treenode *t) //to get number of elements
    {
    if(t==NULL) return;
    getnum(t->left);
    arrcount++;
    getnum(t->right);
    }


    int search(struct treenode *t,int i)
    {
    comp++;
    if(i==t->value) {return 1;}
    if((i<t->value)&&(t->left==NULL)) {return 0;}
    if((i>t->value)&&(t->right==NULL)) {return 0;}
    if(i<t->value) {return search(t->left,i);}
    if(i>t->value) {return search(t->right,i);}

    return 0;
    }
    void callsearch()
    {
    int i,j;

    printf("\nEnter an element to be searched:");
    scanf("%d",&i);
    comp=0;
    j=search(root,i);

    if(j==1)
    {
    printf("\nFound after %d comparisons\n\n",comp);
    return;
    }
    else if(j==0)
    {
    printf("\nCould not find after %d comparisons\n\n",comp);
    return;
    }

    }

    void viewtree(struct treenode *t,int x, int y)
    {
    if(t==NULL) return;

    printf("%d",t->value);
    viewtree(t->left,x-4,y+1);
    viewtree(t->right,x+4,y+1);
    }

    int intro()
    {
    int i;

    printf("Please enter the number of the response you want according to the list below\n\n");
    printf("\n1 .Add items to the tree");
    printf("\n2 .View the tree");
    printf("\n3 .Search for an element");
    printf("\n4 .Exit\n");

    scanf("%d",&i);
    fflush(stdin);

    return i;
    }

    void main()
    {
    int i, n;
    abc: i=intro();

    if(i==1)
    {
    printf("\nEnter the element to be added to the tree:");

    scanf("%d",&n);
    fflush(stdin);
    arrcount=0;
    getnum(root);
    if(arrcount==0)
    {
    intree(n);
    }
    else
    {
    add2tree(root,n);
    }
    goto abc;
    }
    else if(i==2)
    {

    arrcount=0;
    getnum(root);
    if(arrcount==0)
    {
    printf("\nEmptytree");
    }
    else
    {
    viewtree(root,38,1);
    }
    getch();
    goto abc;
    }
    else if(i==3)
    {
    callsearch();
    getch();
    goto abc;
    }
    else if(i==4)
    {
    printf("\nThank you");
    getch();
    exit(0);
    }

    }

    ////////////////////////////////////////////////////////////////////////
    __________________________________________________
    Last edited by seeks; 02-21-2002 at 10:40 AM.

  2. #2
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    In code tags pls, i'll hava look at it k?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with binary search.
    By StateofMind in forum C Programming
    Replies: 6
    Last Post: 05-06-2009, 02:14 PM
  2. Binary Search Trees
    By lorannex in forum C Programming
    Replies: 3
    Last Post: 04-25-2009, 06:24 AM
  3. Performance issue!
    By maven in forum C Programming
    Replies: 42
    Last Post: 03-23-2009, 11:57 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM