1

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.

Improve this question
3
  • What's the purpose of this binary tree? In a binary search tree, for example, at each node you compare the value you're inserting to the value at the node. If it's less than (or equal, for argument's sake) the value you inspect the left subtree. If it's greater, you inspect the right. Any time you try to inspect a subtree that is empty, you create a new leaf node and give it the value you're inserting. You seem to always be going whichever way isn't currently populated? Commented Nov 7, 2010 at 23:11
  • Your options are to either rebalance yourself. Or to use a slighly different algorithm like a [Red-Black tree][1] which automatically rebalances. [1]: en.wikipedia.org/wiki/Red-black_tree Commented Nov 7, 2010 at 23:11
  • I think I know what I need to do now....I might have misunderstood what I am suppose to with this binary tree. I need to order it. Thanks everyone. Commented Nov 7, 2010 at 23:14

3 Answers 3

Reset to default
1

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);
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

What is the variable old? Surely you meant t instead?
So, I tried this... but if I have something that is sorted already ... like 1,2,3,4,5,6 it just chains them together.....how do i put it into likes a binary tree... :\
@Bri: What you want is a balanced binary search tree, which is a lot more challenging than just a bare-bones binary search tree. See en.wikipedia.org/wiki/Balanced_binary_search_tree for links to a number of different algorithms for balancing a binary search tree.
Ah geez, I'm really about to give up on my CS degree... I'll check that out...(I'm literally in tears over this...)
If this is for class, check the assignment again. The first tree most CS students are required to write is not a self balancing tree. Get the basics down by writing an unbalanced binary tree and then you will have the proper foundation for a balanced tree (probably an AVR tree). Just like anything else in life, programming is a gradual process. Take one step at a time and you will be fine. Don't give up.
|
1

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/

Improve this answer

2 Comments

any idea of how to code inserting a list of numbers in that format?
It is usually done using an array as the storage and div/mult to navigate between parents and children. I came up with a scheme to do it using pointers, but it ended up way too contrived. You should really talk to your instructor to get a clearer definition of the problem. I would guess that it is a sorted tree and the problem is worded poorly. In the CS class I tutored, we wrote an unbalanced sorted tree and used pre, post and mid traversal to print the contents of the tree (not the find function). Anything else seems odd for a CS teacher to assign.
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.