09.BINARY TREES

SYNTAX

template<class Type>
struct Node
{
  Type info;
  Node<Type> *lLink;
  Node<Type> *rLink;
};

• Circle represents a "node"

• Each node will have three fields: an information and two pointers (L/R)

• A node will have information such as "A"

• Nodes can have a pointer to the left (lLink) and a pointer to the right (rLink)

DEFINITIONS

DATA STRUCTURES MAIN OPERATIONS

• the three main priority for a programmer when defining data structures are:

  • insert

  • delete

  • search

Binary Trees

• A binary tree, T, is either empty or such that

  • T has a special node called the root node

  • T has two sets of nodes, TsubL and TsubR (left subtree and right subtree of T)

  • TsubL and TsubR are binary trees

BINARY TREES, ARRAYS, & LINKED LISTS COMPARISON

• when organizing data, a highest priority is to insert, delete, and search data as fast as possible

  • Arrays: Random access data structure (by index)

    • +Item search can be fast (mainly if the data is sorted: binary search)

    • -Item insertion and deletion are time consuming (data shifting)

  • Linked Lists: Access by pointers

    • +Faster in insertion and deletion (update some pointers)

    • -Sequential search (must begin with the first item)

  • Binary Trees

    • +More efficient in item insertion, deletion and search

BINARY TREES VISUALIZATION

• A is the root of T

• B is the left child of A (C is the right child of A)

• A is the parent of B and C

• TsubL = {B, D, E, G}, TsubR = {C, F, H}, B is the root of TsubL

BINARY TREE W/ ONE NODE

BINARY TREE W/ TWO NODES

BINARY TREE W/ THREE NODES

LEAF

• a node in a tree with no left and right children

PARENT

• a node U is called the parent of a node V if there is an edge (branch) from U to V

PATH

• a path from a node X to a node Y in a binary tree is a sequence of nodes

LEVEL

• the level of a node in a binary tree is the number of branches on the path from the root to the node

HEIGHT

• the height of a binary tree is the number of nodes on the longest path from the root to a leaf

BINARY TREE TRAVERSAL

• the item insertion, deletion, and search operations require that the binary tree be traversed

• the traversal must start from the root (as we have a pointer to it)

• for each node, we have two choices

  • visit the node first

  • visit the subtrees first

• the above two choices lead to three different traversals: inorder, preorder, & postorder traversals

INORDER TRAVERSAL

template<class Type>
void inorder(Node<Type>* p){
  if (p != NULL){
    inorder(p->lLink);        //left subtree
    cout << p->info << " ";   //root
    inorder(p->rLink);        //right subtree
  }
}

• the binary tree is traversed as follows:

  • traverse the left subtree (recursive call)

  • visit the current root

  • traverse the right subtree (recursive call)

PREORDER TRAVERSAL

template<class Type>
void preorder(Node<Type>* p){
  if (p != NULL){
    cout << p->info << " ";     //root
    preorder(p->lLink);         //left subtree
    preorder(p->rLink);         //right subtree
  }
}

• the binary tree is traversed as follows:

  • visit the current root

  • traverse the left subtree (recursive call)

  • traverse the right subtree (recursive call)

POSTORDER TRAVERSAL

template<class Type>
void postorder(Node<Type>* p){
  if (p != NULL){
    postorder(p->lLink);             //left subtree
    postorder(p->rLink);             //right subtree
    cout << p->info << " ";          //root
  }
}

• the binary tree is traversed as follows:

  • traverse the left subtree (recursive call)

  • traverse the right subtree (recursive call)

  • visit the currrent root

BINARY SEARCH TREE T

• T is either empty or:

  • T has a special node called the root node

  • T has two sets of nodes, TsubL and TsubR, called left subtree and right subtree of T

  • The value in the root node is larger than every value in the left subtree and smaller than every value in the right subtree

  • TsubL and TsubR are binary search trees

BINARY SEARCH TREES OPERATIONS (FUNCTIONS)

• determine whether the binary tree is empty

• find the height of the binary tree

• find the number of nodes in the binary tree

• find the number of leaves in the binary tree

• traverse the binary tree

IMPLEMENTATION

UML

VISUALIZATION

SOURCE

HEADER FILE: binaryTree.h

The data members of the class are divided into public, protected, and private. All the public functions have no parameters. The parameters are specified in the private functions.

• the public members are to be used outside the class to handle the binary tree as an ADT

