0

The code is to implement binary search tree , the fist line is the data of the node to be created ,the second line is the data of the node to deleted ,then print the remaining tree in 'level order'.

The answer is correct when I execute it in GNU GCC but something the output is wrong when I compile it under Linux version of GCC code :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
} ;

int count=0;
int height=0;
void print_level_nodes(struct Node* current,int level)
{
    if(current==NULL)
    {
        return;
    }
    else if(level==1)
    {
        if(count>1)
        {
            printf("%d\n",current->data);
        }
        else
        {
            printf("%d",current->data);
        }
        count--;
    }
    else
    {
        print_level_nodes(current->left,level-1);
        print_level_nodes(current->right,level-1);
    }
}

int tree_height(struct Node* node)
{
    if(node==NULL)
    {
        return 0;
    }
    else
    {
        int left_height=tree_height(node->left);
        int right_height=tree_height(node->right);
        if(left_height>right_height)
        {
            return left_height + 1;
        }
        else
        {
            return right_height+1;
        }
    }
}

struct Node* Insert(struct Node* current, int num)
{
    if (current == NULL)
    {
        current = (struct Node*)malloc(sizeof(struct Node));
        current->data = num;
        current->left = NULL;
        current->right = NULL;
    }
    else
    {
        if (num > current->data)
        {
            current->right = Insert(current->right, num);

        }
        else if (num < current->data)
        {
            current->left = Insert(current->left, num);
        }
    }
    return current;
}

struct Node* Find_MIN(struct Node* root)
{
    if (root == NULL)
    {
        return;
    }
    while (root->left!=NULL)
    {
        root->left = Find_MIN(root->left);
    }
    return root;
}

struct Node* Delete(struct Node* root, int num)
{
    if (root == NULL)
    {
        return root;
    }
    if (num < root->data)
    {
        root->left = Delete(root->left,num);
    }
    else if (num > root->data)
    {
        root->right = Delete(root->right,num);
    }
    else
    {
        //0 child
        if (root->left == NULL && root->right == NULL)
        {
            free(root);
            root = NULL;
        }
        //1 child
        else if (root->left != NULL && root->right == NULL)
        {
            struct Node* temp = root;
            root = root->left;
            free(temp);
        }
        else if (root->left == NULL && root->right != NULL)
        {
            struct Node* temp = root;
            root = root->right;
            free(temp);
        }
        //2 child
        else if (root->left != NULL && root->right != NULL)
        {
            struct Node* temp = Find_MIN(root->right);
            root->data = temp->data;
            root->right = Delete(root->right,temp->data);
        }
        return root;
    }
}

int transfer_input(int num[] , char t1[])
{
   int i=0 , tmp=0;
   int index=0;
   while(t1[i]!='\0')
   {
        if(t1[i]==' ')
        {
            num[index++] = tmp;
            tmp=0;
            i++;
            continue;
        }
        else
        {
            tmp*=10;
            tmp+=(t1[i++]-'0');
        }
    }
    num[index] = tmp;
    index++;
    return index;
}

int main()
{
    struct Node* root = NULL;
    char t1[100000] , t2[100000] , tmp;
    int input1[100000] , input2[100000] , length1 , length2;

    scanf("%[^\r\n]",t1);
    scanf("%c",&tmp);
    if(tmp=='\r')
    {
        scanf("%c",&tmp);
    }
    scanf("%[^\r\n]",t2);
    if(tmp=='\r')
    {
        scanf("%c",&tmp);
    }
    length1 = transfer_input(input1 , t1);
    length2 = transfer_input(input2 , t2);

    for(int i=0 ; i<length1 ; i++)
    {
        root = Insert(root , input1[i]);
        count++;
    }
    for(int i=0 ; i<length2 ; i++)
    {
        if(length2==0)
        {
            break;
        }
        else if(length2!=0)
        {
            root = Delete(root , input2[i]);
            if(input2[i]>0)
            {
                count--;
            }
        }
    }
    height=tree_height(root);
    printf("height = %d",height);
    
    for(int i=1;i<=height;i++)
    {
        print_level_nodes(root,i);
    }
    
    return 0;
}

bolov
  • 72,283
  • 15
  • 145
  • 224
  • How are you compiling in Linux? – Tony Tannous Nov 07 '20 at 13:12
  • @TonyTannous I mean GCC – TheNotoruous0307 Nov 07 '20 at 13:13
  • 7
    Please check the compiler warnings: For `Find_MIN()` and `Delete()` *"not all control paths return a value"*. The code contains *undefined behaviour* and results will vary. – Weather Vane Nov 07 '20 at 13:15
  • @WeatherVane will the result vary when the codes contains undefined behaviour and using gcc -O2 optimization? – TheNotoruous0307 Nov 07 '20 at 13:21
  • 2
    Optimization level is irrelevant, but different levels might give different results. Some paths don't return any value, at least one has `return` but no value. If the behaviour is *undefined* that may still produce the right answer *by chance*. The optimiser can't *guess* the intention of logically (or syntactically) incorrect code. – Weather Vane Nov 07 '20 at 13:23
  • 1
    It's bad practice to have massive arrays (eg t1,t2,input1,input2) as local variables. Some systems might be able to accommodate them, others might not. Allocate such arrays in the heap instead. – dmuir Nov 07 '20 at 13:24
  • 2
    Off-topic: you said *"The answer is correct when I execute it in CodeBlocks"* -- CodeBlocks is an IDE but it does compile the code itself; it is able to use many compilers though. *"I executed it in CodeBlocks"* doesn't provide any information about what compiler are you using to compile the code. – axiac Nov 07 '20 at 13:37
  • @TheNotoruous0307 undefined behavior means anything can happen including [*nasal demons flying out of your nose*](http://www.catb.org/jargon/html/N/nasal-demons.html) – phuclv Nov 07 '20 at 14:00
  • Does this answer your question? [What does “warning: not all control paths return a value” mean? (C++)](https://stackoverflow.com/questions/49349006/what-does-warning-not-all-control-paths-return-a-value-mean-c) – phuclv Nov 07 '20 at 14:01
  • please stop vandalizing your post. If you remove the whole code, the question becomes unanswerable. – bolov Nov 07 '20 at 15:55
  • `Find_MIN` is rather fundamentally broken. `return` with no value is one thing, but this:`root->left = Find_MIN(root->left);`???? `Delete` is also completely broken even before it gets to `Find_MIN`. It simply cannot work with this signature. If this program ever gives a correct answer, this is by sheer luck (and an unbelievably huge amount of it). – n. m. could be an AI Nov 07 '20 at 16:18

0 Answers0