A binary tree implemented in C
Header file for a binary tree
//---------------------------------------------------------------
// File: Code201_Tree.h
// Purpose: Header file for a demonstration of a binary tree
// Programming Language: C
// Author: Dr. Rick Coleman
//---------------------------------------------------------------
#ifndef CODE201_TREE_H
#define CODE201_TREE_H
#include <stdio.h>
// Define a structure to be used as the tree node
typedef struct TreeNodeType
{
int Key;
float fValue;
int iValue;
char cArray[7];
struct TreeNodeType *left;
struct TreeNodeType *right;
}TreeNode;
// Function prototypes
void CreateTree();
int isEmpty();
TreeNode *SearchTree(int Key);
int Insert1(TreeNode *newNode);
int Insert2(int Key, float f, int i, char *cA);
int Delete(int Key);
void PrintOne(TreeNode *T);
void PrintTree();
#ifndef FALSE
#define FALSE (0)
#endif
#ifndef TRUE
#define TRUE (!FALSE)
#endif
#endif
Implementation (.c) file for a binary tree
//---------------------------------------------------------------
// File: Code201_Tree.c
// Purpose: Implementation file for a demonstration of a binary tree
// Programming Language: C
// Author: Dr. Rick Coleman
// Date: February, 2002
//---------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Code201_Tree.h"
// Declare this as static so no code outside of this source
// can access it.
static TreeNode *root; // Declare global pointer to root of the tree
// Prototype this function so CreateTree can call it
static void ClearTree(TreeNode *T);
//--------------------------------------------
// Function: CreateTree()
// Purpose: Initialize tree to empty.
//--------------------------------------------
void CreateTree()
{
ClearTree(root);
root = NULL;
return;
}
//--------------------------------------------
// Function: ClearTree()
// Purpose: Perform a recursive traversal of
// a tree destroying all nodes.
// Note: Function is declared static so it cannot
// be accessed from outside
//--------------------------------------------
static void ClearTree(TreeNode *T)
{
if(T==NULL) return; // Nothing to clear
if(T->left != NULL) ClearTree(T->left); // Clear left sub-tree
if(T->right != NULL) ClearTree(T->right); // Clear right sub-tree
free(T); // Destroy this node
return;
}
//--------------------------------------------
// Function: isEmpty()
// Purpose: Return TRUE if tree is empty.
//--------------------------------------------
int isEmpty()
{
return(root==NULL);
}
//--------------------------------------------
// Function: DupNode()
// Purpose: Duplicate a node in the tree. This
// is used to allow returning a complete
// structure from the tree without giving
// access into the tree through the pointers.
// Preconditions: None
// Returns: Pointer to a duplicate of the node arg
// Note: Function is declared static so it cannot
// be accessed from outside
//--------------------------------------------
static TreeNode *DupNode(TreeNode * T)
{
TreeNode *dupNode;
dupNode = (TreeNode *)malloc(sizeof(TreeNode));
*dupNode = *T; // Copy the data structure
dupNode->left = NULL; // Set the pointers to NULL
dupNode->right = NULL;
return dupNode;
}
//--------------------------------------------
// Function: SearchTree()
// Purpose: Perform an iterative search of the tree and
// return a pointer to a treenode containing the
// search key or NULL if not found.
// Preconditions: None
// Returns: Pointer to a duplicate of the node found
//--------------------------------------------
TreeNode *SearchTree(int Key)
{
int ValueInTree = FALSE;
TreeNode *temp;
temp = root;
while((temp != NULL) && (temp->Key != Key))
{
if(Key < temp->Key)
temp = temp->left; // Search key comes before this node.
else
temp = temp->right; // Search key comes after this node
}
if(temp == NULL) return temp; // Search key not found
else
return(DupNode(temp)); // Found it so return a duplicate
}
//--------------------------------------------
// Function: Insert()
// Insert a new node into the tree.
// Preconditions: None
// Returns: int (TRUE if successful, FALSE otherwise)
//--------------------------------------------
int Insert1(TreeNode *newNode)
{
TreeNode *temp;
TreeNode *back;
temp = root;
back = NULL;
while(temp != NULL) // Loop till temp falls out of the tree
{
back = temp;
if(newNode->Key < temp->Key)
temp = temp->left;
else
temp = temp->right;
}
// Now attach the new node to the node that back points to
if(back == NULL) // Attach as root node in a new tree
root = newNode;
else
{
if(newNode->Key < back->Key)
back->left = newNode;
else
back->right = newNode;
}
return(TRUE);
}
//--------------------------------------------
// Function: Insert2()
// Insert a new node into the tree.
// Preconditions: None
// Returns: int (TRUE if successful, FALSE otherwise)
//--------------------------------------------
int Insert2(int Key, float f, int i, char *cA)
{
TreeNode *newNode;
// Create the new node and copy data into it
newNode = (TreeNode *)malloc(sizeof(TreeNode));
newNode->Key = Key;
newNode->fValue = f;
newNode->iValue = i;
strcpy(newNode->cArray, cA);
newNode->left = newNode->right = NULL;
// Call Insert1() to do the actual insertion
return(Insert1(newNode));
}
//--------------------------------------------
// Function: Delete()
// Purpose: Delete a node from the tree.
// Preconditions: Tree contains the node to delete
// Returns: int (TRUE if successful, FALSE otherwise)
//--------------------------------------------
int Delete(int Key)
{
TreeNode *back;
TreeNode *temp;
TreeNode *delParent; // Parent of node to delete
TreeNode *delNode; // Node to delete
temp = root;
back = NULL;
// Find the node to delete
while((temp != NULL) && (Key != temp->Key))
{
back = temp;
if(Key < temp->Key)
temp = temp->left;
else
temp = temp->right;
}
if(temp == NULL) // Didn't find the one to delete
{
printf("Key not found. Nothing deleted.\n");
return FALSE;
}
else
{
if(temp == root) // Deleting the root
{
delNode = root;
delParent = NULL;
}
else
{
delNode = temp;
delParent = back;
}
}
// Case 1: Deleting node with no children or one child
if(delNode->right == NULL)
{
if(delParent == NULL) // If deleting the root
{
root = delNode->left;
free(delNode);
return TRUE;
}
else
{
if(delParent->left == delNode)
delParent->left = delNode->left;
else
delParent->right = delNode->left;
free(delNode);
return TRUE;
}
}
else // There is at least one child
{
if(delNode->left == NULL) // Only 1 child and it is on the right
{
if(delParent == NULL) // If deleting the root
{
root = delNode->right;
free(delNode);
return TRUE;
}
else
{
if(delParent->left == delNode)
delParent->left = delNode->right;
else
delParent->right = delNode->right;
free(delNode);
return TRUE;
}
}
else // Case 2: Deleting node with two children
{
// Find the replacement value. Locate the node
// containing the largest value smaller than the
// key of the node being deleted.
temp = delNode->left;
back = delNode;
while(temp->right != NULL)
{
back = temp;
temp = temp->right;
}
// Copy the replacement values into the node to be deleted
delNode->Key = temp->Key;
delNode->fValue = temp->fValue;
delNode->iValue = temp->iValue;
strcpy(delNode->cArray, temp->cArray);
// Remove the replacement node from the tree
if(back == delNode)
back->left = temp->left;
else
back->right = temp->left;
free(temp);
return TRUE;
}
}
}
//--------------------------------------------
// Function: PrintOne()
// Purpose: Print data in one node of a tree.
// Preconditions: None
// Returns: void
//--------------------------------------------
void PrintOne(TreeNode *T)
{
printf("%d\t%f\t%d\t%s\n", T->Key, T->fValue, T->iValue, T->cArray);
}
//--------------------------------------------
// Function: PrintAll()
// Purpose: Print the tree using a recursive
// traversal
// Preconditions: None
// Returns: void
// Note: Function is declared static so it cannot
// be accessed from outside
//--------------------------------------------
static void PrintAll(TreeNode *T)
{
if(T != NULL)
{
PrintAll(T->left);
PrintOne(T);
PrintAll(T->right);
}
}
//--------------------------------------------
// Function: PrintTree()
// Purpose: Print the tree using a recursive
// traversal. This gives the user access
// to PrintAll() without giving access to
// the root of the tree.
// Preconditions: None
// Returns: void
//--------------------------------------------
void PrintTree()
{
PrintAll(root);
}
Main file used to test the tree
//---------------------------------------------------------------
// File: TreeMain.c
// Purpose: Main file for a demonstration of a binary tree
// Programming Language: C
// Author: Dr. Rick Coleman
// Date: February, 2002
//---------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Code201_Tree.h"
int main(void)
{
TreeNode *newNode;
char dummy; // Used in the scanf() to to pause before continuing
// Do initialization stuff
CreateTree();
printf("Building tree...\n");
// Do simple insert of 15 nodes into tree.
// Insert with keys in the order.
// 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15
// First 5 nodes are inserted using Insert1(). Remainder using Insert2()
// Node 1
newNode = (TreeNode *)malloc(sizeof(TreeNode));
newNode->Key = 8;
newNode->iValue = 2;
newNode->fValue = 2.3f;
strcpy(newNode->cArray, "Node1");
newNode->left = newNode->right = NULL;
Insert1(newNode);
// Node 2
// Note: Each time a new node is allocated we reuse the same pointer
// Access to the previous node is not lost because it is not in the tree.
newNode = (TreeNode *)malloc(sizeof(TreeNode));
newNode->Key = 4;
newNode->iValue = 4;
newNode->fValue = 3.4f;
strcpy(newNode->cArray, "Node2");
newNode->left = newNode->right = NULL;
Insert1(newNode);
// Node 3
newNode = (TreeNode *)malloc(sizeof(TreeNode));
newNode->Key = 12;
newNode->iValue = 8;
newNode->fValue = 4.5f;
strcpy(newNode->cArray, "Node3");
newNode->left = newNode->right = NULL;
Insert1(newNode);
// Node 4
newNode = (TreeNode *)malloc(sizeof(TreeNode));
newNode->Key = 2;
newNode->iValue = 16;
newNode->fValue = 5.6f;
strcpy(newNode->cArray, "Node4");
newNode->left = newNode->right = NULL;
Insert1(newNode);
// Node 5
newNode = (TreeNode *)malloc(sizeof(TreeNode));
newNode->Key = 6;
newNode->iValue = 32;
newNode->fValue = 6.7f;
strcpy(newNode->cArray, "Node5");
newNode->left = newNode->right = NULL;
Insert1(newNode);
// Node 6
// Remainder of the nodes are inserted using Insert2()
Insert2(10, 7.8f, 64, "Node6");
// Node 7
Insert2(14, 8.9f, 128, "Node7");
// Node 8
Insert2(1, 9.0f, 256, "Node8");
// Node 9
Insert2(3, 0.9f, 512, "Node9");
// Node 10
Insert2(5, 9.8f, 1024, "Node10");
// Node 11
Insert2(7, 8.7f, 2048, "Node11");
// Node 12
Insert2(9, 7.6f, 4096, "Node12");
// Node 13
Insert2(11, 6.5f, 8192, "Node13");
// Node 14
Insert2(13, 5.4f, 16384, "Node14");
// Node 15
Insert2(15, 4.3f, 32768, "Node15");
printf("All nodes inserted\n");
// Print the tree
printf("-----------------------------------------------------\n");
PrintTree();
printf("Press Enter to continue...");
scanf("%c", &dummy);
printf("-----------------------------------------------------\n");
// Find some nodes and print them
printf("-----------------------------------------------------\n");
printf("Testing the search function\n");
newNode = SearchTree(13);
if(newNode != NULL)
{
PrintOne(newNode);
free(newNode); // Remember this is a duplicate node of the one in
// in the tree and main() is responsible for deleting it.
}
else
printf("Search key not found.\n");
newNode = SearchTree(6);
if(newNode != NULL)
{
PrintOne(newNode);
free(newNode);
}
else
printf("Search key not found.\n");
newNode = SearchTree(1);
if(newNode != NULL)
{
PrintOne(newNode);
free(newNode);
}
else
printf("Search key not found.\n");
newNode = SearchTree(25); // Note: there is no Key=25 in the tree
if(newNode != NULL)
{
PrintOne(newNode);
free(newNode);
}
else
printf("Search key not found.\n");
// Delete some nodes
printf("-----------------------------------------------------\n");
printf("Testing delete function\n");
printf("-----------------------------------------------------\n");
printf("Testing deleting a leaf...\n");
Delete(7); // Delete a known leaf
PrintTree();
printf("Press Enter to continue...");
scanf("%c", &dummy);
printf("-----------------------------------------------------\n");
printf("-----------------------------------------------------\n");
printf("Testing deleting a node with 2 children...\n");
Delete(12); // Delete a node known to have 2 children
PrintTree();
printf("Press Enter to continue...");
scanf("%c", &dummy);
printf("-----------------------------------------------------\n");
printf("-----------------------------------------------------\n");
printf("Testing deleting a node with 1 child...\n");
Delete(6); // Delete a node known to have only 1 child
PrintTree();
printf("Press Enter to continue...");
scanf("%c", &dummy);
printf("-----------------------------------------------------\n");
printf("-----------------------------------------------------\n");
printf("Testing trying to delete a node that is not in the tree...\n");
Delete(7); // Delete a node that is not there
PrintTree();
printf("Press Enter to continue...");
scanf("%c", &dummy);
printf("-----------------------------------------------------\n");
printf("-----------------------------------------------------\n");
printf("Testing deleting the root...\n");
Delete(8); // Delete the root
PrintTree();
printf("Done.\nPress Enter to continue...");
scanf("%c", &dummy);
printf("-----------------------------------------------------\n");
}