Skip to main content

Problem Solving with Algorithms and Data Structures using C++: The PreTeXt Interactive Edition

Section 8.4 Nodes and References

Our second method to represent a tree uses nodes and references. In this case we will define a class that has attributes for the root value, as well as the left and right subtrees. Since this representation more closely follows the object-oriented programming paradigm, we will continue to use this representation for the remainder of the chapter.
Using nodes and references, we might think of the tree as being structured like the one shown in Figure 8.4.1.
Illustration of a binary tree structure with three levels. The top level shows a single node labeled ’a’ with two pointers ’left’ and ’right’. The second level has two nodes: ’b’ on the left with its own ’left’ and ’right’ pointers, and ’c’ on the right with pointers also labeled ’left’ and ’right’. The third level shows three nodes: ’d’ is the left child of ’b’ with ’left’ and ’right’ pointers; ’e’ is the right child of ’b’ with pointers labeled ’left’ and ’right’; ’f’ is the right child of ’c’ also with ’left’ and ’right’ pointers. Each pointer is represented by an arrow indicating the direction of the reference.
Figure 8.4.1. A Simple Tree Using a Nodes and References Approach.
We will start out with a simple class definition for the nodes and references approach as shown in Task 8.4.1.a. The important thing to remember about this representation is that the attributes left and right will become references to other instances of the BinaryTree class. For example, when we insert a new left child into the tree we create another instance of BinaryTree and modify self.leftChild in the root to reference the new tree.

Exploration 8.4.1. Nodes and References BinaryTree.

(a) C++ Implementation. 

#include <iostream>
#include <cstdlib>
using namespace std;

class BinaryTree {
private:
    char key;
    BinaryTree *leftChild;
    BinaryTree *rightChild;

public:
    BinaryTree(char rootObj){
        this->key = rootObj;
        this->leftChild = NULL;
        this->rightChild = NULL;
    }
};

(b) Python Implementation. 

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None
Notice that in Task 8.4.1.a, the constructor function expects to get some kind of object to store in the root. Just like you can store any object you like in an array, the root object of a tree can be a reference to any object. For our early examples, we will store the name of the node as the root value. Using nodes and references to represent the tree in Figure 8.4.1, we would create six instances of the BinaryTree class.
Next let’s look at the functions we need to build the tree beyond the root node. To add a left child to the tree, we will create a new binary tree object and set the left attribute of the root to refer to this new object. The code for insertLeft is shown in Task 8.4.2.a.

Exploration 8.4.2. insertLeft.

(a) C++ Implementation. 

void insertLeft(char newNode){
    if (this->leftChild == NULL){
        this->leftChild = new BinaryTree(newNode);
    }
    else {
        BinaryTree *t = new BinaryTree(newNode);
        t->leftChild = this->leftChild;
        this->leftChild = t;
    }
}

(b) Python Implementation. 

def insertLeft(self,newNode):
    if self.leftChild == None:
        self.leftChild = BinaryTree(newNode)
    else:
        t = BinaryTree(newNode)
        t.leftChild = self.leftChild
        self.leftChild = t
We must consider two cases for insertion. The first case is characterized by a node with no existing left child. When there is no left child, simply add a node to the tree. The second case is characterized by a node with an existing left child. In the second case, we insert a node and push the existing child down one level in the tree. The second case is handled by the else statement on line 4 of Task 8.4.2.a.
The code for insertRight must consider a symmetric set of cases. There will either be no right child, or we must insert the node between the root and an existing right child. The insertion code is shown in Task 8.4.3.a.

Exploration 8.4.3. insertRight.

(a) C++ Implementation. 

void insertRight(char newNode){
    if (this->rightChild == NULL){
        this->rightChild = new BinaryTree(newNode);
    }
    else {
        BinaryTree *t = new BinaryTree(newNode);
        t->rightChild = this->rightChild;
        this->rightChild = t;
    }
}

(b) Python Implementation. 

def insertRight(self,newNode):
    if self.rightChild == None:
        self.rightChild = BinaryTree(newNode)
    else:
        t = BinaryTree(newNode)
        t.rightChild = self.rightChild
        self.rightChild = t
To round out the definition for a simple binary tree data structure, we will write accessor methods (see Task 8.4.4.a) for the left and right children, as well as the root values.

Exploration 8.4.4. Accessor Methods for BinaryTree.

(a) C++ Implementation. 

BinaryTree *getRightChild(){
    return this->rightChild;
}

BinaryTree *getLeftChild(){
    return this->leftChild;
}

void setRootVal(char obj){
    this->key = obj;
}

char getRootVal(){
    return this->key;
}

(b) Python Implementation. 

def getRightChild(self):
    return self.rightChild

def getLeftChild(self):
    return self.leftChild

def setRootVal(self,obj):
    self.key = obj

def getRootVal(self):
    return self.key
Now that we have all the pieces to create and manipulate a binary tree, let’s use them to check on the structure a bit more. Let’s make a simple tree with node a as the root, and add nodes b and c as children. Task 8.4.5.a creates the tree and looks at the some of the values stored in key, left, and right. Notice that both the left and right children of the root are themselves distinct instances of the BinaryTree class. As we said in our original recursive definition for a tree, this allows us to treat any child of a binary tree as a binary tree itself.

Exploration 8.4.5. Accessor Methods for BinaryTree.

(a) C++ Implementation.

(b) Python Implementation.

Reading Questions Reading Question

1.

    Which data structure resembles the above implementation of a tree?
  • Hash Table
  • Incorrect, a hash table maps key, value pairs for quick access. To access an item in our tree, we have to go through everything before it.
  • Linked List
  • Correct, this tree is essentially a linked list connecting other linked lists
  • Queue
  • Incorrect, a queue is good for putting data in to fit a FIFO sequence
  • Stack
  • Incorrect, a stack is good for putting data in to fit a LIFO sequence
You have attempted of activities on this page.
PrevTopNext