c - 在C二叉树中插入函数？

Question

我的 C 语言二叉树代码根本没有运行，我不确定到底为什么。该函数有什么明显的错误吗？它仅使用一次插入即可运行，但使用次数过多就会停止工作。它只是一个简单的函数，可以将整数插入树中正确的位置。

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


typedef struct trees Tree;
struct trees {
    int data;
    Tree *left;
    Tree *right;
};

Tree *inicio=NULL; 


void insert(int n){
        Tree *novo = (Tree*)malloc(sizeof(Tree));
        Tree *aux;
        Tree *pai;

        novo->data=n;
        novo->left=NULL;
        novo->right=NULL;
    if(inicio==NULL){
            inicio = novo;
            return;
    } else {
        aux = inicio;
        pai = NULL;
        while(1){
            pai = aux;
            if(n>pai->data){
                aux=aux->right;
                if(aux==NULL){
                    pai->right=novo;
                    return;
            } else {
                aux=aux->left;
                if(aux==NULL){
                    pai->left=novo;
                    return;
                }

            }
            }
        }
    }   
}

int main() {
    insert(9);
    insert(8);

    printf("[%p] -> (%p, %d, %p)\n",inicio,inicio->left,inicio->data,inicio->right);    

    return 0;
}

Answer 1

为了说明@kaylum的观点，这里是重新格式化的相关部分

while(1){
    pai = aux;
    if(n>pai->data){
        aux=aux->right;
        if(aux==NULL){
            pai->right=novo;
            return;
        } // end if(aux==NULL)
        else
        {  // else => aux != NULL
           aux=aux->left;
           if(aux==NULL){
               pai->left=novo;
               return;
           } // end if(aux==NULL)
        } // end else
    } // end if(n>pai->data)
} // end while

请注意，return之后的else是毫无意义的噪音

while(1){
    pai = aux;
    if(n > pai->data){
        aux = aux->right;
        if(aux == NULL){
            pai->right = novo;
            return;
        }
        continue; // skip to next loop
    }
    // implying (n <= pai->data)
    aux = aux->left;
    if(aux == NULL){
        pai->left = novo;
        return;
    }
}

“更好”的实现可能会使用指针到指针并减少冗余代码。

void insert(int n)
{
    Tree **pp = &inicio;

    while (*pp)
    {
        if ((*pp)->data < n)
            pp = &(*pp)->right;
        else
            pp = &(*pp)->left;
    }

    *pp = malloc(sizeof **pp);
    if (*pp)
    {
        (*pp)->data = n;
        (*pp)->left = (*pp)->right = NULL;
    }
}