c - C 上的二叉树实现

Question

我试图在 C 中实现树，但问题是每当我尝试遍历它时，它只显示树的前三个节点，其余的都丢失了。比如，如果我输入 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

only 100 ,200, 300 will be in the output.

在插入函数

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

因为它是t时，t->prev和t->next不全为NULL什么(也就是插入)都没有完成。

添加条件和递归调用时

else if(t->prev->prev == NULL)
{
    t->prev->prev = insert(key, t->prev->prev);
}

节点的插入已经完成，但是由于增长变得像深度优先搜索，树的增长变得有偏差。
因此，作为一种方法，您需要像广度优先搜索一样搜索下一个插入点。
我认为有一些方法，作为我提出的一种方法，它是一种在创建 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
}