Binary Tree
Binary Tree is defined as a tree data structure where each node has at most 2 children. Since each element in a binary tree can have only 2 children, we typically name them the left and right child. The structure is recursive in nature, meaning that each subtree is also a binary tree.
Binary Tree Representation
A Binary tree is represented by a pointer to the topmost node (commonly known as the “root”) of the tree. If the tree is empty, then the value of the root is NULL. Each node of a Binary Tree contains the following parts:
DataPointer to left child
Pointer to right child
Below is a simple representation of a binary tree using C with a linked structure (node-based representation). In this example, each node contains an integer key, a left child pointer (left), and a right child pointer (right):
struct Node
{
int key;
struct Node* left;
struct Node* right;
};
Array Representation of Binary Tree
In the array representation of a binary tree, the elements of the tree are stored in an array in a way that preserves the hierarchical structure of the tree. Here's a common way to represent a binary tree using an array:
For a binary tree where the array index starts from 0:
For any node at index i, its left child is at index 2i + 1, and its right child is at index 2i + 2.The parent of a node at index i is at index (i - 1) / 2 (integer division).
Construct a binary tree from the following elements arranged in an array A[1:15] as:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F G H
C Implementation- Tree Representation using Array
*******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
int treeSize = 7; // Assuming 7 nodes in the tree
// Function to print the array representation of a binary tree
void printArrayRepresentation(int tree[], int n) {
printf("Array Representation of Binary Tree: ");
for (int i = 0; i < n; i++) {
if (tree[i] != -1) {
printf("%d ", tree[i]);
} else {
printf("- ");
}
}
printf("\n");
}
// Function to set a node at a specific index in the binary tree
void setNode(int tree[], int index, int value) {
tree[index] = value;
}
// Function to set the left child of a node at a specific index
void setLeftChild(int tree[], int parentIndex, int value) {
if (0<=parentIndex<=treeSize)
{
int leftChildIndex = 2 * parentIndex + 1;
if (leftChildIndex < treeSize) {
setNode(tree, leftChildIndex, value);
} else {
printf("Left child index out of bounds.\n");
}
}
else
printf("Invalid Parent Index");
}
// Function to set the right child of a node at a specific index
void setRightChild(int tree[], int parentIndex, int value) {
if (0<=parentIndex<=treeSize)
{
int rightChildIndex = 2 * parentIndex + 2;
if (rightChildIndex < treeSize) {
setNode(tree, rightChildIndex, value);
} else {
printf("Right child index out of bounds.\n");
}
}
else
printf("Invalid Parent Index");
}
int main() {
// Example binary tree
// 1
// / \
// 2 3
// / \ \
// 4 5 6
int binaryTree[] = {-1, -1, -1, -1, -1, -1, -1}; // Initialize with -1 for empty nodes
// Set nodes
setNode(binaryTree, 0, 1);
setNode(binaryTree, 1, 2);
setNode(binaryTree, 2, 3);
// Set left and right children
setLeftChild(binaryTree, 1, 4);
setRightChild(binaryTree, 1, 5);
setRightChild(binaryTree, 2, 6);
// Print array representation
printArrayRepresentation(binaryTree, treeSize);
return 0;
}
A full binary tree (sometimes referred to as a proper, plane, or strict binary tree) is a tree in which every node has either 0 or 2 children.
A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes at the last level h. A perfect tree is therefore always complete but a complete tree is not always perfect. Some authors use the term complete to refer instead to a perfect binary tree as defined above, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree. A complete binary tree can be efficiently represented using an array.
fig: A complete binary free that is not full
Complete binary trees are well-balanced. This property ensures that the height of the tree is minimized, leading to more efficient operations
Complete binary trees are commonly used as the underlying structure for heaps, such as binary heaps and binary search heaps. These structures are efficient for priority queue implementations.
C Implementation- Binary Tree using Linked Representation
/*******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
// Definition of a binary tree node
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// Function to create a new node with a given data value
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Function to perform an in-order traversal of the binary tree
void inOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
int main() {
// Creating a binary tree
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
// Performing an in-order traversal
printf("In-order Traversal: ");
inOrderTraversal(root);
printf("\n");
// Remember to free allocated memory
// (This is a simple example; in practice, memory management needs to be handled appropriately)
return 0;
}
Output:
In-order Traversal: 4 2 5 1 3
Comments
Post a Comment