Binary Tree Implementierung auf C

Question

Ich versuche, Baum in C zu implementieren, aber die Sache ist, wenn ich versuche, es zu durchlaufen, zeigt es nur die ersten drei Knoten des Baumes und der Rest sind verloren. wie, wenn ich eingeben 100, 200, 300, 400, 500, 600, 700 dann nur 100, 200, 300 wird in der Ausgabe sein. Ich denke, das Problem ist mit Funktion einfügen, aber ich kann es einfach nicht herausfinden.

#include<stdio.h> 
#include<stdlib.h> 
struct node 
{ 
    int data; 
    struct node *prev; 
    struct node *next; 
}; 
typedef struct node list; 
list *head, *tail, *current, *newn; 
void inorder(struct node *t) 
{ 
    if(t != NULL) 
    { 

     inorder(t->prev); 
     printf("%d->",t->data); 
     inorder(t->next); 
    } 
} 

struct node * insert(int key, struct node *t) 
{ 
    if(t == NULL) 
    { 
     t = (list*)malloc(sizeof(list)); 
     t->data = key; 
     t->prev = NULL; 
     t->next = NULL; 
    } 
    else if(t->prev == NULL) 
    { 
     t->prev = insert(key,t->prev); 
    } 
    else if(t->next == NULL) 
    { 
     t->next = insert(key,t->next); 
    } 
    return(t); 
} 
int main() 
{ 
    int x=1, y, z=1; 
    current = (list*)malloc(sizeof(list)); 
    printf("Enter data:"); 
    scanf("%d",&current->data); 
    current->next = NULL; 
    current->prev = NULL; 
    head = current; 
    while(z == 1) 
    { 
     printf("Enter data:"); 
     scanf("%d",&y); 
     current = insert(y,current); 
     printf("want to insert more:"); 
     scanf("%d",&z); 
    } 
    printf("\nInorder Traversal:"); 
    newn = head; 
    inorder(newn); 

} 

Answer 1

nur 100, 200, 300 werden in der Ausgabe sein.

bei Insert Funktion

if(t == NULL) 
{ 
    ... 
} 
else if(t->prev == NULL) 
{ 
    ... 
} 
else if(t->next == NULL) 
{ 
    ... 
} 
return(t); 

Weil es Wenn t, t->prev und t->next nicht alle nichts NULL sind (das heißt, Einfügen) erfolgt.

Beim Hinzufügen von Bedingungen und rekursive Aufrufe wie

Insertion des Knotens erfolgt, aber da das Wachstum wie Tiefensuche wird, wird das Wachstum des Baumes voreingenommen.
Also, als Ansatz müssen Sie für die nächste Einfügemarke wie Breite erste Suche suchen.
Ich denke, es gibt einige Methoden, Als eine Methode, die ich vorschlage, ist es eine Möglichkeit, es als Pool bei der Erstellung eines NULL-Knoten zu halten, anstatt zu suchen.
Eine konkrete Implementierung, die eine Warteschlange als Knotenpool verwendet, ist wie folgt (Bitte beachten Sie, dass viele Prüfungen weggelassen werden und globale Variablen verwendet werden).

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

struct node{ 
    int data; 
    struct node *prev; 
    struct node *next; 
}; 
typedef struct node list; 

void inorder(struct node *t){ 
    if(t != NULL){ 
     inorder(t->prev); 
     printf("%d->",t->data); 
     inorder(t->next); 
    } 
} 
//node of queue 
typedef struct null_node { 
    list **nodepp; 
    struct null_node *next; 
} node_pool; 
//queue 
typedef struct queue { 
    node_pool *head; 
    node_pool *tail; 
} queue; 
//enqueue 
void push(queue *q, list **nodepp){ 
    node_pool *np = malloc(sizeof(*np)); 
    np->nodepp = nodepp; 
    np->next = NULL; 
    if(q->head == NULL){ 
     q->tail = q->head = np; 
    } else { 
     q->tail = q->tail->next = np; 
    } 
} 
//dequeue 
list **pop(queue *q){ 
    node_pool *head = q->head; 
    if(head == NULL) 
     return NULL; 

    q->head = q->head->next; 
    if(q->head == NULL) 
     q->tail = NULL; 
    list **nodepp = head->nodepp; 
    free(head); 
    return nodepp; 
} 

void clear_queue(queue *q){ 
    while(pop(q)); 
} 

list *Head; 
queue Q; 

struct node *insert(int key, struct node *root){ 
    list *t = malloc(sizeof(*t)); 
    t->data = key; 
    t->next = t->prev = NULL; 
    push(&Q, &t->prev);//enqueue a NULL node 
    push(&Q, &t->next); 

    if(root == NULL){ 
     return t; 
    } 
    list **null_nodep = pop(&Q);//dequeue the node 
    *null_nodep = t;//Replace with new node 
    return root; 
} 
int main(void){ 
    int /*x=1, unused x*/ y, z=1; 

    Head = NULL; 
    while(z == 1){ 
     printf("Enter data:"); 
     scanf("%d",&y); 
     Head = insert(y, Head); 
     printf("want to insert more:"); 
     scanf("%d",&z); 
    } 
    printf("\nInorder Traversal:"); 
    inorder(Head); 
    clear_queue(&Q);//Discard queued nodes 
}