• the protected member(the pointer to the root of the tree) is to be used to derive special binary trees

• the private members are used to implement the public functions. the user of the class doesn't need to access them

/*################################################
# Name: Stephen Razon
# Student ID:
# Date: 081253DEC24
# Filename: binaryTree.h
# Dependency: N/A
################################################*/

template<class Type>
struct Node
{
  Type info;
  Node<Type>* lLink;
  Node<Type>* rLink;
};

template<class Type>
class BinaryTree
{
  protected:
    Node<Type>* root;
  
  //these functions are used to assist in the implementation of the public functions
  private:
    void destroy(Node<Type>*&);
    void inorder(Node<Type>*);
    void preorder(Node<Type>*);
    void postorder(Node<Type>*);
    int height(Node<Type>*);
    int max(int, int);
    int nodeCount(Node<Type>*);
    int leavesCount(Node<Type>*);
    
  //these functions doesn't have parameter to prevent the root from being manipulated
  public:
    BinaryTree(); 
    bool isEmpty();
    void inorderTraversal();
    void preorderTraversal();
    void postorderTraversal();
    int treeHeight();
    int treeNodeCount();
    int treeLeavesCount();
    void destroyTree();
    ~BinaryTree();
};

//inheritance
template<class Type>
class BinarySearchTree : public
BinaryTree<Type>
{
  private:
    void deleteFromTree(Node<Type>*&);
  public:
    bool search(const Type&);
    void insert(const Type&);
    void deleteNode(const Type&);
};

HEADER FILE: binaryTreeImplementation.h

/*################################################
# Name: Stephen Razon
# Student ID:
# Date: 081253DEC24
# Filename: binaryTreeImplementation.h
# Dependency: binaryTree.h
################################################*/

#include "binaryTree.h"

template<class Type>
BinaryTree<Type>::BinaryTree(){                //constructor
  root = NULL;
}

template<class Type>
bool BinaryTree<Type>::isEmpty(){
  return(root == NULL);
}

template<class Type>
void BinaryTree<Type>::inorderTraversal(){     //this is a public function and calls the private function
  inorder(root);
}

template<class Type>
void BinaryTree<Type>::inorder(Node<Type>* p){
  if (p != NULL){
    inorder(p->lLink);
    cout << p->info << " ";
    inorder(p->rLink);
  }
}

template<class Type>
void BinaryTree<Type>::preorderTraversal(Node<Type>* p){
  preorder(root);
}

template<class Type>
void BinaryTree<Type>::preorder(Node<Type>* p){
  if (p != NULL){
    cout << p->info << " ";     //root
    preorder(p->lLink);         //left subtree
    preorder(p->rLink);         //right subtree
  }
}

template<class Type>
void BinaryTree<Type>::postorderTraversal(Node<Type>* p){
  postorder(root);
}

template<class Type>
void BinaryTree<Type>::postorder(Node<Type>* p){
  if (p != NULL){
    postorder(p->lLink);             //left subtree
    postorder(p->rLink);             //right subtree
    cout << p->info << " ";          //root
  }
}

template<class Type>
int BinaryTree<Type>::treeHeight(){
  return height(root);
}

template<class Type>
int BinaryTree<Type>::height(Node<Type>* p){
  if (p == NULL)
    return 0;
  else
    //1 is the root node + the no of nodes in the left subtree + the no of nodes in the right subtree
    return 1 + max(height(p->lLink), height(p->rLink));
}

template<class Type>
Type BinaryTree<Type>::max(Type x, Type y){
  if (x >= y)
    return x;
  else
    return y;
}

template<class Type>
int BinaryTree<Type>::treeNodeCount(){
  return nodeCount(root);
}


template<class Type>
int BinaryTree<Type>::nodeCount(Node<Type>* p){
  if (p == NULL)
    return 0;
  else
    //1 is the root node + the no of nodes in the left subtree + the no of nodes in the right subtree
    return 1 + nodeCount(p->lLink) + nodeCount(p->rLink);
}

template<class Type>
int BinaryTree<Type>::treeLeavesCount(){
  return leavesCount(root);
}

/*leavesCount
Basic step:
  If the tree is empty, return 0
  If the tree contains only one node, return 1
Recursive step:
  Return the number of leaves of the left subtree + the number of leaves of the right subtree.
*/
template<class Type>
int BinaryTree<Type>::leavesCount(Node<Type>* p){
  if (p == NULL)
    return 0;
  if (p->lLink == NULL && p->rLink == NULL)
    return 1;
  else
    return leavesCount(p->lLink) + leavesCount(p->rLink);
}

