Snippet of an easy binary search tree

Question

ALL I want to do is making binary search tree, inputting there from users, and then print out data in each node one by one according to the user's selection (whether he choose to print the data in the right node of the current node or the left). So I only define three functions: prompt(), inputData() and printOneNode().

As you can see, I place the prompt() function in an infinite while loop and continuously prompt the user for selection, until he chooses to exit.

I have also made some comments in the source code for improvement of my code.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct BSTnode{
    struct BSTnode* leftchild;
    struct BSTnode* rightchild;
    char data[20];
}BSTnode;

void prompt();
void inputData();
void printOneNode();


BSTnode firstNode;
BSTnode* MyNode=&firstNode;          //I don't know if there is another better way to initialize the first node

int main()
{
    //BSTnode* MyNode=malloc(sizeof(BSTnode));    //Can't initialize it in the main function , or it won't be accessible in another function 

    MyNode->leftchild=NULL;
    MyNode->rightchild=NULL;
    strcpy(MyNode->data,"");
    while(1)
        prompt();

    return 0;
}

void prompt(){
    int i=0;     
    printf("Please select:\n");
    printf("1.input a data\n2.print only one data\n3.Exit\n");

    scanf("%d",&i);
    switch(i){
        case 1:
            inputData();
            break;
        case 2:
            printOneNode();
            break;
        case 3:
            exit(0);
        default:
            printf("Please input a valid number!(1-3)");
    }
}

void inputData(){
    char data[20]={0};
    printf("Input your data here(character only / less than 19 characters!): ");
    scanf("%s",data);
    BSTnode** ptr=&MyNode;
    while(1){
        if(strcmp(data,(*ptr)->data)){
            if((*ptr)->rightchild!=NULL){
                ptr=&((*ptr)->rightchild);
                continue;
            }
            else{
                (*ptr)->rightchild=malloc(sizeof(BSTnode));
                ptr=&((*ptr)->rightchild);
                (*ptr)->rightchild=NULL;
                (*ptr)->leftchild=NULL;
                strcpy((*ptr)->data,data);
                break;
            }
        }

        else{
            if((*ptr)->leftchild!=NULL){
                ptr=&((*ptr)->leftchild);
                continue;
            }
            else{
                (*ptr)->leftchild=malloc(sizeof(BSTnode));
                ptr=&((*ptr)->leftchild);
                (*ptr)->leftchild=NULL;
                (*ptr)->rightchild=NULL;
                strcpy((*ptr)->data,data);
                break;
            }
        }
    }

    printf(" Your data have been input successfully!\n");
    return;
}


void printOneNode(){
    BSTnode** ptr=&MyNode;
    printf("The first node is%s\n",(*ptr)->data);
    while(1){
        printf("Select which side of node do you want to print now(l/r)?(q for quit) ");
        char a;
        getchar();                   //have to use getchar() to clear the buffer of stdin,
                                    // or the variable 'a' will automatically get a newline character.
                                   //I guess there might be some function to help improve
        scanf("%c",&a);
        switch(a){
            case 'l':
                {
                    if((*ptr)->leftchild!=NULL){
                        ptr=&((*ptr)->leftchild);
                        printf("\t%s\n",(*ptr)->data);
                    }
                    else
                        printf("There is no more leftchild");
                    break;
                }
            case 'r':
                {
                    if((*ptr)->rightchild!=NULL){
                        ptr=&((*ptr)->rightchild);
                        printf("\t%s\n",(*ptr)->data);
                    }
                    else
                        printf("There is no more rightchild!");
                    break;
                }
            case 'q':
                return;
            default:
                return;
        }
    }
}

Answer 1

This is a really interesting implementation. I wouldn't have thought to do it quite like this. I always like seeing something that looks at things in a new way!

Avoid Globals

There's no need for these to be global:

BSTnode firstNode;
BSTnode* MyNode=&firstNode;

You can make them local to main() and pass them to prompt() or whatever would be appropriate.

