C Programming Data Structures Tree Terminology And Types Complete Guide

1. Understanding Tree Terminology

A tree data structure is a hierarchical structure where each node has zero or more child nodes, with one node designated as the root. Here are some essential terms used in tree data structures:

• Root: The topmost node in a tree which has no parent.
• Node: Each element in the tree is called a node.
• Parent Node: A node which has one or more children.
• Child Node: A node which has a parent (one above it).
• Leaf Node: A node which does not have any children.
• Siblings: Nodes that have the same parent.
• Ancestor: A parent of a node or parent of the parent, and so on. Every node except the root has an ancestor.
• Descendant: A node which is directly or indirectly below a given node.
• Subtree: Any set of nodes in a tree that includes a node and all its descendants.
• Height: The height of a node is the number of edges on the longest path from the node to a leaf. The height of the tree is the height of the root.
• Depth: The depth of a node is the number of edges from the root node to the node itself. The depth of the root is 0.

Example Structure for a Binary Tree Node

Let's start by defining a basic structure for a binary tree node in C.

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

// Define a structure for a tree node
struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

// Function to create a new tree node
struct TreeNode* createNode(int value) {
    struct TreeNode *newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {
    // Create root node
    struct TreeNode *root = createNode(1);

    // Create left child of root
    root->left = createNode(2);

    // Create right child of root
    root->right = createNode(3);

    // Create children of left child (root->left)
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    // Create children of right child (root->right)
    root->right->left = createNode(6);
    root->right->right = createNode(7);

    printf("Example Binary Tree structure created.\n");
    printf("Root: %d\n", root->data);
    printf("Left Child of Root: %d\n", root->left->data);
    printf("Right Child of Root: %d\n", root->right->data);
    printf("Left Child of Left Child of Root (2): %d\n", root->left->left->data);
    printf("Right Child of Left Child of Root (2): %d\n", root->left->right->data);
    printf("Left Child of Right Child of Root (3): %d\n", root->right->left->data);
    printf("Right Child of Right Child of Root (3): %d\n", root->right->right->data);

    // Free memory allocated for nodes
    free(root->left->left);
    free(root->left->right);
    free(root->right->left);
    free(root->right->right);
    free(root->left);
    free(root->right);
    free(root);

    return 0;
}

2. Types of Trees

There are several types of trees based on their properties. Let's cover some common ones.

a) Binary Tree

Every node has at most two children.

• Full Binary Tree: Every node other than the leaves has two children.
• Complete Binary Tree: All levels are completely filled except possibly the last level. In the last level, the nodes are as far left as possible.
• Perfect Binary Tree: All levels are completely filled including the last level.
• Balanced Binary Tree: The difference between heights of left and right subtrees is not more than one for all nodes in the tree.
• Skewed Binary Tree: Can be either left-skewed (all nodes have only the left child) or right-skewed (all nodes have only the right child).

Example: Simple Binary Tree

Let’s implement a simple binary tree and traverse it using Pre-order, In-order, and Post-order techniques.

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

// Define a structure for a tree node
struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

// Function to create a new tree node
struct TreeNode* createNode(int value) {
    struct TreeNode *newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Pre-order traversal (Root - Left - Right)
void preOrderTraversal(struct TreeNode *node) {
    if (node == NULL)
        return;

    // Visit root
    printf("%d ", node->data);

    // Traverse left subtree
    preOrderTraversal(node->left);

    // Traverse right subtree
    preOrderTraversal(node->right);
}

// In-order traversal (Left - Root - Right)
void inOrderTraversal(struct TreeNode *node) {
    if (node == NULL)
        return;

    // Traverse left subtree
    inOrderTraversal(node->left);

    // Visit root
    printf("%d ", node->data);

    // Traverse right subtree
    inOrderTraversal(node->right);
}

// Post-order traversal (Left - Right - Root)
void postOrderTraversal(struct TreeNode *node) {
    if (node == NULL)
        return;

    // Traverse left subtree
    postOrderTraversal(node->left);

    // Traverse right subtree
    postOrderTraversal(node->right);

    // Visit root
    printf("%d ", node->data);
}

int main() {
    // Create root node
    struct TreeNode *root = createNode(1);

    // Create left child of root
    root->left = createNode(2);

    // Create right child of root
    root->right = createNode(3);

    // Create children of left child (root->left)
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    // Create children of right child (root->right)
    root->right->left = createNode(6);
    root->right->right = createNode(7);

    printf("Pre-order Traversal: ");
    preOrderTraversal(root);
    printf("\n");

    printf("In-order Traversal: ");
    inOrderTraversal(root);
    printf("\n");

    printf("Post-order Traversal: ");
    postOrderTraversal(root);
    printf("\n");

    // Free memory allocated for nodes
    free(root->left->left);
    free(root->left->right);
    free(root->right->left);
    free(root->right->right);
    free(root->left);
    free(root->right);
    free(root);

    return 0;
}

b) Binary Search Tree (BST)

