Cのバイナリツリーの実装

Question

私はツリーをC言語で実装しようとしていますが、トラバースしようとするたびにツリーの最初の3つのノードしか表示されず残りは失われます。私が100,200,300,400,500,600,700と入力すると、100,200,300が出力されます。私は問題がの挿入機能であると思うが、私はそれを把握できない。

#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

のみ100、200、300は出力であろう。

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

t、t->prevとt->nextが行われる（すなわち挿入、である）全てNULL 何もしないしない場合、それは あるので関数Insertました。

条件と

ような再帰呼び出し

を追加する場合のノードの挿入が行われるが、成長は深さ優先探索ようになるので、ツリーの成長がバイアスされます。
アプローチとして、幅優先探索のような次の挿入ポイントを検索する必要があります。
私はいくつかの方法があると思います。 私が提案する方法として、それは検索ではなくNULLノードを作成するときにプールとして保持する方法です。
キューをノードプールとして使用した具体的な実装は次のとおりです（多くのチェックは省略され、グローバル変数を使用することに注意してください）。

#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 
}