Function that generates random BST?

[Makara]

I have to write a function the creates a random binary search tree that includes capital letters.

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

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.

[anduril462]

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.

[Makara]

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??

#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);
    }
}

[oogabooga]

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.

[Makara]

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??

[oogabooga]

The best method would be a "shuffle" I guess.

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]

You should probably read the article in the FAQ about not casting malloc, and also make the return type of main explicit.