DATA STRUCTURES
Lab 6 – Binary Search Tree
PDF created with pdfFactory Pro trial version [Link]
Agenda
¨ Introduction
¨ Class TreeNode Declaration.
¨ Class Tree Declaration.
¨ Insert function.
¨ Find function.
¨ Main and testing.
PDF created with pdfFactory Pro trial version [Link]
Binary Search Tree (BST)
¨ It is a binary tree where for each node x
¨ x’s left subtree values< x <x’s right subtree values
PDF created with pdfFactory Pro trial version [Link]
Class Declaration (TreeNode)
¨ Create a class (TreeNode), which
1. Has member variables of
nA pointer to NODE ( left)
n A pointer to NODE ( right)
n Value of the data
2. Has two constructors
n With parameters.
PDF created with pdfFactory Pro trial version [Link]
Class Declaration (TreeNode.h)
// Tree.h
template <class T>
class TreeNode
{
public:
TreeNode<T>* left;
TreeNode<T>* right;
T data;
TreeNode(T);
};
PDF created with pdfFactory Pro trial version [Link]
Class Declaration ([Link])
// [Link]
#include "Tree.h“
template<class T>
TreeNode<T>::TreeNode(T v)
{
data=v;
left=NULL;
right=NULL;
}
PDF created with pdfFactory Pro trial version [Link]
Class Declaration (Tree)
¨ Create a class (Tree), which
1. Has member variables of
nA pointer to NODE ( root)
n Size of tree
2. Has two constructors
n Default Constructor.
PDF created with pdfFactory Pro trial version [Link]
Class Declaration (Tree.h)
template<class T>
class Tree
{
private:
TreeNode<T> * root;
int size;
public:
Tree();
};
PDF created with pdfFactory Pro trial version [Link]
Class Declaration ([Link])
template<class T>
Tree<T>::Tree()
{
size = 0;
root = NULL;
}
PDF created with pdfFactory Pro trial version [Link]
Insert Operation
Example: insert 60 in the tree:
1. start at the root, 60 is greater than 25, search in right
subtree
2. 60 is greater than 50, search in 50’s right subtree
3. 60 is less than 70, search in 70’s left subtree
4. 60 is less than 66, add 60 as 66’s left child
PDF created with pdfFactory Pro trial version [Link]
Insert Operation
¨ Always insert new node as leaf node
¨ Start at root node as current node
¨ While the end of the tree is not reached
¤ If new node’s data < current’s data
n Then search left
¤ If new node’s key > current’s key
n Then search right
¤ Else
n Then, it already exists
¨ End while
¨ Add the node in it correct place, whether at the right or the left of
the targeted subtree.
¨ Increment the size.
PDF created with pdfFactory Pro trial version [Link]
Insert Operation (Tree.h)
template<class T>
class Tree
{
private:
TreeNode<T> * root;
int size;
public:
Tree();
void insert(T val);
};
PDF created with pdfFactory Pro trial version [Link]
Insert Operation ([Link])
template<class T> else if (val < ptr->data) {
void Tree<T>::insert(T val) { parentPtr = ptr;
ptr = ptr->left;
if (root==NULL) }
{
else {
root=new TreeNode<T>(val);
size++; cout<<“The value is
already added"<<endl;
return;
} return;
}
TreeNode<T> * ptr = root; }
TreeNode<T> * parentPtr = root;
ptr = new TreeNode<T>(val);
while(ptr != NULL) { if(val > (parentPtr -> data)) {
parentPtr -> right = ptr;
if (val > ptr->data) {
} else {
parentPtr = ptr;
ptr = ptr->right; parentPtr -> left = ptr;
} }
size++;
}
PDF created with pdfFactory Pro trial version [Link]
Find Operation
Example: search for 45 in the tree
1. start at the root, 45 is greater than 25, search in right
subtree
2. 45 is less than 50, search in 50’s left subtree
3. 45 is greater than 35, search in 35’s right subtree
4. 45 is greater than 44 , but 44 has no right subtree so 45 in
not in the BST
PDF created with pdfFactory Pro trial version [Link]
Find Operation
¨ Start at the root node as current node
¨ While the node is not found and the tree did not end
¤ If the value is less than the data in the current node
n Then search in the left sub tree
¤ Else if the value is greater than the data in the current
node
n Then search in the right sub tree
¤ Else
n Then the node is found
¨ End while
PDF created with pdfFactory Pro trial version [Link]
Find Operation (Tree.h)
template<class T>
class Tree
{
private:
TreeNode<T> * root;
int size;
public:
Tree();
void insert(T val);
bool find(T val);
};
PDF created with pdfFactory Pro trial version [Link]
Find Operation ([Link])
template <class T>
bool Tree<T>::find(T val) {
bool found = false;
TreeNode<T> * ptr = root;
while(!found && ptr != NULL) {
if (val < ptr->data) {
ptr = ptr->left;
}
else if (val > ptr->data) {
ptr = ptr->right;
}
else {
found = true;
}
}
return found;
}
PDF created with pdfFactory Pro trial version [Link]
The “main” Function
#include "[Link]"
using namespace std;
void main()
{
Tree<int> BST;
[Link](10);
[Link](5);
[Link](15);
[Link](25);
if([Link](7)== true)
cout<<"Found 7"<<endl;
if([Link](10)== true)
cout<<"Found 10"<<endl;
}
PDF created with pdfFactory Pro trial version [Link]
Thank You J
PDF created with pdfFactory Pro trial version [Link]