Thread: Binary Search Tree in Linked List

Code:

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


struct bst
{
    int val, level;
    struct bst *left, *right, *parent;
};


typedef struct bst BST;


BST *display(BST *tree);
BST *insert(int VAL, BST *tree);
int getLevel(BST *b, int lev);
BST *traverseTree(BST *tree);
BST *create();


BST *create()
{
    return NULL;
}


void main()
{
    int val;
    int choice;
    BST *tree = create();
    while(1)
    {
        clrscr();
        printf("\nMENU");
        printf("\n[1]Insert");
        printf("\n[2]Delete");
        printf("\n[3]Exit");
        printf("\nChoice? ");
        scanf("%d", &choice);
        switch(choice)
        {
            case 1:
            
                printf("\nInput value to insert: ");
                scanf("%d", &val);
                tree = insert(val, tree);
                display(tree);
                getch();
                break;
            
            case 2:
                clrscr();
                printf("Input value to delete: ");
                scanf("%d", &val);
                /*b = delete(val, b);*/
                display(tree);
                break;
            
            case 3:
                exit(0);
            
            default:
                break;
        }
    }
}


int getLevel(BST *b, int lev)
{
    int rl, ll;
    if(b==NULL)
        return lev-1;
    
    ll = getLevel(b->left, lev+1);
    rl = getLevel(b->right, lev+1);
    
    return (ll<rl) ? rl : ll;
}


BST *insert(int VAL, BST *tree)
{
    int level;
    static ctr = 1;
    BST *root;
    BST *new = NULL;
    level = getLevel(tree, 1);
    if (level == 5)
    {
        printf("Tree is full");


    }
    else if(tree==NULL)
    {
        tree = (BST *)malloc(sizeof(BST));
        tree -> val = VAL;
        tree -> level = ctr;
   
    }
    else
    {
        if (VAL < tree->val) 
        {
            ctr = ctr + 1;
            if (tree->left == NULL)
            {
            
                new = (BST *)malloc(sizeof(BST));
                new -> val = VAL;
                new -> parent = tree;
                tree ->left = new;
                new -> level = ctr;
            }
            else
                insert(VAL, tree->left);
        } 
        else 
        {
            ctr = ctr + 1;
            if(tree->right == NULL)
            {
                new = (BST *)malloc(sizeof(BST));
                new -> val = VAL;
                new -> parent = tree;
                tree-> right = new;
                new -> level = ctr;
            }
            else
                insert(VAL, tree->right);
        }
    }
    root = traverseTree(tree);
    display(root);
}


BST *traverseTree(BST *tree)
{
    BST *temp;
    temp = tree;
    while(temp->level !=1)
        temp = temp -> parent;
        
    return (temp);
}


BST *display(BST *tree)
{    
    if(tree!=NULL)
    {
        printf("\n\t%d", tree->val);
        display(tree->left);
        display(tree->right);
    }
    
}

The code above is supposed to be a binary search tree.
The main outcome for this program is to display the tree in C each time the user inserts or deletes a value.

Since I am a newbie in C programming, I first tried creating a code that would simply display the values in the tree after a user inserts and deletes, before I proceed to displaying the exact tree.

But when I run it the following output shows:


And when I try to insert another value,


It won't display anything and won't respond to any keys pressed.

I NEED YOUR HELP GUYS

Please help

Originally Posted by moondrums

Code:

BST *create()
{
    return NULL;
}


    BST *tree = create();

?

For some reason you're trying to create your tree inside insert which isn't working because modifying a local variable has no effect once that variable goes out of scope.

Also main returns an integer to the operating system and takes no arguments, it should be int main( void ).

There are possibly other errors but those seem like a good start.

Originally Posted by iMalc

How do you intend to display them?
Not something like this is it?:
Splay Tree Demo

Something like that. but without the lines..