You can use recursion.
You may be overthinking it all.
I'll argue that it is easier in C++, but don't take that to mean it's all that much more difficult in C, nor some snark against C. I wrote in C for years before C++ existed, and I have to think a bit to re-orient my thinking a little, but it's all good.
Ok, let's start with the simplest points, and what's good about what you've posted above.
Code:
typedef struct Bin_Node
{
int data;
struct Bin_Node *left;
struct Bin_Node *right;
}Bin_Node;
typedef struct Bin_Tree
{
struct Bin_Node *root; //same as head node in a linked list
int node_count;
}Bin_Tree;
This much is quite useful. The tree has a count, is initialized appropriately (you call an initializer function), and we have a workable node structure.
Now, about building the tree.
I'd suggest that for an unbalanced tree, this be changed:
Code:
int i, nums[] = {2, 6, 3, 9, 20, 13, 54, 10, 43};
In order to visualize what happens as you debug your example, it is best not to insert a value near or at the least of the data as your first entry. It makes the entire tree hang to the right. Change this to something like:
Code:
int i, nums[] = { 13, 6, 3, 9, 20, 2, 54, 10, 43};
I merely swapped 13 and 2. This is a better starting point. You might choose 20 instead.
Now, the heart of the problem (and where the first warning appears)
Code:
void insert_node(Bin_Tree *tree, Bin_Node *node)
{
if (!tree) //parent node has no children??
{
tree = node; // ***** < 1 >
}
else
{
if (tree->root->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
{
insert_node(tree->root->right, node);
}
else
{
insert_node(tree->root->left, node);
}
}
}
Note comment < 1 >. Here the warning exists because the tree is not a node. It contains a node. tree->root would work, but that's not the real problem.
The real problem is that the recursion does NOT need to track the tree structure. It is useful to store the count, sure, but it is NOT relative to the recursion into the tree. Consider one of your diagrams (you've posted several) populated with lots of leaves. Look at a leaf at least interior to the tree (not root).
What is it? It is not a tree. It is a node.
Now look at the root. It is a node, not a tree. The tree is completely outside and auxiliary to the structure of the tree.
In fact, the entire tree is represented by the root node of the tree, NOT THE TREE structure.
That's central to the problem you're having.
The tree starts at the root, but that's just a node (Bin_Node to you). The function insert_node should be changed to:
Code:
void insert_node( Bin_Node **root, Bin_Node *node );
I'll get to why in a moment (I know, you want to know what the ** is doing and why - patience padawan).
Now, look again where you call this, but IMAGINE it thus:
Code:
for (i = 0; i < 9; i++)
{
node = create_node();
assert(node != NULL);
node = initalize_node(node, nums[i]);
insert_node(&tree->root, node);
tree->node_count++;
}
You don't need to provide the tree here.
Ok, you're thinking, WHAT ABOUT COUNT?
I know...I get that. We must wrap this into another function. "insert_node" must be made "internal", called by yet an outer function that knows the tree structure.
Now, turn your attention to insert_node and look at the first test. Would tree ever be null? Think about that. It is fashioned, it must exist already. "tree" is NOT what may be null. "tree->root" is what starts out as null. The tree itself exists, was initialized so that root is null and count is zero. This test makes no sense here as a result.
Now consider this function:
Code:
bool insert_tree(Bin_Tree *tree, Bin_Node *node )
{
if( insert_node( &(tree->root), node ) )
{
tree->count++;
return true;
}
// maybe delete node here?
return false;
}
Note how the root is passed. This is the ADDRESS of the root, a member of tree. It is a pointer, so the address of a pointer is a pointer to a pointer, or Bin_Node **.
I'm not trying to tell you how to fix your code, but I am trying to suggest a change of direction. What happens if the insertion failed? You know you can't enter duplicates, for example. This, at least, considers insertion failure. It also assumes insert_node, an "interior" function, returns a bool to indicate success. By "interior" I mean not the function application code calls to insert a node.
What's more important, however, is that it provides THE ADDRESS of the root in the tree structure, and that's something that applies equally to recursive calls into the tree structure when leaves are not trees, but nodes.
So, insert changes.
Code:
bool insert_node(Bin_Node **root, Bin_Node *node)
{
if (! (*root)) //parent node has no children??
{
*root = node;
return true;
}
else
{
if ( (*root)->data < node->data) //the data of the parent we are looking at is less than the data of the node so go to its right child
{
insert_node( &((*root)->right), node);
return true;
}
//else - oops, what if equals - THE TREE STRUCTURE WOULD BE DESTROYED
else if ( (*root)->data != node->data )
{
insert_node( &((*root)->left), node);
return true;
}
return false; // that node already existed
}
}
Here the root is passed as the address of the pointer (the type is pointer to a pointer, or Bin_Node **). To use it, it must be "double de-referenced". The advantage here is that this enables the assignment to root's CONTENT to change the value IN THE CALLING CODE's notion of the root (be it root of the tree or leaf along the way).
Where I write (*root), this is one level of de-reference. What was passed is the address of the pointer, this gets the pointer that ** points to - the Bin_Node * you know and love.
Where I don't bother with parenthesis around root, it is merely because I have no reason to think there's an ambiguity, but for something like (*root)->right, I want to be sure both a reader and the compiler know I need first to get the pointer that the ** is pointing to (I know, dizzying), THEN I can use that pointer (a Bin_Node *) to de-reference into the struct using ->.
Another point made here is that there must be a plan when a duplicate is inserted. Duplicates are not allowed in a tree, it destroys the structure (the rules no longer apply). If the data is not <, it might not also be >, it could be "==". If it is equal, you must return a false (indicating insertion was refused).
In the exterior function I comment where you MIGHT decided to delete the new node so there's no memory leak, but I'll leave that interface detail to you. If not here, it would HAVE to be dealt with when called (a bit ugly). At least a false is returned to indicate refusal to accept the insertion.
In theory when a node is handed to tree_insert, that function "agrees" to take possession of the new node. If it is to be refused, that means deleting the node (at least that's how I see it).
I have not tested the code.
I have no idea if this actually works to solve your problems.
I'm merely trying to provide that "over the hump" illustration I think you need to get past the writers block you think you have.
I don't think "Bin_Node **" is required for searches, just insertions and possibly deletions. Deletion may need an "outer" function and an "interior" function along similar lines.
In my theory (suggested change), the interior function can recurse, but the outer function can't, it just sets things up for recursion and deals with the result of that operation, whatever it is (like decrementing count if deletion succeeds).