Thread: Binary Tree Issues

Hello, i'm working on a project dealing with creating a Binary Tree and I've come to a point where i'm stuck on inserting new nodes into the tree. The following is the definitions for the structs and functions that must be used:

Code:

/*
 * Defines one node in the Binary Tree
 */
typedef struct TreeNode
{
    struct TreeNode *L;
    TreeInfoT info;
    struct TreeNode *R;
} *TreeNodeT;

/*
 * Tree type is just a pointer to the root of the tree
 */
typedef struct Tree
{
    TreeNodeT root;
} *TreeT;

/*
 * Creates tree node with the provided info node
 * Inserts the tree node into the correct position in the tree
 */
void insertTree(TreeT, TreeInfoT);

Now, when I look over the function insertTree I see that i'll be passing it a pointer to a Tree (which contains a pointer to a TreeNode) and also a pointer to some information (TreeInfoT is a pointer to a struct containing some information).

my current code looks like this:

Code:

void insertTree(TreeT a, TreeInfoT b)
{

if (a->root==NULL) //if the root of the tree is pointing to nothing
{                  //create the node, store the data and set the root equal tot he node
	TreeNodeT temp=(TreeNodeT)malloc(sizeof(struct TreeNode));
	if (temp==NULL) //if malloc fails, display error and exit
		{
			printf("Memory Allocation Failed! \n");
			exit(1);
		}
temp->info=b;      //store the pointer to the info in the nodes info field
temp->L=NULL;		 //set the L and R pointers to Null
temp->R=NULL;

a->=temp;			 //Point the root to the node
return				 //exit the function
}



else
	if (compareToTreeInfo(a->root->info,b)<= 0)
		insertTree(

edit: I've inserted my new code, now, but i'm still stuck when trying to figure this out recursively. the compareToTreeInfo function takes two things of type TreeInfoT (which are pointers to some information, we arn't allowed to know what type of information it contains until we show off the project which is why we have to do this with the pointers) and compares them, returning values as if it were strcmp. My issue is, the first time we check this it has to be done via a->root because we're being passed a pointer to the tree and not a pointer to the node. That means I have no clue how to do this recursively since any further calls won't have a root to go through....it would just be a->info.

Any help that can set me in the right direction would be SO helpful,
Anthony Vitello

You speak for findTree but you give insertTree. Insert a tree where? The insertTreeNode makes sense, but insertTree not that much. It would make sense creating a Tree, but that is just declaring a variable TreeT.

If you want to insert a node you could do:

Code:

insertNode(TreenNodeT pos, TreeInfoT info)
{
    pos = malloc(sizeof(*pos)); //best way to use malloc
    pos->R = pos->L = NULL;
    pos->info = info;    
}

or use any logic in order to insert a node

this

Code:

TreeInfoT findTree(TreeT, TreeInfoT);

needs a bit clarification. Why would you return a TreeInfoT? What is that info exactly? Maybe you mean

Code:

TreeNodeT findTree(TreeT, TreeInfoT);

In this case you can simply search the whole tree recursively. Like:

Code:

TreeNodeT findTree(TreeT tree, TreeInfoT info)
{
    TreeNodeT root= tree->root;
    return findNode(root, info);
}

and

Code:

TreeNodeT findNode(TreeNodeT node, TreeInfoT info)
{
    TreeNodeT found;
    if (node->info == info)
       return node;
   if (node->L) {
       found = findNode(node->L);
       if (found) return found;
   }
   if (node->R) {
      found = findNode(node->R);
      if (found) return found;
   }
   return NULL;
}

or sth like this (maybe not correct). It will search the node itself for info. If it exists it returns. If note it repeats the process for L and R nodes. At any point, if a findNode succeds, it returns the node.
Think findTree as the initialization function for findNode. Instead of doing

Code:

findNode(tree->root, info);

you can do

Code:

findTree(tree, info);

since it is a requirement

Ack, i'm sorry. I put the wrong definition. It's supposed to be:

Code:

/*
 * Creates tree node with the provided info node
 * Inserts the tree node into the correct position in the tree
 */
void insertTree(TreeT, TreeInfoT);

Also, i'll show you the definition for TreeInfoT as we can't change around any of the definitions provided in the .h files.

Code:

/*
 * The data for one person
 */
typedef struct TreeInfo
{
    char name[MAX_NAME];

} *TreeInfoT;

Note: The reason we have to use the TreeInfoT type is because the information stored in the nodes won't always just be an array of characters and so our nodes will be pointing to a pointer that holds the information so if we end up having to store an integer or a struct in the nodes than it can be quickly changed and the majority of the code won't have to be touched.

I'm not sure if this is useful but heres the code for the other function I had called to compare the TreeInfo

Code:

int compareToTreeInfo(TreeInfoT a, TreeInfoT b)
{
int temp;
temp=strcmp(a->name,b->name);

	return temp;
}

Note: again, it won't always be a string but if we end up changing it the only code I should have to change is how it compares and the definition.

also, though I wasn't actually having issues with findTree (just yet >.>) I do thank you for the response on it since I accidentally put the wrong info in my original post. Once I figure out how I can get this recursion down with the parameters that are called for to be passed I should be able to finish this off.

Also, since the TreeInfoT is a pointer to SOME kind of information which can change based no the definition I guess the findTree function should be returning the pointer to the information, once it's been found, as a "just in case" sort of situation.

What do you mean by "correct position"?

Well, in any case, as mentioned before just use two functions. Your insertTree:

Code:

void insertTree(TreeT a, TreeInfoT b)
{
  TreeNodeT temp = malloc(sizeof(struct TreeNode)); //better not to cast
  if (a->root==NULL) {
    ...
  }
  else {
       TreeNodeT correctPosition = foundNode(a->root, b);
       ...
  }
}

the foundNode(TreeNodeT, TreeInfoT) will be like the one posted before. Instead of the == I use you can use the compare function you have. Or any other method. Then in the insertTree() function you can allocate and insert a new node in the position you found. The idea is, again, to use two functions. One that takes a node, so you can use recursion and a basic one that will do the rest of operations