Avoid Infinite Loops & One Function Per Function

I'm not a big fan of infinite loops in general. There are a few cases where they might make sense. But neither of the ones in this code are good choices in my opinion. I'll show a better way in a minute.

Your prompt() function doesn't just prompt the user. It then takes their response and acts on it. It would be cleaner to have prompt() return what the user decided to do and act on it by calling inputData() or printOneNode() from main() like this:

int main ()
{
    BSTnode rootNode;
    BSTnode *myNode = &rootNode;
    myNode->leftchild = NULL;
    myNode->rightchild = NULL;
    strcpy(myNode->data,"");
    int userResponse;
    do
    {
        userResponse = prompt();
        if (userResponse == 1)
        {
            inputData(myNode);
        }
        else if (userResponse == 2)
        {
            printOneNode(myNode);
        }
    } while (userResponse != 3);
}

int prompt ()
{
    int i=0;

    do
    {
        printf("Please select:\n");
        printf("1.input a data\n2.print only one data\n3.Exit\n");

        scanf("%d",&i);
        if ((i < 1) || (i > 3))
        {
            printf ("Error in input.\n");
        }
    } while ((i < 1) || (i > 3));

    return i;
}

Too Many Levels Of Indirection

There are many places where you use pointers to pointers. There's rarely a need to do that unless you're going to change the value of a pointer and return it to the caller. That's not the case here. Just create a pointer and use that.

Don't Do More Work Than You Have To

In the loop inside inputData() you're using continue where you don't need to. There's only a single statement inside the while loop - an if/else statement. In both places where you have continue, it's the last statement in an if clause, and there's nothing after the if clause, so it will continue anyway.

You don't need the return statement at the end of inputData(). void functions will simply return after the last statement is reached.

Also, when you create new nodes, since you're setting all fields to 0, you can use calloc() instead of malloc() and it will set all fields to 0.

Only Allocate In One Place

Speaking of allocating new nodes, you should allocate all nodes in a single place. Otherwise, every time you want to change how nodes are allocated and initialized (for example, if you add a field that needs to be initialed to 1 instead of 0 in all nodes), you'll have to do it every place you allocate them. If it's in 1 place, it's much easier to do.

I'd create a new function named createNewNode() that looks something like this:

BSTnode* createNewNode()
{
    BSTnode* newNode = (BSTnode*)calloc(1, sizeof(BSTnode));
    return newNode;
}

Give Things Meaningful Names

You have variables named MyNode, data, and ptr. Those don't tell me anything about what type of data they hold. I'd rename them currentNode (since it's the node you're adding data to, or printing out), inputString, and nextNode since it's the next node in the tree to examine.

So the rest of the code would look something like this:

void inputData(BSTnode* rootNode){
    char inputString[20] = {0};
    printf("Input your data here(character only / less than 19 characters!): ");
    scanf("%s",inputString);
    BSTnode* nextNode = rootNode;
    int found = 0;

    while (!found) {
        if (strcmp(inputString, nextNode->data) > 0) {
            if (nextNode->rightchild != NULL) {
                nextNode = nextNode->rightchild;
            }
            else {
                nextNode->rightchild = createNewNode();
                nextNode = nextNode->rightchild;
                strcpy(nextNode->data, inputString);
                found = 1;
            }
        }
        else {
            if(nextNode->leftchild != NULL) {
                nextNode = nextNode->leftchild;
            }
            else {
                nextNode->leftchild = createNewNode();
                nextNode = nextNode->leftchild;
                strcpy(nextNode->data, inputString);
                found = 1;
            }
        }
    }

    printf(" Your data have been input successfully!\n");
}

