Basic Binary Tree Operations in C
To implement binary tree operations in C, a queue is used for level - order traversal and checking if a tree is a complete binary tree (unlike C++ which may not need an external queue structure for some operations). Here are the core operations:
Constructing a Binary Tree Node
The CreateBinaryTree function builds a binary tree from a string (where # represents a null node) using recursion to create left and right sub - trees.
BinTreeNode* CreateBinaryTree(char* dataStr, int* index) {
if (dataStr[*index] == '#') {
(*index)++;
return NULL;
}
BinTreeNode* node = (BinTreeNode*)malloc(sizeof(BinTreeNode));
if (!node) {
perror("Memory allocation failed");
exit(EXIT_FAILURE);
}
node->data = dataStr[(*index)++];
node->left = CreateBinaryTree(dataStr, index);
node->right = CreateBinaryTree(dataStr, index);
return node;
}
Destroying the Binary Tree
The DestroyBinaryTree function recursive frees all nodes by first destroying the left and right sub - trees and then the current node.
void DestroyBinaryTree(BinTreeNode** rootRef) {
if (!rootRef) return;
DestroyBinaryTree(&((*rootRef)->left));
DestroyBinaryTree(&((*rootRef)->right));
free(*rootRef);
*rootRef = NULL;
}
Counting Nodes in the Binary Tree
The GetBinaryTreeSize function calculates the total number of nodes. For a null tree, it returns 0; otherwise, it sums the nodes in the left and right sub - trees and adds 1 for the current node.
int GetBinaryTreeSize(BinTreeNode* root) {
return root ? (GetBinaryTreeSize(root->left) + GetBinaryTreeSize(root->right) + 1) : 0;
}
Counting Leaf Nodes
A leaf node has no left or right children. The GetLeafNodeCount function uses recursion to count such nodes.
int GetLeafNodeCount(BinTreeNode* root) {
if (!root) return 0;
if (!root->left && !root->right) return 1;
return GetLeafNodeCount(root->left) + GetLeafNodeCount(root->right);
}
Counting Nodes at Level k
The GetLevelKNodeCount function counts the number of nodes at a specific level k. For level 1, it returns 1 (the root). For other levels, it sums the nodes in the left and right sub - trees at level k - 1.
int GetLevelKNodeCount(BinTreeNode* root, int k) {
if (!root) return 0;
if (k == 1) return 1;
return GetLevelKNodeCount(root->left, k - 1) + GetLevelKNodeCount(root->right, k - 1);
}
Finding a Node with Value x
The FindNode functon searches for a node with a given value. It first checks the current node, then recursively searches the left and right sub - trees.
BinTreeNode* FindNode(BinTreeNode* root, char target) {
if (!root) return NULL;
if (root->data == target) return root;
BinTreeNode* leftResult = FindNode(root->left, target);
if (leftResult) return leftResult;
return FindNode(root->right, target);
}
Pre - order Traversal
Pre - order traversal visits the root first, then the left sub - tree, and finally the right sub - tree.
void PreorderTraversal(BinTreeNode* node) {
if (!node) return;
printf("%c ", node->data);
PreorderTraversal(node->left);
PreorderTraversal(node->right);
}
In - order Traversal
In - order traversal visits the left sub - tree first, then the root, and then the right sub - tree.
void InorderTraversal(BinTreeNode* node) {
if (!node) return;
InorderTraversal(node->left);
printf("%c ", node->data);
InorderTraversal(node->right);
}
Post - order Traversal
Post - order traversal visits the left sub - tree first, then the right sub - tree, and finally the root.
void PostorderTraversal(BinTreeNode* node) {
if (!node) return;
PostorderTraversal(node->left);
PostorderTraversal(node->right);
printf("%c ", node->data);
}
Level - order Traversal
Level - order traversal visits nodes level by level. It uses a queue to enqueue nodes and process them in a first - in - first - out way.
void LevelorderTraversal(BinTreeNode* root) {
Queue q;
QueueInitialize(&q);
if (root) {
QueueEnqueue(&q, root);
}
while (!QueueIsEmpty(&q)) {
BinTreeNode* front = QueueFront(&q);
printf("%c ", front->data);
QueueDequeue(&q);
if (front->left) QueueEnqueue(&q, front->left);
if (front->right) QueueEnqueue(&q, front->right);
}
QueueDestroy(&q);
}
Check if Binary Tree is Complete
A complete binary tree has all levels filled except possibly the last, and nodes are filled from left to right. The IsCompleteBinaryTree function uses a queue to check this.
int IsCompleteBinaryTree(BinTreeNode* root) {
Queue q;
QueueInitialize(&q);
if (root) QueueEnqueue(&q, root);
int endFlag = 0;
while (!QueueIsEmpty(&q)) {
BinTreeNode* front = QueueFront(&q);
QueueDequeue(&q);
if (!front) {
endFlag = 1;
} else {
if (endFlag) return 0;
QueueEnqueue(&q, front->left);
QueueEnqueue(&q, front->right);
}
}
QueueDestroy(&q);
return 1;
}
Height of the Binary Tree
The height of a tree is the number of nodes along the longest path from the root to a leaf. The GetTreeHeight function recursively calculates the height of the left and right sub - trees and returns the maximum of the two plus 1.
int GetTreeHeight(BinTreeNode* root) {
if (!root) return 0;
int leftH = GetTreeHeight(root->left);
int rightH = GetTreeHeight(root->right);
return (leftH > rightH? leftH : rightH) + 1;
}
Source Code Structure
The code is split into three files:
binary_tree.h: Defines the binary tree node structure, function prototypes, and queue structure.binary_tree.c: Implements the binary tree operations.queue.c: Implements the queue operations (used for level - order traversal and complete tree check).test.c: Tests the binary tree operations with a sample enput.
Sample Input/Output
For the input string 123###45##6## (representing a specific binary tree):
- Leaf Node Count: 3
- Total Nodes: 6
- Nodes at Level 2: 2
- Pre - order Traversal:
1 2 3 4 5 6(actual output depends on the tree structure) - In - order Traversal:
3 2 1 5 4 6(actual output depends on the tree structure) - Post - order Traversal:
3 2 5 6 4 1(actual output depends on the tree structure) - Level - order Traversal:
1 2 4 3 5 6(actual output depends on the tree structure) - Is Complete: 1
- Tree Height: 3
