A tree data structure is a hierarchical nonlinear structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes.
- Important terminologies
- Types of trees
- Heights of a Binary Tree
- The ADT Binary Tree implementations
- Useful videos
- Useful articles
- For practice
- Parent Node: The node which is a predecessor of a node is called the parent node of that node.
- Child Node: The node which is the immediate successor of a node is called the child node of that node.
- Root Node: The topmost node of a tree or the node which does not have any parent node is called the root node.
A non-empty tree must contain exactly one root node and exactly one path from the root to all other nodes of the tree.
- Leaf Node or External Node: The nodes which do not have any child nodes are called leaf nodes.
- Ancestor of a Node:* Any predecessor nodes on the path of the root to that node are called Ancestors of that node.
- Descendant: A node x is a descendant of another node y if and only if y is an ancestor of x.
- Sibling: Children of the same parent node are called siblings.
- Level of a node: The count of edges on the path from the root node to that node. The root node has level 0.
- Internal node: A node with at least one child is called Internal Node.
- Neighbour of a Node: Parent or child nodes of that node are called neighbors of that node.
- Subtree: Any node of the tree along with its descendant.
Generic trees are a collection of nodes where each node is a data structure that consists of records and a list of references to its children(duplicate references are not allowed). Unlike the linked list, each node stores the address of multiple nodes. Every node stores address of its children and the very first node’s address will be stored in a separate pointer called root.
The Generic trees are the N-ary trees which have the following properties:
- Many children at every node.
- The number of nodes for each node is not known in advance.
For more info
A binary Tree is defined as a Tree data structure with 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.
Types of BTs:
- Full BT (based on number of nodes)
all nodes that are at a level less than h have two children each.
- Complete BT (based on levels completion)
A complete binary tree of height h is a binary tree that is full down to level h – 1, with level h filled in from left to right.
- Balanced BT (based on levels completion)
A binary tree is height balanced, or simply balanced, if the height of any node’s right sub-tree differs from the height of the node’s left subtree by no more than 1.
for a BT with n nodes
- Max height :
- min height --> Fill each level of tree as completely as possible
for a BT with height h
- max number of nodes :
- min number of nodes :
template <typename T>
class BinaryNode
{
private:
T item; // Data portion
BinaryNode<T>* leftChildPtr; // Pointer to left child
BinaryNode<T>* rightChildPtr; // Pointer to right child
public:
BinaryNode();
BinaryNode(const T& anItem, BinaryNode<T>* leftPtr = nullptr, BinaryNode<T>* rightPtr = nullptr);
void setItem(const T& anItem);
T getItem() const;
bool isLeaf() const;
BinaryNode<T>* getLeftChildPtr() const;
BinaryNode<T>* getRightChildPtr() const;
void setLeftChildPtr(BinaryNode<T>* leftPtr);
void setRightChildPtr(BinaryNode<T>* rightPtr);
};
#include "BinaryNode.h"
template <typename T>
class BinaryTreeInterface
{
public:
/** Tests whether this binary tree is empty.
@return True if the binary tree is empty, or false if not. */
virtual bool isEmpty() const = 0;
/** Gets the height of this binary tree.
@return The height of the binary tree. */
virtual int getHeight() const = 0;
/** Gets the number of nodes in this binary tree.
@return The number of nodes in the binary tree. */
virtual int getNumberOfNodes() const = 0;
/** Gets the data that is in the root of this binary tree.
@pre The binary tree is not empty.
@post The root’s data has been returned, and the binary tree is unchanged.
@return The data in the root of the binary tree. */
virtual T getRootData() const = 0;
/** Replaces the data item in the root of this binary tree
with the given data, if the tree is not empty. However, if the tree is empty,
inserts a new root node containing the given data into the tree.
@pre None.
@post The data in the root of the binary tree is as given.
@param newData The data for the root. */
virtual void setRootData(const T& newData) = 0;
/** Adds a new node containing the given data to this binary tree.
@param newData The data for the new node.
@post The binary tree contains a new node.
@return True if the addition is successful, or false not. **/
virtual bool add(const T & newData) = 0;
/** Removes the node containing the given data item from this binary tree.
@param data The data value to remove from the binary tree.
@return True if the removal is successful, or false not. */
virtual bool remove(const T & data) = 0;
/** Removes all nodes from this binary tree.*/
virtual void clear() = 0;
/** Gets a specific entry in this binary tree.
@post The desired entry has been returned, and the binary tree
is unchanged. If no such entry was found, an exception is thrown.
@param anEntry The entry to locate.
@return The entry in the binary tree that matches the given entry.
@throw NotFoundException if the given entry is not in the tree. */
virtual T getEntry(const T& anEntry) const throw(NotFoundException) = 0;
/** Tests whether a given entry occurs in this binary tree.
@post The binary search tree is unchanged.
@param anEntry The entry to find.
@return True if the entry occurs in the tree, or false if not. */
virtual bool contains(const T& anEntry) const = 0;
/** Traverses this binary tree in preorder (inorder, postorder) and
calls the function visit once for each node.
@param visit A client-defined function that performs an operation on
or with the data in each visited node. */
virtual void preorderTraverse(void visit(T&)) const = 0;
virtual void inorderTraverse(void visit(T&)) const = 0;
virtual void postorderTraverse(void visit(T&)) const = 0;
};- Functions implemented:
- header file:
Note
public ADT methods usually are not themselves recursive, but rather call a recursive method that is either private or protected. We do this to hide the underlying data structure from the client.
#include "BinaryTreeInterface.h"
#include "BinaryNode.h"
template <typename T>
class BinaryNodeTree : public BinaryTreeInterface<T>
{
public:
BinaryNode<T>* rootPtr;
BinaryNodeTree();
BinaryNodeTree(const T rootItem, const BinaryNodeTree<T>* leftTreePtr = nullptr, const BinaryNodeTree<T>* rightTreePtr = nullptr);
BinaryNodeTree(const BinaryNodeTree<T>& aTree); //copy constructor
virtual ~BinaryNodeTree();
//-------------
// Public Interface methods section
//-------------
bool isEmpty() const;
int getHeight() const;
int getNumberOfNodes() const;
T getRootData() const throw(PrecondViolatedExcep);
void setRootData(const T& newData);
bool add(const T& newData); // Adds a node
bool remove(const T& data); // Removes a node
void clear();
T getEntry(const T& anEntry) const throw(NotFoundException);
bool contains(const T& anEntry) const;
void preorderTraverse() const;
void inorderTraverse() const;
void postorderTraverse() const;
void levelorderTraverse() const;
//-------------
// Protected utility helper (recursive) methods
//-------------
int getHeightHelper(BinaryNode<T>* subTreePtr) const;
int getNumberOfNodesHelper(BinaryNode<T>* subTreePtr) const;
void destroyTree(BinaryNode<T>* subTreePtr);
BinaryNode<T>* balancedAdd(BinaryNode<T>* subTreePtr, BinaryNode<T>* newNodePtr);
BinaryNode<T>* removeValue(BinaryNode<T>* subTreePtr, const T target, bool& success);
BinaryNode<T>* moveValuesUpTree(BinaryNode<T>* subTreePtr);
BinaryNode<T>* findNode(BinaryNode<T>* treePtr, const T& target, bool& success) const;
BinaryNode<T>* copyTree(const BinaryNode<T>* treePtr) const;
void preorder(BinaryNode<T>* treePtr) const;
void inorder(BinaryNode<T>* treePtr) const;
void postorder(BinaryNode<T>* treePtr) const;
void levelorder(BinaryNode<T>* treePtr) const;
};uses a recursive preorder traversal to copy each node in the tree. By copying each node as soon as the traversal visits it, copyTree can make an exact copy of the original tree. To make the copy distinct from the original tree, the new nodes must be linked together by using new pointers. That is, you cannot simply copy the pointers in the nodes of the original tree. The result is a deep copy of the tree.
template <typename T>
inline BinaryNode<T>* BinaryNodeTree<T>::copyTree(const BinaryNode<T>* treePtr) const
{
BinaryNode<T>* newTreePtr = nullptr;
if (treePtr)
{
newTreePtr = new BinaryNode<T>*(treePtr->getItem());
newTreePtr->setLeftChildPtr(copyTree(treePtr->getLeftChildPtr()));
newTreePtr->setRightChildPtr(copyTree(treePtr->getRightChildPtr()));
}
return newTreePtr;
}The copy constructor then uses this method as follows:
template <typename T>
inline BinaryNodeTree<T>::BinaryNodeTree(const BinaryNodeTree<T>& aTree)
{
rootPtr = copyTree(aTree.rootPtr);
}the protected method destroyTree , which the destructor calls, uses a recursive postorder traversal to delete each node in the tree. A postorder traversal is appropriate here because you can delete a node only after you have fi rst traversed and deleted both of its subtrees.
template <typename T>
inline void BinaryNodeTree<T>::destroyTree(BinaryNode<T>* subTreePtr)
{
if (subTreePtr)
{
destroyTree(subTreePtr->getLeftChildPtr());
destroyTree(subTreePtr->getRightChildPtr());
delete subTreePtr;
}
}The destructor only needs to call it:
template<typename T>
inline BinaryNodeTree<T>::~BinaryNodeTree()
{
destroyTree(rootPtr);
}template<typename T>
inline int BinaryNodeTree<T>::getHeightHelper(BinaryNode<T>* subTreePtr) const
{
if (subTreePtr)
{
int left = getHeightHelper(subTreePtr->getLeftChildPtr());
int right = getHeightHelper(subTreePtr->getRightChildPtr());
return 1 + std::max(x, y);
}
else
return 0;
}while getHeight() just calls it
template<typename T>
inline int BinaryNodeTree<T>::getHeight() const
{
return getHeightHelper(rootPtr);
}similar to getting the height of a tree
template<typename T>
inline int BinaryNodeTree<T>::getNumberOfNodesHelper(BinaryNode<T>* subTreePtr) const
{
if (subTreePtr)
{
return 1 + getNumberOfNodesHelper(subTreePtr->getLeftChildPtr()) + getNumberOfNodes(subTreePtr->getRightChildPtr());
}
else
return 0;
}while getNumberOfNodes() just calls it
template<typename T>
inline int BinaryNodeTree<T>::getNumberOfNodes() const
{
getNumberOfNodesHelper(rootPtr);
}Adds the new node so that the resulting tree is balanced (to the shorter subtree)
template<typename T>
inline BinaryNode<T>* BinaryNodeTree<T>::balancedAdd(BinaryNode<T>* subTreePtr, BinaryNode<T>* newNodePtr)
{
if (subTreePtr == nullptr)
return newNodePtr;
BinaryNode<T>* leftPtr = subTreePtr->getLeftChildPtr();
BinaryNode<T>* rightPtr = subTreePtr->getRightChildPtr();
if (getHeightHelper(rightPtr) < getHeightHelper(leftPtr))
{
leftPtr = balancedAdd(leftPtr, newNodePtr);
subTreePtr->setLeftChildPtr(leftPtr);
}
else
{
rightPtr = balanced(rightPtr, newNodePtr);
subTreePtr->setRightChildPtr(rightPtr);
}
return subTreePtr;
}while The add(..) function creates the new node and calls it as follows:
template<typename T>
inline bool BinaryNodeTree<T>::add(const T& newData)
{
BinaryNode<T>* newNodePtr = new BinaryNode(newData);
rootPtr = balancedAdd(rootPtr, newNodePtr);
return true;
}
template<typename T>
inline void BinaryNodeTree<T>::preorder(BinaryNode<T>* treePtr) const
{
if (treePtr)
{
// Do something supposedly, print
std::cout << treePtr->getItem() << " ";
preorder(treePtr->getLeftChildPtr());
preorder(treePtr->getRightChildPtr());
}
}
template<typename T>
inline void BinaryNodeTree<T>::postorder(BinaryNode<T>* treePtr) const
{
if (treePtr)
{
postorder(treePtr->getLeftChildPtr());
postorder(treePtr->getRightChildPtr());
// Do something supposedly, print
std::cout << treePtr->getItem() << " ";
}
}
template<typename T>
inline void BinaryNodeTree<T>::inorder(BinaryNode<T>* treePtr) const
{
if (treePtr)
{
inorder(treePtr->getLeftChildPtr());
// Do something supposedly, print
std::cout << treePtr->getItem() << " ";
inorder(treePtr->getRightChildPtr());
}
}while the three public traversal functions just call them
A queue is needed to store the address of the skipped nodes.
template<typename T>
inline void BinaryNodeTree<T>::levelorder(BinaryNode<T>* treePtr) const
{
std::queue<BinaryNode<T>*> Nodesqueue;
Nodesqueue.push(rootPtr);
while (!Nodesqueue.empty())
{
BinaryNode<T>* currentPtr = Nodesqueue.front();
// Do something supposedly, print
std::cout << currentPtr->getItem() << " ";
if (currentPtr->getLeftChildPtr())
Nodesqueue.push(currentPtr->getLeftChildPtr());
if (currentPtr->getRightChildPtr())
Nodesqueue.push(currentPtr->getRightChildPtr());
Nodesqueue.pop();
}
}