void printOneNode(const BSTnode* rootNode) {
    const BSTnode* nextNode = rootNode;
    printf("The first node is %s\n", nextNode->data);

    int donePrinting = 0;
    while (!donePrinting) {
        printf("Select which side of node do you want to print now(l/r)?(q for quit) ");
        char a;
        getchar();                   //have to use getchar() to clear the buffer of stdin,
        // or the variable 'a' will automatically get a newline character.
        //I guess there might be some function to help improve
        scanf("%c",&a);
        switch(a){
            case 'l':
            {
                if(nextNode->leftchild != NULL) {
                    nextNode = nextNode->leftchild;
                    printf("\t%s\n", nextNode->data);
                }
                else
                    printf("There is no more leftchild");
                break;
            }

            case 'r':
            {
                if (nextNode->rightchild != NULL) {
                    nextNode = nextNode->rightchild;
                    printf("\t%s\n", nextNode->data);
                }
                else
                    printf("There is no more rightchild!");
                break;
            }

            case 'q':
                donePrinting = 1;

            default:
                printf ("Error in input.");
        }
    }
}

Also, I fixed a bug in inputData(). It was always inserted to the right because strcmp() returns -1 for "less than," 0 for "equal," and +1 for "greater than." You were just checking for "not equal" and always taking the first branch of the if.

Answer 2

//BSTnode* MyNode=malloc(sizeof(BSTnode));    //Can't initialize it in the main function , or it won't be accessible in another function 

I want to quickly list things wrong with this line. Most of these are very minor, but it's a lot for one line. Further, the big problem is particularly big.

Minor

• Trailing space.

• The = isn't spaced (nor is the //).

• Typo in the comment (space before the comma).

• Inconsistent naming. You write lowerCamelCase elsewhere for local variables, but use UpperCamelCase for this one. You also write BSTnode but MyNode. This should probably by BSTNode and myNode.

Significant

• It's way too long.

• There's no NULL check for malloc.

Big

• To make things accessible in other functions, pass it as a parameter. Do not use globals for this purpose.

Ideally one would do something like

int main() {
    // calloc automatically zeroes the fields
    BSTNode* myNode = calloc(1, sizeof(BSTNode));
    if (!myNode) {
        // Handle allocation failure by bailing.
        // Anything sensible is fine.
        return 1;
    }
    while(1) {
        prompt(myNode);
    }
}

Answer 3

I eventually make a success one, getting rid of most of the bug and potential risk in my code. Though this one it's not qualified to all the answers and suggestions given by other users within this question, it work out right and within my own expectation. So I decide to post it here in case you have any interest:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct BSTNode{
    struct BSTNode* leftchild;
    struct BSTNode* rightchild;
    char data[20];
}BSTNode;

void prompt(BSTNode*);
int inputData(BSTNode*);
void printOneNode(BSTNode*);


int main()
{
    BSTNode* firstNode=calloc(1,sizeof(BSTNode));
    if(!firstNode)
        return 1;

    firstNode->leftchild=NULL;
    firstNode->rightchild=NULL;
    strcpy(firstNode->data,"");
    while(1)
        prompt(firstNode);

    return 0;
}

void prompt(BSTNode* Node){
    int i=0;     
    printf("Please select\n1.input a data\n2.print only one data\n3.Exit\n");

    if(scanf("%d",&i)!=1){
        printf("scanf failed!!\nplease input a valid number!!\n");
        fflush(stdin);
        return;
    }
    switch(i){
        case 1:
            inputData(Node);
            break;
        case 2:
            printOneNode(Node);
            break;
        case 3:
            exit(0);
        default:
            printf("Please input a valid number!(1-3)");
    }
}

