Binary Trees in C

A binary tree is a data structure that visually looks cool, but more importantly allows for rapid searching by the way it is structured. The hierarchical structure is analogous to the family tree model, with parents and children the branch off from parents, and one single common ancestor, the root. Ideally, if we organize the tree well, the search time for any one element or “node” in the tree should take a time of log2n.

However, in order to get this to work, the tree must be balanced with the height of the left subtrees equaling the height of the right subtrees.

A binary tree can be set up as a multiply linked list in which each node consists of a link pointing to its left child, another link pointing to its right child, and its node data.

In our free-and-easy implementation, a node with NULL pointer values for the left child and right child is a leaf node.

To dynamically create and use a node, we will first allocate memory space via the malloc() system call. Therefore, the entire binary tree can dynamically grow or shrink during the execution of the program.

#include <stdio.h>
#include <stdlib.h>

typedef struct structNode {
 struct structNode *lChildPtr;
 struct structNode *rChildPtr;
 int iNodeData;
} sNode;

//create a new node with an int i
//data value
sNode * createNode(int i) {

 sNode *nPtr = (sNode*)malloc(sizeof(sNode));
 if (nPtr != NULL) {
 nPtr->lChildPtr = NULL;
 nPtr->rChildPtr = NULL;
 nPtr->iNodeData = i;
 return nPtr;
 }
 else {
 printf("Failed to allocated another node.\n");
 exit(EXIT_FAILURE);
 }
}

//release the memory space after it is used
void disposeNode(sNode * nPtr) {
 free(nPtr);
 nPtr = NULL;
}

int populateSubTree(int num, sNode *theNode) {
 theNode->lChildPtr = createNode(++num);
 theNode->rChildPtr = createNode(++num);
 return num;
}

//visit each node of the tree in order
//starts printing from the leftmost leaf node
//ends at the rightmost leaf node
void traverseInOrder(sNode *root) {
 if (root != NULL) {
 traverseInOrder(root->lChildPtr);
 //print root
 printf("%d\n", root->iNodeData);
 traverseInOrder(root->rChildPtr);
 }
}

//visit each node in tree
//starting from leftmost leaf node
//ending at the root of the trea
void traversePostOrder(sNode *root) {
 if (root != NULL) {
 traversePostOrder(root->lChildPtr);
 traversePostOrder(root->rChildPtr);
 //finally print root
 printf("%d\n", root->iNodeData);
 }
}



int main()
{
 int i = 1;
 sNode * rootNode = createNode(i);
 sNode * currentNode;

 i = populateSubTree(i, rootNode);
 i = populateSubTree(i, rootNode->lChildPtr);
 i = populateSubTree(i, rootNode->rChildPtr);

 
 currentNode = rootNode->lChildPtr;
 i = populateSubTree(i, currentNode->lChildPtr);
 i = populateSubTree(i, currentNode->rChildPtr);

 currentNode = rootNode->rChildPtr;
 i = populateSubTree(i, currentNode->lChildPtr);
 i = populateSubTree(i, currentNode->rChildPtr);

 printf("Traversing the tree, in order\n");
 traverseInOrder(rootNode);

 printf("\nTraversing the tree, post order\n");
 traversePostOrder(rootNode);

 return 0;
}

That’s enough for today. If you want, take a look at my book on Amazon.com http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s