17 Trees.ppt DSADSADSADSADSADSADSADSADSA

DSA

1. Binary Search Tree (BST)
Implementation
Data Structures & Algorithms
SPRING 2024

2. Binary Search Tree Operations
There are many operationsone can perform on a binary search tree.
a) Creatinga binary search tree
b) Insertinga node into a binary search tree
c) Findinga node in a binary search tree
d) Deletinga node in a binary search tree.
We will use a simple classthat implements a binary tree to store
integer values.
Creating a Binary Tree
We create an IntBinaryTreeclass.

3. The basic node of our binary tree has the following structdeclaration.
struct TreeNode
{
int value;
TreeNode *left;
TreeNode *right;
}
The class IntBinaryTree declaration is -
IntBinaryTree.h
class IntBinaryTree
{
private:
struct TreeNode
{
int value;
TreeNode *left;
TreeNode *right;
};

4. TreeNode *root;
void destroySubTree(TreeNode *);
void deleteNode(int, TreeNode *&);
void makeDeletion(TreeNode *&);
void displayInOrder(TreeNode *);
void displayPreOrder(TreeNode *);
void displayPostOrder(TreeNode *);
public:
IntBinaryTree() // Constructor
{ root = NULL; }
~IntBinaryTree() // Destructor
{ destroySubTree(root); }
void insertNode(int);
bool searchNode(int);
void remove(int);
void showNodesInOrder(void)
{ displayInOrder(root); }
void showNodesPreOrder()
{ displayPreOrder(root); }
void showNodesPostOrder()
{ displayPostOrder(root); }
};

5. Searching using Recursion( Individual Activity )
Void Search(node* temp, int num)
{
if(temp==NULL)
cout<<“Number not found";
elseif(temp->data == num)
cout<<"Number found";
else if(temp->data > num)
Search(temp->LTree, num);
else if(temp->data < num)
Search(temp->RTree, num);
}

6. Binary Search Tree –Deletion
Algorithm
1.Perform search for value X
2.If X is a leaf, delete X
3.else if X has only one child node
a)replace the node with either left or right subtree
a)else if X has two child nodes (internal node)
a) replace with largest value Y on left subtree
ORsmallest value Z on right subtree
b) deletereplacement value (Y or Z) from subtree

7. Example Deletion (Leaf)
Delete ( 25 )
5
10
30
2 25 45
10 < 25, right
30 > 25, left
25 = 25, delete
5
10
30
2 45

8. Example Deletion (Internal Node)
Delete ( 10 )
5
10
30
2 25 45
5
5
30
2 25 45
2
5
30
2 25 45
Replacing 10
with largest
value in left
subtree
Replacing 5
with largest
value in left
subtree
Deleting leaf

9. Example Deletion (Internal Node)
Delete ( 10 )
5
10
30
2 25 45
5
25
30
2 25 45
5
25
30
2 45
Replacing 10
with smallest
value in right
subtree
Deleting leaf Resulting tree

10. void IntBinaryTree::deleteNode(intnum,
TreeNode*&nodePtr)
{
if (num < nodePtr->value)
deleteNode(num, nodePtr->left);
else if (num > nodePtr->value)
deleteNode(num, nodePtr->right);
else
makeDeletion(nodePtr);
}
Deleting Node from BST (code)

11. void IntBinaryTree::makeDeletion(TreeNode*&nodePtr)
{
TreeNode*tempNodePtr;
// Temporary pointer, used in
// reattaching the left subtree.
if (nodePtr== NULL)
cout<< "Cannot delete empty node. \n";
else if (nodePtr->right == NULL)
{
tempNodePtr= nodePtr;
nodePtr= nodePtr->left;
delete tempNodePtr;
}
else if (nodePtr->left == NULL)
{
tempNodePtr= nodePtr;
nodePtr= nodePtr->right;
delete tempNodePtr;
}

12. // If the node has two children
else
{ // Move one node the right.
tempNodePtr= nodePtr->right;
// Go to the end left node.
while (tempNodePtr->left)
tempNodePtr= tempNodePtr->left;
nodePtr->value = tempNodePtr->value;
makeDeletion(tempNodePtr);
}
}

13. #include <iostream.h>
#include "IntBinaryTree.h“
void main(void)
{
IntBinaryTreetree;
cout<< "Inserting nodes.\n";
tree.insertNode(5);
tree.insertNode(8);
tree.insertNode(3);
tree.insertNode(12);
tree.insertNode(9);
cout<< "Here are the values in the tree: \n";
tree.showNodesInOrder ();

14. cout<< "Deleting 8...\n";
tree.deleteNode(8,root);
cout<< "Deleting 12...\n";
tree.deleteNode(12,root);
cout<< "Now, here are the nodes: \n";
tree.showNodesInOrder ();
}Program Output
Inserting nodes.
Here are the values in the tree:
3
5
8
9
12
Deleting 8...
Deleting 12...
Now, here are the nodes:
3
5
9

15. Program
Figure shows the structure of the binary tree built by the program.
Note:The shapeof the tree is
determined by the orderin
which the values are inserted.
The root node in the diagram
above holds the value 5 because
that was the first value inserted.

16. The IntBinaryTree class can displayallthe valuesin the tree using
all3 of these algorithms.
The algorithms are initiated by the following inline public member
functions -
void showNodesInOrder(void)
{ displayInOrder(root); }
void showNodesPreOrder()
{ displayPreOrder(root); }
void showNodesPostOrder()
{ displayPostOrder(root); }
Each of these public member functions calls a recursiveprivate
member function, and passes the root pointer as argument.
The code for these recursive functions is simple -

17. void IntBinaryTree::displayInOrder(TreeNode *nodePtr)
{
if (nodePtr != NULL)
{
displayInOrder(nodePtr ->left);
cout << nodePtr->value << endl;
displayInOrder(nodePtr ->right);
}
}
void IntBinaryTree::displayPreOrder(TreeNode *nodePtr)
{
if (nodePtr != NULL)
{
cout << nodePtr->value << endl;
displayPreOrder(nodePtr ->left);
displayPreOrder(nodePtr ->right);
}
}

18. void IntBinaryTree::displayPostOrder(TreeNode *nodePtr)
{
if (nodePtr != NULL)
{
displayPostOrder(nodePtr ->left);
displayPostOrder(nodePtr ->right);
cout << nodePtr->value << endl;
}
}

19. Program
// This program builds a binary tree with 5 nodes.
// The nodes are displayed with inorder, preorder,
// and postorder algorithms.
#include <iostream.h>
#include "IntBinaryTree.h “
void main(void)
{
IntBinaryTree tree;
cout << "Inserting nodes. \n";
tree.insertNode(5);
tree.insertNode(8);
tree.insertNode(3);
tree.insertNode(12);
tree.insertNode(9);

20. cout << "Inorder traversal: \n";
tree.showNodesInOrder();
cout << "\nPreorder traversal:\n";
tree.showNodesPreOrder();
cout << "\nPostorder traversal: \n";
tree.showNodesPostOrder();
}
Program Output
Inserting nodes.
Inorder traversal:
3
5
8
9
12

21. Preorder traversal:
5
3
8
12
9
Postorder traversal:
3
9
12
8
5