Trees | Data Structures | Cplusplus Tutorial

Introduction to Trees

A tree is a widely used abstract data type that simulates a hierarchical tree structure with a set of connected nodes. Each node in a tree has zero or more child nodes, and a node without any children is called a leaf node. Trees are used to represent hierarchical relationships, such as organizational structures, file systems, and more.

Basic Terminology

Here are some key terms related to trees:

Node: A fundamental part of a tree that contains data and may have links to other nodes.
Root: The topmost node of a tree. It is the ancestor of all other nodes.
Child: A node that is a descendant of another node.
Parent: A node that has one or more children.
Leaf: A node that does not have any children.
Subtree: A tree consisting of a node and its descendants.
Depth: The length of the path from the root to a node.
Height: The length of the path from a node to the deepest leaf.

Types of Trees

There are several types of trees used in computer science:

Binary Tree: A tree where each node has at most two children.
Binary Search Tree (BST): A binary tree where the left child contains only nodes with values less than the parent node, and the right child contains only nodes with values greater than the parent node.
AVL Tree: A self-balancing binary search tree where the difference between the heights of the left and right subtrees cannot be more than one.
Red-Black Tree: A self-balancing binary search tree where each node contains an extra bit for denoting the color of the node, either red or black.
B-Tree: A self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

Binary Tree Implementation in C++

Below is a simple example of a binary tree implementation in C++:


#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

class BinaryTree {
public:
    Node* root;
    BinaryTree() : root(nullptr) {}

    void insert(int value) {
        root = insertRec(root, value);
    }

    void inorderTraversal() {
        inorderRec(root);
    }

private:
    Node* insertRec(Node* node, int value) {
        if (node == nullptr) {
            return new Node(value);
        }
        if (value < node->data) {
            node->left = insertRec(node->left, value);
        } else if (value > node->data) {
            node->right = insertRec(node->right, value);
        }
        return node;
    }

    void inorderRec(Node* node) {
        if (node != nullptr) {
            inorderRec(node->left);
            cout << node->data << " ";
            inorderRec(node->right);
        }
    }
};

int main() {
    BinaryTree tree;
    tree.insert(50);
    tree.insert(30);
    tree.insert(20);
    tree.insert(40);
    tree.insert(70);
    tree.insert(60);
    tree.insert(80);

    cout << "Inorder traversal of the binary tree: ";
    tree.inorderTraversal();
    return 0;
}

The above code defines a binary tree with an insertion operation and an inorder traversal method.

Binary Search Tree (BST) Operations

Binary Search Trees (BST) have several key operations:

Insertion: Adding a new node in its correct position to maintain the BST property.
Deletion: Removing a node while maintaining the BST property.
Search: Finding a node with a specific value.

Here is an example of a search operation in a BST:


bool search(Node* root, int key) {
    if (root == nullptr) {
        return false;
    }
    if (root->data == key) {
        return true;
    }
    if (key < root->data) {
        return search(root->left, key);
    }
    return search(root->right, key);
}

The above function recursively searches for a key in the BST.

Tree Traversal Methods

Tree traversal refers to the process of visiting all the nodes in a tree. There are several types of tree traversal methods:

Inorder Traversal: Visit the left subtree, root node, and then the right subtree.
Preorder Traversal: Visit the root node, left subtree, and then the right subtree.
Postorder Traversal: Visit the left subtree, right subtree, and then the root node.

Here is an example of preorder traversal in C++:


void preorder(Node* node) {
    if (node == nullptr) {
        return;
    }
    cout << node->data << " ";
    preorder(node->left);
    preorder(node->right);
}

AVL Tree Example

An AVL tree is a self-balancing binary search tree. Here is a simple example of how to maintain balance in an AVL tree:


int height(Node* N) {
    if (N == nullptr)
        return 0;
    return N->height;
}

int max(int a, int b) {
    return (a > b)? a : b;
}

Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    x->right = y;
    y->left = T2;

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

    return x;
}

Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    y->left = x;
    x->right = T2;

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

    return y;
}

int getBalance(Node* N) {
    if (N == nullptr)
        return 0;
    return height(N->left) - height(N->right);
}

Node* insert(Node* node, int key) {
    if (node == nullptr)
        return(new Node(key));

    if (key < node->data)
        node->left = insert(node->left, key);
    else if (key > node->data)
        node->right = insert(node->right, key);
    else
        return node;

    node->height = 1 + max(height(node->left), height(node->right));

    int balance = getBalance(node);

    if (balance > 1 && key < node->left->data)
        return rightRotate(node);

    if (balance < -1 && key > node->right->data)
        return leftRotate(node);

    if (balance > 1 && key > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if (balance < -1 && key < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

The above code includes functions for rotating nodes and maintaining balance in an AVL tree.

Conclusion

Trees are a fundamental data structure in computer science, providing a versatile way to represent hierarchical data. Understanding the various types of trees and their operations is crucial for solving complex computational problems efficiently. This tutorial covered the basics of trees, different types of trees, and some key operations and traversal methods in the context of the C++ language.

Trees in Data Structures