int inputData(BSTNode* Node){
    char data[20]={0};
    printf("Input your data here(character only / less than 19 characters!): ");
    scanf("%s",data);
    BSTNode* ptr=Node;
    while(1){
        if(strcmp(data,ptr->data)>0){
            if(ptr->rightchild!=NULL){
                ptr=ptr->rightchild;
                continue;
            }
            else{
                ptr->rightchild=calloc(1,sizeof(BSTNode));
                if(!ptr->rightchild)
                    return 1;
                ptr=ptr->rightchild;
                ptr->rightchild=NULL;
                ptr->leftchild=NULL;
                strcpy(ptr->data,data);
                break;
            }
        }

        else if(strcmp(data,ptr->data)<0){
            if(ptr->leftchild!=NULL){
                ptr=ptr->leftchild;
                continue;
            }
            else{
                ptr->leftchild=calloc(1,sizeof(BSTNode));
                if(!ptr->leftchild)
                    return 1;
                ptr=ptr->leftchild;
                ptr->leftchild=NULL;
                ptr->rightchild=NULL;
                strcpy(ptr->data,data);
                break;
            }
        }
        else{
            printf("There is a identical word in the BST tree already!\n");
            return 0;
        }
    }

    printf(" Your data have been input successfully!\n");
    return 0;
}


void printOneNode(BSTNode* Node){
    BSTNode* ptr=Node;
    printf("The first node is%s\n",ptr->data);
    while(1){
        printf("Select which side of node do you want to print now(l/r)?(q for quit) ");
        char a;
        //getchar();
        //fflush(stdin);
        if(scanf("%*c%c",&a)!=1){
            printf("scanf failed!!");
            exit(1);
        }
        switch(a){
            case 'l':
                {
                    if(ptr->leftchild!=NULL){
                        ptr=ptr->leftchild;
                        printf("\t%s\n",ptr->data);
                    }
                    else
                        printf("There is no more leftchild\n");
                    break;
                }
            case 'r':
                {
                    if(ptr->rightchild!=NULL){
                        ptr=ptr->rightchild;
                        printf("\t%s\n",ptr->data);
                    }
                    else
                        printf("There is no more rightchild!\n");
                    break;
                }
            case 'q':
                return;
            default:
                return;
        }
    }
}

Note that in the function printOneData(), I use a specifier %*c%c to get rid of the leading newline character in the stdin buffer, because the %c specifier in the scanf() function will not ignore the newline character(the %d will) , thus making trouble. Also, you can use fflush(stdin) and getchar() to get rid of that.

Answer 4

Avoid empty parameters lists: Rather than void prompt(), use void prompt(void). This approach will certainly cause a compiler warning should code call prompt("Hello") whereas void prompt() will not.

---

Instead allocating to the size of a type, allocate based on the variable. As code develops and the type of rightchild changes, the following is automatically the right size.

// (*ptr)->rightchild = malloc(sizeof(BSTnode));
(*ptr)->rightchild = malloc(sizeof *((*ptr)->rightchild));

---

Enforce size limit with code, do not trust the user to follow directions. Check the return value of input functions.

char data[20] = {0};
printf("Input your data here(character only / less than 19 characters!): ");
// scanf("%s",data);
if (scanf("%19s",data) != 1) return;  // EOF encountered

---

Code is using scanf() and leaving the user '\n' in stdin for some other function to cope. Better for each function to get the user input and not leave trailing char in stdin for some other function.

char data[20];
do {
  char line[sizeof data * 2];
  printf("Input your data here(character only / less than 19 characters!): ");
  if (fgets(line, sizeof line, stdin) == NULL) return;  // EOF encountered
while (sscanf("%19s", data) != 1);

Instead of filling code with the above (it has better error checking, but is longer), make a helper function to handle user input. Something like the below. The key is to control and validate user input before trusting it.

int ReadText(const char * prompt, char *dest, size_t len) {
  char format[];
  sprintf(format, "%%zus %%c", len -1);
  do {
    fputs(prompt, stdout);
    char line[len*2];
    if (fgets(line, sizeof line, stdin) == NULL) return EOF;
    int n1, n2;
    char sentinel;
    // catch blank lines and lines with more than `len-1` non-white-space.
  } while (sscanf(line, format, data, &sentinel) != 1);
  return 1;
}

...    
char dest[10];
if (ReadText("Input your data here", dest, sizeof dest) != 1) Handle_EOF();