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

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);

Answer 2

由于分配不是针对排序树的，因此您可以以广度优先的方式填充它。这意味着插入的第一个始终是根，下一个是下一级的第一个节点，因此它看起来像这样：

   0
  1 2
3 4 5 6

这是一篇进一步解释它的文章：

http://www.cs.bu.edu/teaching/c/tree/breadth-first/

Answer 3

二叉树中的简单插入和保持二叉树平衡是不同的问题。我建议您从第一个问题开始，只关注保持树中订单属性的正确性。你离那并不远。

然后你应该看看红黑树的经典实现，这是经过充分研究的保持树平衡的有效方法，但有成本，它更复杂。