Help inserting a list of values into a binary tree..?

Well, I've been at it for a while...trying to figure out an algorithm to insert my list of random numbers into a binary tree.

This is what I have gotten so far:

NodePtr and Tree are pointers to a node

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

I'm lost on what to do if the both children of a particular node are not null. What I did here works for a small amount of numbers (1,2,3,5,6) but if the list is larger it becomes unbalanced and wrong.

---

Is it meant to be a search-tree? I don't see any if (value < T->Value) conditions.

And you have an InsertNull (not shown). That shouldn't be necessary, 1 function should be enough.

To address your main problem, use a pointer-to-pointer parameter or, more elegant, always return a new Tree:

//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;
}

And in CreateTree:

Tree t = InsertValue(null, in);

---

Since the assignment is not for a sorted tree, you can populate it in a breadth-first manner. This means the first thing inserted is always the root, the next is the first node at the next level so it looks like this:

   0
  1 2
3 4 5 6

Here is an article that explains it further:

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

---

Simple insertion in a binary tree and keeping a binary tree balanced are different problems. I suggest you start with the first problem and just focus on keeping order properties correct within the tree. Your are not far from that.

Then you should have a look at classical implementations for red-black trees, well studied and efficient way of keeping trees balanced, but with a cost, it's more complex.