A binary search tree is a binary tree in which every node fits the following criteria:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a BST.

Example: Insertion and Search in BST

Here’s how you can insert elements into a BST and search for a specific element.

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

// Define a structure for a tree node
struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

// Function to create a new tree node
struct TreeNode* createNode(int value) {
    struct TreeNode *newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to insert a new node with given key in BST
struct TreeNode* insert(struct TreeNode *root, int value) {
    // If the tree is empty, return a new node
    if (root == NULL) {
        root = createNode(value);
        return root;
    }

    // Otherwise, recur down the tree
    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    // return the (unchanged) node pointer
    return root;
}

// Function to do inorder tree traversal (used to sort the data)
void inOrderTraversal(struct TreeNode *root) {
    if (root == NULL)
        return;

    inOrderTraversal(root->left);
    printf("%d ", root->data);
    inOrderTraversal(root->right);
}

// Function to search a given key in a BST. It returns NULL if key is not present.
struct TreeNode* search(struct TreeNode *root, int key) {
    // Base cases: root is null or key is present at root
    if (root == NULL || root->data == key)
        return root;

    // Key is greater than root's key
    if (root->data < key)
        return search(root->right, key);

    // Key is smaller than root's key
    return search(root->left, key);
}

int main() {
    struct TreeNode *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("Inorder traversal of the BST: ");
    inOrderTraversal(root);
    printf("\n");

    int key = 60;
    if (search(root, key)) {
        printf("Element %d found in BST\n", key);
    } else {
        printf("Element %d not found in BST\n", key);
    }

    // Free memory allocated for nodes
    free(root->left->left);
    free(root->left->right);
    free(root->left);
    free(root->right->left);
    free(root->right->right);
    free(root->right);
    free(root);

    return 0;
}

c) AVL Tree

AVL tree is a self-balancing Binary Search Tree where the difference between heights of left and right subtrees cannot be more than one for all nodes.

Let's create an AVL tree with insertion and balancing mechanisms.

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

// An AVL tree node
struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
    int height;
};

// A utility function to get the height of the tree
int height(struct TreeNode *node) {
    if (node == NULL)
        return 0;
    return node->height;
}

// A utility function to get maximum of two integers
int max(int a, int b) {
    return (a > b) ? a : b;
}

// A utility function to right rotate subtree rooted with y
struct TreeNode *rightRotate(struct TreeNode *y) {
    struct TreeNode *x = y->left;
    struct TreeNode *T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

    // Update heights
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // Return new root
    return x;
}

// A utility function to left rotate subtree rooted with x
struct TreeNode *leftRotate(struct TreeNode *x) {
    struct TreeNode *y = x->right;
    struct TreeNode *T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

    // Update heights
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    // Return new root
    return y;
}

// Get Balance factor of node N
int getBalanceFactor(struct TreeNode *node) {
    if (node == NULL)
        return 0;
    return height(node->left) - height(node->right);
}

// Utility function to create a new BST node
struct TreeNode *createNode(int data) {
    struct TreeNode *newNode = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    newNode->height = 1; // new node is initially added at leaf
    return newNode;
}

// Recursive function to insert a data in the subtree rooted with node and returns the new root of the subtree.
struct TreeNode *insert(struct TreeNode *root, int data) {
    if (root == NULL)
        return (createNode(data));

    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    else // Equal datas are not allowed in BST
        return root;

