A Strictly Binary Tree, also known as a Full Binary Tree, is a special type of binary tree where:
- Each node has either 0 or 2 children.
- No node has only one child.
- If a node has children, it must have both a left and a right child.
This structure ensures a well-defined branching pattern, which has implications for the number of nodes, tree height, and leaf nodes.
Properties of a Strictly Binary Tree
- If there are n internal nodes, the number of leaf nodes is n+1n + 1n+1.
- The total number of nodes in a strictly binary tree is 2n+12n + 12n+1, where nnn is the number of internal nodes.
- The height hhh of the tree is determined by the number of levels in it.
- If the height of the tree is hhh, the maximum number of nodes is 2h+1−12^{h+1} – 12h+1−1.
Implementation of a Strictly Binary Tree in C
The implementation of a strictly binary tree involves:
- Structuring nodes such that each internal node has exactly two children.
- Verifying the strictly binary property during operations like insertion or construction.
1. Defining a Node
The structure of a node in C:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
- data: Stores the value of the node.
- left: Pointer to the left child.
- right: Pointer to the right child.
2. Creating a New Node
A function to create a new node dynamically:
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf(“Memory allocation failed.\n”);
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
3. Constructing a Strictly Binary Tree
To maintain the strictly binary property, ensure that every node inserted into the tree has both left and right children or is a leaf node. Here, we construct a strictly binary tree manually.
Node* constructStrictlyBinaryTree() {
Node* root = createNode(1); // Root node
root->left = createNode(2); // Left child
root->right = createNode(3); // Right child
root->left->left = createNode(4); // Left subtree
root->left->right = createNode(5);
root->right->left = createNode(6); // Right subtree
root->right->right = createNode(7);
return root;
}
4. Traversing the Strictly Binary Tree
Traversal methods for strictly binary trees are the same as for general binary trees.
- In-order Traversal: Left → Root → Right
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf(“%d “, root->data);
inorderTraversal(root->right);
}
}
- Pre-order Traversal: Root → Left → Right
void preorderTraversal(Node* root) {
if (root != NULL) {
printf(“%d “, root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
- Post-order Traversal: Left → Right → Root
void postorderTraversal(Node* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf(“%d “, root->data);
}
}
5. Main Function
A demonstration of constructing and traversing a strictly binary tree:
int main() {
Node* root = constructStrictlyBinaryTree();
printf(“In-order Traversal: “);
inorderTraversal(root);
printf(“\n”);
printf(“Pre-order Traversal: “);
preorderTraversal(root);
printf(“\n”);
printf(“Post-order Traversal: “);
postorderTraversal(root);
printf(“\n”);
return 0;
}
Output
For the tree structure:
markdown
Copy code
1
/ \
2 3
/ \ / \
4 5 6 7
The output will be:
In-order Traversal: 4 2 5 1 6 3 7
Pre-order Traversal: 1 2 4 5 3 6 7
Post-order Traversal: 4 5 2 6 7 3 1
Strictly Binary Tree Validation
To verify if a binary tree is strictly binary:
int isStrictlyBinary(Node* root) {
if (root == NULL) {
return 1; // Empty tree is strictly binary
}
if ((root->left == NULL && root->right != NULL) ||
(root->left != NULL && root->right == NULL)) {
return 0; // Node has only one child
}
return isStrictlyBinary(root->left) && isStrictlyBinary(root->right);
}
Use this function in the main() function:
if (isStrictlyBinary(root)) {
printf(“The tree is strictly binary.\n”);
} else {
printf(“The tree is not strictly binary.\n”);
}
Advantages of Strictly Binary Tree
- Ensures a balanced structure.
- Provides a predictable node arrangement.
Limitations
- Not suitable for dynamic data, as it requires specific properties.
- Manual maintenance of the structure is cumbersome in some cases.