template<class Type>
void BinaryTree<Type>::destroyTree()
{
  destroy(root);
}

template<class Type>
void BinaryTree<Type>::destroy(Node<Type>*& p){
  if (p != NULL){
    destroy(p->lLink);
    destroy(p->rLink);
    delete p;
    p = NULL;
  }
}

template<class Type>
BinaryTree<Type>::~BinaryTree(){
  destroy(root);
}

template<class Type>
bool BinarySearchTree<Type>::search(const Type& x){
  Node<Type>* current;
  bool found = false;
  if (this->root == NULL)
    cout << "Empty tree!" << endl;
  else{
    current = this->root;
    while (current != NULL && !found){
      if (current->info == x)
        found = true;
      else if (current->info > x)
	current = current->lLink;
      else
	current = current->rLink;
    }
  }
  return found;
}

template<class Type>
void BinarySearchTree<Type>::insert(const Type& x){
  Node<Type>* current, *prevCurrent=NULL, *newNode;
  newNode = new Node<Type>;
  assert(newNode != NULL);
  newNode->info = x;  newNode->lLink = NULL; newNode->rLink = NULL;
  if (this->root == NULL)
    this->root = newNode;
  else{
    current = this->root;
    while (current != NULL){
      prevCurrent = current;
      if (current->info == x){
        cout << "Item is already in the list!" << endl;
	return;
      }
      else if (current->info > x)
        current = current->lLink;
      else
        current = current->rLink;
    }
    if (prevCurrent->info > x)
      prevCurrent->lLink = newNode;
    else
      prevCurrent->rLink = newNode;
  }
}

template<class Type>
void BinarySearchTree<Type>::deleteFromTree(Node<Type>*& p){
  Node<Type>* current, *prevCurrent, *temp;
  if (p == NULL)
    cout << "The node to be deleted is NULL!" << endl;
  else if (p->llink == NULL && p->rlink == NULL) {//p points to a leaf
    temp = p;
    p = NULL;
    delete temp;
  }
  else if (p->llink == NULL) { //p points to a node with only a right child  
    temp = p;
    p = temp->rlink;
    delete temp;
  }
  else if (p->rlink == NULL) { //p points to a node with only a left child 
    temp = p;
    p = temp->llink;
    delete temp;
  }
  else { //p points to a node with two children
    current = p->llink;
    prevCurrent = NULL;
    while (current->rlink != NULL){
      prevCurrent = current;
      current = current->rlink;
    }
    p->info = current->info;
    if (prevCurrent == NULL)   //current did not move, current = p->llink, adjust p
    p->llink = current->llink;
    else
      prevCurrent->rlink = current->llink;
      delete current;
  }
}

//**************************   deleteNode   **************************
template<class Type>
void BinarySearchTree<Type>::deleteNode(const Type& x){
  Node<Type>* current;
  Node<Type>* prevCurrent;
  bool found = false;
  if (this->root == NULL)
    cout << "Cannot delete from an empty tree!" << endl;
  else{
    current = this->root;
    prevCurrent = this->root;
    while (current != NULL && !found){
      if (current->info == x)
        found = true;
      else{
        prevCurrent = current;
	if (current->info > x)
	  current = current->llink;
	else
	  current = current->rlink;
      }
    }
    if (current == NULL)
      cout << "The item is not in the tree!" << endl;
    else if (found){
      if (current == this->root)
        deleteFromTree(this->root);
      else
        if (prevCurrent->info > x)
	  deleteFromTree(prevCurrent->llink);
	else
	  deleteFromTree(prevCurrent->rlink);
    }
  }
}

#include<iostream>
using namespace std;
#include"BinarySearchTree.h"

void main()
{
	BinarySearchTree<int> bst;
	bst.insert(3);
	bst.insert(5);
	bst.insert(2);
	bst.insert(-1);
	bst.insert(4);
	bst.insert(6);
	bst.insert(-3);
	bst.insert(1);
	bst.insert(0);
	//bst.inorderTraversal();
	bst.postorderTraversal();
	bst.deleteNode(-3);
	cout << "\n";
	bst.postorderTraversal();
	//bst.preorderTraversal();
	cout << "\nNumber of leaves: "<<bst.treeLeavesCount() << endl;;
}