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;;
}
Last updated