0

Question: Build a binary tree according to previous order and in order sequence of binary tree and output it. Problem : Incurring a runtime error. I think the problem may incur in fir_in_crea function,but i cannot solve this problem

MainFunc.c

#include "AllFun.h"
int main(int argc, char* argv[])
{
    int n;
    printf("Node numbers: ");
    scanf_s("%d", &n);

    int A[100], B[100];
    create(A, n);
    create(B, n);

    BiNode *BT = fir_in_crea(A, 1, 8, B, 1, 8);

    print(BT);

    return 0;
}

AllFun.h

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

typedef struct bitree {
    int data;
    struct bitree* lchild, *rchild;
} BiNode;

void create(int array[], int num);
void print(BiNode *bt);
BiNode *fir_in_crea(int A[], int s1, int e1, int B[], int s2, int e2);

OtheFunc.c

#include "AllFun.h"

void create(int array[], int num)
{
    printf("Enter elements of array: ");
    for (int i = 0; i < num; ++i)
        scanf_s("%d", &array[i]);
}


void print(BiNode* bt)
{
    printf("Output as level order: ");
     BiNode *queue[100], *temp;
    int s = 0, e = 0;
    queue[e++] = bt;
    while (s != e) {
        temp = queue[s++];
        printf("%d", temp->data);
        if (temp->lchild)
            queue[e++] = temp->lchild;
        if (temp->rchild)
            queue[e++] = temp->rchild;
    }
}

BiNode *fir_in_crea(int A[], int s1, int e1, int B[], int s2, int e2)
{
    BiNode *bt;
    int llen, rlen;
    int i;
    bt = malloc(sizeof(*bt));
    bt->data = A[s1];
    for (i = s2; B[i] != bt->data; ++i);
    llen = i - s2;
    rlen = e2 - i;

    if (llen)
        bt->lchild = fir_in_crea(A, s1+1, s1 + llen, B, s2, s2 + llen - 1);
    else
        bt->lchild = NULL;

    if (rlen)
        bt->rchild = fir_in_crea(A, e1 - llen + 1, e1, B, e2 - rlen + 1, e2);
    else
        bt->rchild = NULL;
    
    return bt;
}
lanqi
  • 85
  • 6
  • Not checking for other errors, at least `bt = (BiNode*)malloc(sizeof(int));` is bad because the structure to allocate contains `int` and it must be larger than `int`. It should be `bt = malloc(sizeof(*bt));`. (Note: casting results of `malloc()` family is [considered as a bad practice](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc)) – MikeCAT Aug 13 '21 at 11:51
  • 2
    `for (i = s2; i != bt->data; ++i);` doesn't make sense. This can simply be `i = bt->data;`. (Not checked if this operation is what to do here) – MikeCAT Aug 13 '21 at 11:55
  • 1
    Doing `queue[e++] = temp->rchild;` without checking if `temp->rchild` is not `NULL` may make `printf("%d", temp->data);` dereference `NULL` and invoke *undefined behavior*. – MikeCAT Aug 13 '21 at 11:56
  • Also both of `s++` and `e++` are done exactly once in each iteration of the loop `while (s != e)` in the function `print`. This means the loop will go infinitely and invoke *undefined behavior* by causing out-of-range access of the array `queue`. – MikeCAT Aug 13 '21 at 12:06
  • The answer to "how to solve" -> Debug your program. [debugging - What is a debugger and how can it help me diagnose problems? - Stack Overflow](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – MikeCAT Aug 13 '21 at 12:09

0 Answers0