c - 帮助将值列表插入二叉树..？

Question

好吧，我已经研究了一段时间...试图找出一种算法来将我的随机数列表插入到二叉树中。

这是我到目前为止得到的:

NodePtr 和 Tree 是指向节点的指针

NodePtr CreateTree(FILE * fpData)
{
    int in;

    fscanf(fpData, "%i", &in);
    Tree T = (NodePtr)malloc(sizeof(Node));
    T->Left = NULL;
    T->Right = NULL;
    T->value = in;

    while((fscanf(fpData, "%i", &in)) != EOF)
    {   
        InsertInTree(in, T);
        printf("\n %p", T);
    }

    return T;

}


void InsertInTree(int value,Tree T)
{
    if(T == NULL)
    {
        T->Left = (NodePtr)malloc(sizeof(Node));
        T->Left->Left = NULL;
        T->Left->Right = NULL;
        T->Left->value = value;
        printf("\n %i ", value);
        return;
    }
    if(T->Left == NULL)
    {
        InsertInNull(value, T->Left);   
    }
    else if(T->Right == NULL) 
    {
        InsertInNull(value, T->Right);
    }
    else
    {
        if(T->Left->Left == NULL || T->Left->Right == NULL) InsertInTree(value, T->Left);
        else InsertInTree(value, T->Right);
    }
}

如果特定节点的两个子节点都不为空，我不知道该怎么办。我在这里所做的工作适用于少量数字(1、2、3、5、6)，但如果列表更大，它就会变得不平衡和错误。

Answer 1

它是一个搜索树吗？我没有看到任何 if (value < T->Value)条件。

并且您有一个 InsertNull(未显示)。这应该不是必需的，1 个函数就足够了。

要解决您的主要问题，请使用指针到指针参数，或者更优雅地始终返回一个新树:

//untested, no balancing
Tree InsertValue(Tree t, int value)
{
   if (t == null)
      t = // create and return new node
   else
   {
      if (value < t->Value)
         t->Left = InsertValue(t->Left, value);
      else
         t->Right = InsertValue(t->Left, value);      
   }
   return t;
}

在 CreateTree 中:

Tree t = InsertValue(null, in);