Like Tree1Likes
  • 1 Post By oogabooga

Function that generates random BST?

This is a discussion on Function that generates random BST? within the C Programming forums, part of the General Programming Boards category; I have to write a function the creates a random binary search tree that includes capital letters. Code: void GenerateBST(BinTreePointer ...

  1. #1
    Registered User Makara's Avatar
    Join Date
    Dec 2011
    Posts
    24

    Function that generates random BST?

    I have to write a function the creates a random binary search tree that includes capital letters.
    Code:
    void GenerateBST(BinTreePointer Root, int n)  {     int i;      for(i = 0; i < n; i++)     {         n = rand()% 26 + 'A';     } }
    First I create the empty BST, than I ask from the user to insert the number of the letters and than I call the GenerateBST. This is the main
    Code:
    main() {     int n;     BinTreePointer Root, LocPtr;     BinTreeElementType Item;      CreateBST(&Root);     printf("Give the number of letters: ");     n = GetInteger();      GenerateBST(Root,n);      InorderTraversal(Root);      system("PAUSE"); }
    I know I'm doing something wrong, but I can't understand it.
    Last edited by Makara; 03-30-2012 at 05:20 PM.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,469
    For starters, your code has no new lines, making it very difficult to read and debug. Then, you never actually insert the random letters. You just generate them, then do nothing with them. Lastly, read this: FAQ > main() / void main() / int main() / int main(void) / int main(int argc, char *argv[]) - Cprogramming.com. It's int main(void) and return an int at the end, usually 0.

  3. #3
    Registered User Makara's Avatar
    Join Date
    Dec 2011
    Posts
    24
    This is what I got so far. Please tell me whats wrong?? I think it has to do with the pointers. I create the tree at the beginning but when I call the insert function, the root remains empty which means the tree is empty.Am I right??
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef int BinTreeElementType;
    
    typedef struct BinTreeNode *BinTreePointer;
    struct BinTreeNode {
        BinTreeElementType Data;
        BinTreePointer LChild, RChild;
    };
    
    typedef enum {
        FALSE, TRUE
    } boolean;
    
    
    void CreateBST(BinTreePointer *Root);
    boolean EmptyBST(BinTreePointer Root);
    void BSTInsert(BinTreePointer *Root, BinTreeElementType Item);
    void InorderTraversal(BinTreePointer Root);
    void GenerateBST(BinTreePointer *Root, int n);
    //main program
    main()
    {
        int n;
        BinTreePointer Root;
    
        CreateBST(&Root);
        printf("Give the number of letters: ");
        n = GetInteger();
    
        GenerateBST(&Root, n);
    
        InorderTraversal(Root);
    
        system("PAUSE");
    }
    void CreateBST(BinTreePointer *Root)
    {
        *Root = NULL;
    }
    
    boolean EmptyBST(BinTreePointer Root)
    {
        return (Root==NULL);
    }
    void BSTInsert(BinTreePointer *Root, BinTreeElementType Item)
    {
        BinTreePointer LocPtr, Parent;
        boolean Found;
    
        LocPtr = *Root;
        Parent = NULL;
        Found = FALSE;
        while (!Found && LocPtr != NULL) {
            Parent = LocPtr;
            if (Item < LocPtr->Data)
                LocPtr = LocPtr ->LChild;
            else if (Item > LocPtr ->Data)
                LocPtr = LocPtr ->RChild;
            else
                Found = TRUE;
        }
        if (Found)
            printf("To %c EINAI HDH STO DDA\n", Item);
        else {
            LocPtr = (BinTreePointer)malloc(sizeof (struct BinTreeNode));
            LocPtr ->Data = Item;
            LocPtr ->LChild = NULL;
            LocPtr ->RChild = NULL;
            if (Parent == NULL)
                *Root = LocPtr;
            else if (Item < Parent ->Data)
                Parent ->LChild = LocPtr;
            else
                Parent ->RChild = LocPtr;
        }
    }
    void InorderTraversal(BinTreePointer Root)
    {
        if (Root!=NULL) {
            InorderTraversal(Root->LChild);
            printf("%d ",Root->Data);
            InorderTraversal(Root->RChild);
        }
    }
    void GenerateBST(BinTreePointer *Root, int n)
    {
        int i;
        BinTreeElementType Item;
        for(i = 0; i < n; i++)
        {
            Item = rand()% 26 + 'A';
            BSTInsert(*Root,Item);
            //printf("%c", Item);
        }
    }

  4. #4
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    You've hidden the pointer in a typedef (although the typedef name ends in Pointer ... which is kind of pointless). Normally, you'd define, say, BinTree and use BinTree* for a pointer, and BinTree** for a double pointer.

    Be that as it may, in GenerateBST you pass *Root to BSTInsert. Since Root is a BinTreePointer*, that means you're passing a BinTreePointer. But BSTInsert wants a BinTreePointer*. Hence, you should just be passing Root.

    BTW, you should decide whether you want to use BST as a prefix or suffix for all your bst function names. Don't use it as a prefix for some and suffix for others.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  5. #5
    Registered User Makara's Avatar
    Join Date
    Dec 2011
    Posts
    24
    Quote Originally Posted by oogabooga View Post
    You've hidden the pointer in a typedef (although the typedef name ends in Pointer ... which is kind of pointless). Normally, you'd define, say, BinTree and use BinTree* for a pointer, and BinTree** for a double pointer.

    Be that as it may, in GenerateBST you pass *Root to BSTInsert. Since Root is a BinTreePointer*, that means you're passing a BinTreePointer. But BSTInsert wants a BinTreePointer*. Hence, you should just be passing Root.

    BTW, you should decide whether you want to use BST as a prefix or suffix for all your bst function names. Don't use it as a prefix for some and suffix for others.
    Thanks. Now I have another question: How to generate random letters without repeating??

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    The best method would be a "shuffle" I guess.
    Code:
    char letters[26];
    
    /* TODO: Fill letters with 'A' to 'Z' */
    
    for (i = 25; i > 0; i--) {
        int r = (int)(rand() / (RAND_MAX + 1.0) * (i + 1));
        /* TODO: swap letters[i] and letters[r] */
    }
    You do that once (somewhere) and then pick a letter from the shuffled letters one at a time.

    Also, you should be calling srand((unsigned)time(NULL)); to seed the random number generator. This should only be done once, perhaps as the first executable statement in main.
    iMalc likes this.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    You should probably read the article in the FAQ about not casting malloc, and also make the return type of main explicit.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 01-25-2012, 06:24 PM
  2. A C program that generates random sentences
    By ecrazed in forum C Programming
    Replies: 3
    Last Post: 07-27-2011, 10:49 PM
  3. Program that generates a "random walk" across 10*10 array
    By danieldcc in forum C Programming
    Replies: 37
    Last Post: 07-23-2011, 01:19 AM
  4. Random Number Generator Always Generates 0 First
    By LyTning94 in forum C++ Programming
    Replies: 3
    Last Post: 06-21-2011, 03:08 PM
  5. Replies: 2
    Last Post: 12-25-2003, 12:31 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21