• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 883
  • Last Modified:

Need help with Binary Trees in C

Ok, I'm trying to write a progam with a menu, that allows you to manipulate binary trees.  I've got most of the code finished.  Here are my problems:

1.) I am having some trouble understanding how to remove the specified number from the tree, and if it is not found in the tree, to show an error message.

2.) I do not know how to allow the menu to print out the contents of the tree in ascending and descending order.

I would greatly appreciate some help with these problems.  Even if you can't answer both questions, your help will be rewarded.
#include <stdio.h>
#include <stdlib.h>
 
typedef struct treenode{
  int data;
  struct treenode *left, *right;
} *binarytree;
 
#define TRUE 1;
#define FALSE 0;
typedef int boolean;
boolean is_full(binarytree t);
boolean is_empty(binarytree t);
 
char menu (void);
 
void init_tree(binarytree *t);
void add(binarytree *t, int input);
void take(binarytree *t, int xput);
int print();
 
int main (void)
{
  binarytree t;
  int input, xput;
  char selection;
  
  init_tree(&t);
  
  selection = menu();
  
  while (selection != 'q'){
    switch (selection){
      case '+': if(!is_full(t)){
		  printf("Enter a number: ");
	    	  scanf("%d", &input);
		  if(t == NULL)
		    add(&t, input);
		  else if(input <= t -> data)
		    add(&t -> left, input);
		  else
		    add(&t -> right, input);
		}
                else
		  printf("ERROR: Tree is full.");
		printf("\n");
		break;
      case '-': if(!is_empty(t)){
                  printf("Enter number to be removed: ");
		  scanf("%d", &xput);
		  if(xput == t -> data)
		    take(&t, xput);
		  else{
		    if(xput < t -> data)
		      take(&t -> left, xput);
		    else
		      take(&t -> right, xput);
		  }
		}
		else
                  printf("ERROR: Tree is empty.");
                printf("\n");
                break;
      case 'C':
      case 'c': if(!is_empty(t)){
		// print code goes here
		}
		else
		  printf("ERROR: Tree is empty.");
                printf("\n");
		break;
      default:  printf("%c is not a valid selection.\n", selection);
    }
    selection =  menu();
  }
  printf ("Goodbye!\n");
  printf ("\n");
}
 
char menu(void){
  char choice[2];
 
  printf("\n");
  printf("+\tAdd number to tree\n");
  printf("-\tRemove number from tree\n");
  printf("C\tDisplay contents of tree\n");
  printf("Q\tQuit\n\n");
  printf("Please enter a selection: ");
  scanf("%s", &choice);
  printf("\n");
 
  return choice[0];
}
 
void init_tree(binarytree *t){
  (*t) = NULL;
}
 
boolean is_full(binarytree t){
  t = (binarytree) malloc (sizeof(struct treenode));
  if(t == NULL){
    return TRUE;
  }
  else{
    free (t);
    return FALSE;
  }
}
 
boolean is_empty(binarytree t){
  if(t == NULL){
    return TRUE;
  }
  else{
    return FALSE;
  }
}        
 
void add(binarytree *t, int input){
  if((*t) == NULL){
    binarytree temp;
	temp = (*t);
	(*t) = (binarytree) malloc (sizeof(struct treenode));
	(*t)-> data = input;
	(*t) -> left = NULL;
	(*t) -> right = NULL;
  }
  else if(input <= (*t) -> data)
	add(&(*t) -> left, input);
  else
    add(&(*t) -> right, input);
}
 
void take(binarytree *t, int xput){ //need to add code for xput
  binarytree temp;
  
  if(((*t) -> left == NULL) && ((*t) -> right == NULL)){
    printf("1\n");
    temp = (*t);
	(*t) = NULL;
	free(temp);
  }
  else if(((*t) -> left != NULL) && ((*t) -> right == NULL)){
    printf("2\n");
	temp = (*t);
	(*t) = (*t) -> left;
	free(temp);
  }
  else if(((*t) -> left == NULL) && ((*t) -> right != NULL)){
    printf("3\n");
    temp = (*t);
	(*t) = (*t) -> right;
	free(temp);
  }
  else if(((*t) -> left != NULL) && ((*t) -> right != NULL)){
    printf("4\n");
    temp = (*t);
	(*t) = (*t) -> left;
	while((*t) -> right != NULL){
		(*t) = (*t) -> right;
	}
	(*t) -> right = temp -> right;
	(*t) = temp -> left;
	free(temp);
  }
  //if xput not found in tree, give error message
}
 
int print(){
//print code
}

Open in new window

0
Thickman
Asked:
Thickman
1 Solution
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi Thickman,

You've got several good questions, all at the heart of a binary tree.  If we can help you to understand the answers, you'll have gone far in understanding binary trees.

The first step is to understand exactly what a binary tree is.  It is simply a storage mechanism whereby the contents are stored in a sorted order.  Where the values are stored in memory is meaningless, as data is located by address, not position within a list or array.

The rules of a binary tree are simple.  For any node in the tree, all nodes that are accessed from the left child of the node have a value less than the current node.  Similarly, all nodes that are accessed from the right child of the node are larger than the node.

One possible binary tree (albeit a lousy one) is actually just a linked list.  It you were to construct a binary tree so that all nodes had a value for the left child of NULL, the construct

 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

Is a "tree" where all of the right children point to the next higher valued node.

But that's a lousy tree.  A much better one is balanced, where the middle value serves as the root node and all of the branches of the tree have the same number of nodes on each side.  That tree would look like this:

         4
      /     \
    2       6
   /  \    /  \
  1  3  5   7

Note that the basic rule applies.  All nodes to the left of 4 are smaller than 4.  All nodes left of 2 are smaller than 2.  All nodes to the right of 4 are larger than 4, etc.


Traversing the tree is very easy, but recursive.  You absolutely must understand recursion to manage the tree.

To traverse a tree, you recursively follow the left child of a node, then the right node.  Since this is recursive, you don't go left then right, you go left of current, left of next, left of next, until no more left children remain.  THEN you traverse the right children.  Note that after the recursion gets to a right child it may be necessary to traverse ITS left children.

The code is easy.  :)


InOrder (node *P)
{
  if (*P == NULL)
    return;

  if (P->Left)
    InOrder (P->Left);

  print ("Current node value is %d\n", P->Value);

  if (P->Right)
    InOrder (P->Right);

}

To print the list in reverse order, you simply move the *print* statement to after the check for the right child.  :)

And of course, you don't have to print anything.  If you're looking for a node, you'd return a flag to indicate that the node was found.

Deleting a node is a bit trickier.  You MUST know the parent node.  In the tree above, to delete the node with a value of 2, you'd make either of the child nodes of 2 the left child of of it's parent (4).  The other child of 2 would then have to be linked to the bottom of the chain that was linked to (4).

That would leave you with a tree that looked like this:

         4
      /     \
    3       6
   /        /  \
  1       5   7

or:

         4
      /     \
    1       6
      \    /  \
       3  5   7

The trees look different, but they are equivalent.


Now.  I'm sure that there are a ton more questions, so fire away.

Kent
0
 
ThickmanAuthor Commented:
No, that seems to all be fairly clear.  Thanks.
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now