A Very Basic Introduction to Binary Trees in C

A binary tree is a finite set of elements called nodes, where each node is either empty or else is partitioned into three disjoint subsets, which themselves may also be likewise partitioned, or else empty.

A node in a binary tree may have at most two child nodes, a left node and a right node. A node that has no child nodes is called a leaf. The greatest ancestor of all nodes in the binary tree is the root node. Trees are graphically represented as growing downwards, rather than upwards.

The levels of a tree are defined starting at 0 for the root node, and increasing by one for each node descended from the parent node. The depth of the tree is determined by the maximum level of the leaf with the longest path from the root.

If every nonleaf node in a binary tree has nonempty left and right child nodes, then tree is a strictly binary tree. A complete binary tree of a certain depth of x is the strictly binary tree all of whose leaves reach level x.

In  a complete binary tree, the number of nodes at a certain level is twice the number of nodes at the level before it. Likewise, in a complete binary tree, the total number of nodes is always odd; in fact, the formula for finding the total number of nodes is the number 2 raised to a certain power, and then having one subtracted from that number, or 2^x – 1, where x is equal to the number of levels.

The official formula for finding the maximum number of nodes in a binary tree, which is the number of nodes a complete binary tree will have, is actually 2^(k+1) – 1, where k represents the height of the tree. Why k+1? Because height is measured by counting the number of lines, called edges, between the root node and its furthest descendant. As the root node by definition has no ancestors, and thus no lines connecting to it from above, its height is zero, and the height of the level beneath that is 1, and so on.

#include <math.h>

int GetMaxNodes(int height) {
 return pow(2, height+1) - 1;
}


int main()
{

 for (int i = 0; i < 5; i++) {
 printf("A binary tree graph of height %d will have a maximum of %d nodes\n",
 i, GetMaxNodes(i));
 }

 return 0;
}

A binary tree can be implemented as either an array of nodes or a linked list. The data stored in a node can be either simple or itself a structure.

To implement a binary tree as an array, we will set each node to be a struct with elements consisting of the left child, the right child, and the node data. In this scheme, the zero-indexed node structure is the root node, and a special named constant value LEAF is used to indicate that there is no child.

If we were to create a tree graph were each node only had a left child, we would in fact end up with a linear list. We will do exactly this.

#include <stdlib.h>
#include <math.h>
#include <time.h>

#define ROOT 0
#define LEAF -1

struct structNode {
	double dData;
	int leftChildIndex;
	int rightChildIndex;
};


void InitializeNode(structNode *node, double dValue);
void PrintNode(const structNode *node);

int main()
{
 const int Num_Nodes = 7;
 int iCtr;
 srand(time(NULL));

 struct structNode TreeGraph[Num_Nodes];

 for (iCtr = 0; iCtr < Num_Nodes - 1; iCtr++) {
 InitializeNode(&TreeGraph[iCtr], (rand() / (double)rand()));
 TreeGraph[iCtr].leftChildIndex = iCtr + 1;
 }
 
 InitializeNode(&TreeGraph[Num_Nodes-1], (rand() / (double)rand()));

 for (iCtr = 0; iCtr < Num_Nodes; iCtr++) {
 PrintNode(&TreeGraph[iCtr]);
 }

 return 0;
}

void InitializeNode(structNode *node, double dValue) {
	node->dData = dValue;
	node->leftChildIndex = LEAF;
	node->rightChildIndex = LEAF;
}

void PrintNode(const structNode *node) {
	printf("Node Value: %f", node->dData);
	if (node->leftChildIndex != LEAF) {
		printf("\t Left Child = %d", node->leftChildIndex);
	}
	else {
		printf("\t Left Child = LEAF");
	}

	if (node->rightChildIndex != LEAF) {
		printf("\t Rigth Child = %d", node->rightChildIndex);
	}
	else {
		printf("\t Right Child = LEAF");
	}

	printf("\n");
}
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