    // Update height of this ancestor node
    root->height = 1 + max(height(root->left), height(root->right));

    // Get the balance factor of this ancestor node to check whether this node became unbalanced
    int balance = getBalanceFactor(root);

    // If this node becomes unbalanced, then there are 4 cases

    // Left Left Case
    if (balance > 1 && data < root->left->data)
        return rightRotate(root);

    // Right Right Case
    if (balance < -1 && data > root->right->data)
        return leftRotate(root);

    // Left Right Case
    if (balance > 1 && data > root->left->data) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // Right Left Case
    if (balance < -1 && data < root->right->data) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    // Return the (unchanged) node pointer
    return root;
}

// A utility function to print preorder traversal of the tree
void preOrderTraversal(struct TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preOrderTraversal(root->left);
        preOrderTraversal(root->right);
    }
}

int main() {
    struct TreeNode *root = NULL;

    /* Constructing tree given in the above figure */
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    /* The constructed AVL Tree would be
             30
            /  \
          20   40
         / \     \
        10 25    50
    */

    printf("Preorder traversal of the constructed AVL tree is \n");
    preOrderTraversal(root);
    printf("\n");

    // Free memory allocated for nodes
    free(root->left->left);
    free(root->left->right);
    free(root->left);
    free(root->right->right);
    free(root->right);
    free(root);

    return 0;
}

d) Red-Black Tree

Red-Black Tree is another self-balancing binary search tree which maintains the tree balanced during insertions and deletions, providing faster lookup times.

Example: Basic Node Structure of Red-Black Tree

Let’s define the structure. Note that implementing full functionalities like insert, delete, etc., for a Red-Black tree is quite complex and beyond the scope of a basic example.

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

typedef enum { RED, BLACK } Color;

// Define a structure for a tree node
struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
    struct TreeNode *parent;
    Color color;
};

// Function to create a new tree node
struct TreeNode* createNode(int value, Color col) {
    struct TreeNode *newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->parent = NULL;
    newNode->color = col;
    return newNode;
}

void leftRotate(struct TreeNode **T, struct TreeNode *x) {
    struct TreeNode *y = x->right; // Set y
    x->right = y->left; // Turn y’s left subtree into x’s right subtree
    if (y->left != NULL)
        y->left->parent = x;
    y->parent = x->parent; // Link x’s parent to y
    if (x->parent == NULL)
        *T = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x; // Put x on y’s left
    x->parent = y;
}

void rightRotate(struct TreeNode **T, struct TreeNode *y) {
    struct TreeNode *x = y->left; // Set x
    y->left = x->right; // Turn x’s right subtree into y’s left subtree
    if (x->right != NULL)
        x->right->parent = y;
    x->parent = y->parent; // Link y’s parent to x
    if (y->parent == NULL)
        *T = x;
    else if (y == y->parent->right)
        y->parent->right = x;
    else
        y->parent->left = x;
    x->right = y; // Put y on x’s right
    y->parent = x;
}

// To be completed: Insert and Balance functions

void printTree(struct TreeNode *root) {
    if (root == NULL) return;
    printf("%d: [%s]\n", root->data, root->color == RED ? "RED" : "BLACK");
    printTree(root->left);
    printTree(root->right);
}

int main() {
    struct TreeNode *root = NULL;

    // We need to implement functions like insert and balance here which is quite complex
    root = createNode(10, BLACK);

    printf("Binary Tree Example:\n");
    printTree(root);

    // Free allocated memory
    free(root);

    return 0;
}

Conclusion

This guide covered essential tree terminologies, basic binary tree structure, and examples of different kinds of trees such as binary search tree and AVL tree. Implementing more sophisticated tree structures like Red-Black Trees involves more intricate algorithms for maintaining balance which were simplified here. With these examples, you should now have a foundational understanding of how to work with trees in C programming.

Additional Notes

• Always free dynamically allocated memory to avoid memory leaks.
• Recursive functions play a crucial role in traversing through the tree.
• Balancing is critical for achieving O(log n) operations in self-balancing trees like AVL and Red-Black Trees.