Trees in C++

Data Structures and Algorithms with C++ is a course designed to help students understand the fundamentals of data structures and algorithms, such as stacks, queues, linked lists, and trees. In this article, we will focus on trees, exploring how to implement them in C++ and how to traverse, insert, and delete elements from them. By the end of this article, readers should have a full understanding of trees in C++, including how to traverse, insert, and delete elements from them.

Overview of Trees

A tree is a hierarchical data structure that consists of nodes that are connected by edges. Each node has a value and can have zero or more children. The topmost node is called the root of the tree. The nodes that are directly connected to the root are called the children of the root, and the nodes that are connected to the children are called the grandchildren of the root. This pattern continues down the tree.

The most common type of tree is a binary tree, which is a tree with a maximum of two children per node. A binary tree can be either a full binary tree, which means that every node has either zero or two children, or a complete binary tree, which means that all levels except the last are full and all nodes are as far left as possible in the last level.

Implementing Trees Using Classes

In order to create a binary tree in C++, we must first create a class that will represent the nodes in the tree. Each node will have a value and two pointers, one for the left child and one for the right child. The following is an example of how to create a Node class in C++:

class Node 
{ 
    public: 
        int data; 
        Node *left, *right; 
  
        Node(int data) 
        { 
            this->data = data; 
            left = right = NULL; 
        } 
};

Once we have created the Node class, we can create a Tree class that will create and manage the binary tree. The Tree class will have a root node and methods that can be used to traverse, insert, and delete elements from the tree. The following is an example of what a Tree class might look like in C++:

class Tree 
{ 
    public: 
        Node *root; 
  
        Tree() 
        { 
            root = NULL; 
        } 
  
        void insert(int data); 
        void delete(int data); 
        void traverse(); 
};

Traversing a Tree

In order to traverse a tree, we must visit each node and perform some action on it. There are three common ways to traverse a tree: pre-order, in-order, and post-order.

Pre-order traversal visits the root node first and then traverses the left subtree followed by the right subtree. We can implement pre-order traversal in C++ using the following code:

void Tree::preOrder(Node *node) 
{ 
    if (node == NULL) 
        return; 
  
    cout << node->data << " "; 
    preOrder(node->left);  
    preOrder(node->right); 
} 

In-order traversal visits the left subtree first, then the root node, and then the right subtree. We can implement in-order traversal in C++ using the following code:

void Tree::inOrder(Node *node) 
{ 
    if (node == NULL) 
        return; 
  
    inOrder(node->left);  
    cout << node->data << " "; 
    inOrder(node->right); 
} 

Post-order traversal visits the left subtree first, then the right subtree, and then the root node. We can implement post-order traversal in C++ using the following code:

void Tree::postOrder(Node *node) 
{ 
    if (node == NULL) 
        return; 
  
    postOrder(node->left);  
    postOrder(node->right); 
    cout << node->data << " "; 
} 

Inserting and Deleting Elements from a Tree

In order to insert an element into a tree, we first need to find the appropriate spot for the element. To do this, we start at the root node and compare the value of the node to the value of the element we want to insert. If the value of the node is greater than the value of the element, we move down the left subtree. If the value of the node is less than the value of the element, we move down the right subtree. We continue this process until we find a node that has no children, at which point we can insert the element.

We can implement this insertion algorithm in C++ using the following code:

void Tree::insert(int data) 
{ 
    Node *node = new Node(data); 
  
    if (root == NULL) 
        root = node;  
    else 
    { 
        Node *temp = root; 
        Node *parent; 
  
        while (true) 
        { 
            parent = temp; 
  
            if (data < temp->data) 
            { 
                temp = temp->left; 
  
                if (temp == NULL) 
                { 
                    parent->left = node; 
                    break; 
                } 
            } 
            else 
            { 
                temp = temp->right; 
  
                if (temp == NULL) 
                { 
                    parent->right = node; 
                    break; 
                } 
            } 
        } 
    } 
}

In order to delete an element from a tree, we must first find the element in the tree. To do this, we start at the root node and compare the value of the node to the value of the element we want to delete. If the value of the node is greater than the value of the element, we move down the left subtree. If the value of the node is less than the value of the element, we move down the right subtree. Once we find the element, we must delete it while preserving the structure of the tree.

We can implement this deletion algorithm in C++ using the following code:

void Tree::delete(int data) 
{ 
    Node *temp; 
    Node *parent; 
    bool isLeft = true; 
  
    // Find the node to delete 
    temp = root; 
  
    while (temp->data != data) 
    { 
        parent = temp; 
  
        if (data < temp->data) 
        { 
            isLeft = true; 
            temp = temp->left; 
        } 
        else 
        { 
            isLeft = false; 
            temp = temp->right; 
        } 
  
        if (temp == NULL) 
            return; 
    } 
  
    // Node to delete has no children 
    if (temp->left == NULL && temp->right == NULL) 
    { 
        if (temp == root) 
            root = NULL; 
        else if (isLeft) 
            parent->left = NULL; 
        else
            parent->right = NULL; 
    } 
  
    // Node to delete has one child 
    else if (temp->right == NULL) 
    { 
        if (temp == root) 
            root = temp->left; 
        else if (isLeft) 
            parent->left = temp->left; 
        else
            parent->right = temp->left; 
    } 
    else if (temp->left == NULL) 
    { 
        if (temp == root) 
            root = temp->right; 
        else if (isLeft) 
            parent->left = temp->right; 
        else
            parent->right = temp->right; 
    } 
  
    // Node to delete has two children 
    else 
    { 
        Node *successor = getSuccessor(temp); 
  
        if (temp == root) 
            root = successor; 
        else if (isLeft) 
            parent->left = successor; 
        else
            parent->right = successor; 
  
        successor->left = temp->left; 
    } 
  
    delete temp; 
}

Conclusion

In this article, we covered trees in C++, including how to implement them using classes, how to traverse them, how to insert and delete elements from them, and how to delete elements from them. With this knowledge, you should have a good understanding of how to work with trees in C++ and be able to create your own binary trees.

Exercises

int Tree::height(Node *node) 
{ 
    if (node == NULL) 
        return 0; 
  
    int leftHeight = height(node->left); 
    int rightHeight = height(node->right); 
  
    if (leftHeight > rightHeight) 
        return leftHeight + 1; 
    else
        return rightHeight + 1; 
} 

int Tree::countLeaves(Node *node) 
{ 
    if (node == NULL) 
        return 0; 
  
    if (node->left == NULL && node->right == NULL) 
        return 1; 
    else
        return countLeaves(node->left) + countLeaves(node->right); 
} 

int Tree::countNodesAtLevel(Node *node, int level) 
{ 
    if (node == NULL) 
        return 0; 
  
    if (level == 1) 
        return 1; 
    else
        return countNodesAtLevel(node->left, level-1) + 
               countNodesAtLevel(node->right, level-1); 
} 

int Tree::maxElement(Node *node) 
{ 
    if (node == NULL) 
        return INT_MIN; 
  
    int max = node->data; 
    int leftMax = maxElement(node->left); 
    int rightMax = maxElement(node->right); 
  
    if (leftMax > max) 
        max = leftMax; 
    if (rightMax > max) 
        max = rightMax; 
  
    return max; 
} 

int Tree::minElement(Node *node) 
{ 
    if (node == NULL) 
        return INT_MAX; 
  
    int min = node->data; 
    int leftMin = minElement(node->left); 
    int rightMin = minElement(node->right); 
  
    if (leftMin < min) 
        min = leftMin; 
    if (rightMin < min) 
        min = rightMin; 
  
    return min; 
}