Thread: creating a binary search tree

  1. #1
    Registered User
    Join Date
    Dec 2010
    Posts
    6

    creating a binary search tree

    I am really sorry.I didn't know how to use code tags.
    This is the program can anyone tell what is wrong with this

    #include<stdio.h>
    #include<stdlib.h>
    #define NULL 0
    struct binary
    {
    int number;
    struct binary *parent;
    struct binary *rightchild;
    struct binary *leftchild;
    };
    typedef struct binary node;
    main()
    {
    void create(node *head);
    void inorder(node *head);
    node *head;
    head=(node *)malloc(sizeof(node));
    printf("enter number and press -999 at the end");
    scanf("%d",&head->number);
    head->parent=NULL;
    head->rightchild=NULL;
    head->leftchild=NULL;
    create(head);
    inorder(head);
    }
    void create(node *list1)
    {
    node *list,*head1;
    int x;
    head1=list1;
    printf("enter number and press -999 at the end");
    scanf("%d",&x);
    if(x==-999)
    return;
    else
    {
    while(head1!=NULL)
    {
    list=head1;
    if(x<head1->number)
    {
    if(head1->leftchild==NULL)
    {
    list->leftchild=(node *)malloc(sizeof(node));
    list=list->leftchild;
    }
    head1=head1->leftchild;
    continue;
    }
    if(x>=head1->number)
    {
    if(head1->rightchild==NULL)
    {
    list->rightchild=(node *)malloc(sizeof(node));
    list=list->rightchild;
    }
    head1=head1->rightchild;
    }
    }
    list->number=x;
    list->parent=list;
    list->rightchild=NULL;
    list->leftchild=NULL;
    create(list1);
    }
    return;
    }
    void inorder(node *head1)
    {
    if(head1!=NULL)
    {
    inorder(head1->leftchild);
    printf("%d",head1->number);
    inorder(head1->rightchild);
    }
    return;
    }

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    For the sake of everyone's eyes;

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #define NULL 0
    
    struct binary
    {
        int number;
        struct binary *parent;
        struct binary *rightchild;
        struct binary *leftchild;
    };
    
    typedef struct binary node;
    
    main()
    {
        void create(node *head);
        void inorder(node *head);
        node *head;
        head=(node *)malloc(sizeof(node));
        printf("enter number and press -999 at the end");
        scanf("%d",&head->number);
        head->parent=NULL;
        head->rightchild=NULL;
        head->leftchild=NULL;
        create(head);
        inorder(head);
    }
    
    void create(node *list1)
    {
        node *list,*head1;
        int x;
        head1=list1;
        printf("enter number and press -999 at the end");
        scanf("%d",&x);
        if(x==-999)
        return;
        else
        {
            while(head1!=NULL)
            {
                list=head1;
                if(x<head1->number)
                {
                    if(head1->leftchild==NULL)
                    {
                        list->leftchild=(node *)malloc(sizeof(node));
                        list=list->leftchild;
                    }
                    head1=head1->leftchild;
                    continue;
                }
                if(x>=head1->number)
                {
                    if(head1->rightchild==NULL)
                    {
                        list->rightchild=(node *)malloc(sizeof(node));
                        list=list->rightchild;
                    }
                    head1=head1->rightchild;
                }
            }
            list->number=x;
            list->parent=list;
            list->rightchild=NULL;
            list->leftchild=NULL;
            create(list1);
        }
        return;
    }
    
    void inorder(node *head1)
    {
        if(head1!=NULL)
        {
            inorder(head1->leftchild);
            printf("%d",head1->number);
            inorder(head1->rightchild);
        }
        return;
    }
    Devoted my life to programming...

  3. #3
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    Your use of C is from 70s, man! Where did you find it? ( Or who taught you that way? )
    Devoted my life to programming...

  4. #4
    Registered User
    Join Date
    Dec 2010
    Posts
    6
    I follow ansiC-Balagurusamy

  5. #5
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    I don't know, it seems a little jumpy.
    Devoted my life to programming...

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    First you need to decide if you are doing an iterative or recursive add (create) function. As it stands, you're basically doing an iterative insert, but call the create function recursively to get more input and insert the next node. Then, here are a number of suggestions:

    1. Don't define your own NULL. It should be defined in stdlib.h, and may not be 0 on every system.
    2. Don't put prototypes inside functions
    3. It's int main(void), and return 0 when you're done: Cprogramming.com FAQ > main() / void main() / int main() / int main(void) / int main(int argc, char *argv[])
    4. Don't put input gathering in both the main routine and your create function. Have one place you gather input and a separate place you insert a node. This is called "separation of concerns", which is generally a very good design practice.
    5. if(x>=head1->number) will cause problems. You want strict inequality (>). There should not be duplicate nodes in a binary tree.

    Since you're basically doing an iterative add, here is some pseudo code to get you going:
    Code:
    node *create_node(int x)
        malloc a node
        initialize it's pointers to NULL
        set it's number to x
        return it
    
    node *insert_node(node *root, int x)
        node *curr;
        if root is null
            root = create_node(x)
        else
            set curr to root
            while curr is not NULL
                if x is less than curr->number
                    if curr->leftchild is NULL
                        set curr to curr->leftchild
                    else
                        curr->leftchild = create_node(x)
                        break out of loop
                else if x is greater than curr->number
                    // same code as above, but for rightchild
                else
                    print out "Duplicate node x"
                    break out of loop
        return root
    
    int main(void)
        int x;
        node *root;
    
        do
            print "enter number and press -999 at the end "
            get input
            if x is not -999
                root = insert_node(root, x)
        while x is not equal to -999
        print inorder traversal
        return 0;

  7. #7
    Registered User
    Join Date
    Dec 2010
    Posts
    6
    Thank you very much your pseudo works.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree problem (too)
    By ariadne in forum C Programming
    Replies: 1
    Last Post: 12-05-2010, 08:46 AM
  2. Help with delete - Binary search tree
    By lazyme in forum C Programming
    Replies: 10
    Last Post: 03-21-2010, 12:19 PM
  3. problem in creating a tree
    By Lorin_sz in forum C++ Programming
    Replies: 2
    Last Post: 09-26-2005, 01:28 PM
  4. problem in creating a tree
    By Lorin_sz in forum C Programming
    Replies: 1
    Last Post: 09-26-2005, 01:24 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

Tags for this Thread