Why is there a problem with the creation of binary trees?-CodePudding

the code is in order to create a binary tree stored in a sequential structure, and to be able to traverse the binary tree in a previous order. However , when I create the binary tree, it can't output. Why is there a problem with the creation of binary trees? Is the struct has something wrong? please tell me how can I solve this problem? I will be appreciate you for what you have done.

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

typedef struct node
{
    int data;
    struct node* left;
    struct node* right;
}Tree;
typedef struct bit
{
    Tree *a[100];
    int length;
}Bitree;

typedef struct Stack
{
    Tree *sq[1000];
    int top;
}stack;

int empty(stack s)
{
    return s.top==-1;
}

void push(stack *s,Tree *p)
{
    s->sq[  s->top]=p;
}

void pop(stack *s)
{
    if(s->top!=-1)
    {
        s->top--;
    }
}
//return the top element


Tree *top(stack s)
{
    if(s.top!=-1)
        return s.sq[s.top];
}
Bitree *create(Bitree *tree1,int n)
{
    int x;
    tree1->a[0]->data=1;
    printf("%d ",tree1->a[0]->data);
    tree1->length=0;
    printf("请输入根节点\n");
    scanf("%d ",&x);
    tree1->a[1]->data=x;
    tree1->length  ;
    for(int i=2;i<=n;i  )
    {
        if(i%2==0)
        {
            printf("please input left binary tree\n");
            scanf("%d ",&x);
            tree1->a[i]->data=x;
            tree1->a[i/2]->left=tree1->a[i];
            tree1->length  ;
        }
        else
        {
            printf("please input right binary tree\n");
            scanf("%d ",&x);
            tree1->a[i]->data=x;
            tree1->a[i/2]->right=tree1->a[i];
            tree1->length  ;
        }
    }
    return tree1;
}
void preorder1(Bitree *t)
{
    stack s;
    s.top=-1;
    if(t->a[1]!=NULL) {
        push(&s,t->a[1]);
    }
    while(!empty(s))
    {
        Tree *x=top(s);
        pop(&s);
        printf("%d ",x->data);
        if(x->right!=NULL)
            push(&s,x->right);
        if(x->left!=NULL)
            push(&s,x->left);
    }
}
int main()
{

    int n;
    Bitree *t1;
    scanf("%d",&n);
    t1=create(t1,n);
    preorder1(t1);
}

CodePudding user response：

First problem I see , you forgot to allocate your Bitree and the a structure in it . try this :

int main()
{

int n;
Bitree *t1 = (Bitree*) malloc(sizeof(Bitree));
int i = 0 ; 
for(i ; i < 100 ; i  )
        t1->a[i] = (Tree*) malloc(sizeof(Tree)); 
scanf("%d",&n);
t1=create(t1,n);
preorder1(t1);
for(i = 0 ; i < 100 ; i  )
        free(t1->a[i]); 
free(t1); 
}

CodePudding user response：

Major issues with this program include:

Dereferencing the indeterminate initial value of main()'s pointer t1, as @AsmineBensalem observed first.

The signature of function create() suggests that there may have been some confusion about how space was supposed to be allocated -- create() receives a pointer to a Bitree, but also returns one. If that function were expected to allocate the space, then it would not need to receive a pointer to existing space, but given that it in fact relies on the caller to provide a valid Bitree *, there seems little point in it echoing that same pointer value back to the caller.

For the record, given create() as presently written, I would write main() like so (without malloc()):
```
int main(void) {
    int n;
    Bitree t1 = { .length = 0 };  // not a pointer; with initializer

    scanf("%d", &n);
    create(&t1, n);
    preorder1(&t1);
}
```
Declaring t1 as a Bitree instead of a Bitree * provides storage for the whole Bitree instead of just for a pointer to one. See below for more about the initializer.
Dereferencing the values of elements of t1->a when these (pointer) values are indeterminate, also as @AsmineBensalem observed first. This is essentially the same as the previous issue, and its recurrence suggests that you do not understand that declaring a pointer gets you only a pointer, not an object for it to point to. Since you seem to be trying to avoid dynamic allocation, you could start a solution to this by changing the definition of type Bitree to contain an array of the needed Tree objects instead of pointers to such objects:
```
typedef struct bit {
    Tree a[100];  // array of Tree, not of Tree *
    int length;
} Bitree;
```
That will require several additional changes elsewhere in the code, but these are straightforward.
Failing to initialize the left and right pointers of nodes that have fewer than two children. Your preorder() function assumes that these will be NULL where a node has no child in the specified direction, but create() does not ensure that.

You could, however, get that automatically by changing the definition of Bitree as described in the previous point, and ensuring that your Bitree object is declared with an initializer, as shown in the first point above. In that case, you don't have to explicitly initialize all the pointers to get null initial values for them, but you do need to provide an initializer for at least some part of the Bitree.

Alternatively, you could just have create() explicitly assign NULL to the child pointers of each node it initializes.

Additional issues include:

Function create()'s scanf() formats cause misleading behavior. This code appears three times:
```
    scanf("%d ",&x);
```
The trailing whitespace in the format matches any amount of whitespace, so scanf has to match it by continuing to read whitespace until it sees non-witespace. The practical effect is that the user has to input the value for each non-root node before the prompt for that node is printed, and they need to input an extra value or some kind of trailing junk in order to complete the input stage. Just remove the space at the end of each of these formats:
```
    scanf("%d", &x);
```
Function top() is declared to return a Tree *, but when the stack passed to it is empty, it terminates without returning anything.
Functions top() and empty() each receive a stack as an argument, by value. Although this is not inherently wrong, it does, in principle, involve making a copy of the caller's argument at every call. stack is a pretty big structure, so this is undesirable.
It is surprising that pop() pops an element from the stack without returning it. You work with that by first retrieving the top element with top() and then pop()ping it, but it would be much more conventional to have pop() both pop an element off the stack and return that element.
It is surprising and unnecessary that create() does not use the tree node at index 0. (I discount entering a dummy value into it, since that's purposeless when you don't mean for that value to be accessed elsewhere.)