Learn Computer Science programming - C# and C++ Algorithms

 
C++ Breadth-first search (BFS)

This is a graph search algorithm that begins at the root node and explores all the neighboring nodes until it finds the node that it seeks.
Picture
Code
bfs.zip
File Size: 6981 kb
File Type: zip
Download File

bst.zip
File Size: 4143 kb
File Type: zip
Download File

This is the code you can place inside your main class void main()

#include <iostream>
#include "Classes.h"
#include <string.h>
#include <windows.h>
using namespace std;

void main()
{
wcout <<  "*** Binary Tree ***" << endl;
wcout << "*************************************************" << endl;
//Build a tree
int x; 
Tree T;

T.AddNode(root1 ,100); 
T.AddNode(root1,50); 
T.AddNode(root1,115);
T.AddNode(root1,25); 
T.AddNode(root1,75); 
T.AddNode(root1,15);
T.AddNode(root1,110); 
T.AddNode(root1,125);
T.AddNode(root1,135); 
cout << endl << "*** PreOrder ***" << endl;
T.PrintPreOrder (root1);
cout << endl << "*** InOrder ***" << endl;
T.PrintInOrder (root1);
cout << endl << "*** PostOrder ***" << endl;
T.PrintPostOrder (root1);
cout << endl << "*** BFS ***" << endl;
T.PrintBFS(root1);
cout << endl << "*** DFS ***" << endl;
T.PrintDFS(root1);
}

BFS class code
#include <iostream>
#include "Classes.h"
using namespace std;


void Tree::PrintPreOrder(BTNode* Current)
{
if (Current)
{
cout << endl << "Node Value = " << Current->Data;
PrintPreOrder(Current->Left); 
PrintPreOrder(Current->Right);
}
}


void Tree::PrintInOrder(BTNode* Current)
{
if (Current)
{
PrintInOrder(Current->Left);
cout << endl << "Node Value = " << Current->Data;
PrintInOrder(Current->Right);
}
}


void Tree::PrintPostOrder(BTNode* Current)
{
if (Current)
{
PrintPostOrder(Current->Left);
PrintPostOrder(Current->Right);
cout << endl << "Node Value = " << Current->Data;
}
}


void Tree::AddNode (BTNode* tree, int d)
{
// Handles the first item in the tree only.
if (!tree->Data)
{
tree->Data = d;
tree->Left = NULL; 
tree->Right = NULL;
return;
}
else
{
BTNode* NewItem = new BTNode;
NewItem->Data = d;
NewItem->Left = NULL; 
NewItem->Right = NULL;

if (d > tree->Data) 
InsertRight(NewItem, tree);
else
InsertLeft(NewItem, tree);
}
}
BTNode* Tree::InsertRight(BTNode* NewItem, BTNode* Current)
{
if (!Current->Right && NewItem->Data > Current->Data )
Current->Right = NewItem;
else
{
if (NewItem->Data > Current->Data) 
{
Current = Current->Right;
InsertRight(NewItem, Current);
}
else 
InsertLeft(NewItem, Current);
}
return NewItem;
}


BTNode* Tree::InsertLeft(BTNode* NewItem, BTNode* Current)
{
if (!Current->Left && NewItem->Data < Current->Data)
Current->Left = NewItem;
else
{
if (NewItem->Data < Current->Data) 
{
Current = Current->Left;
InsertLeft(NewItem, Current);
}
else 
InsertRight(NewItem, Current);
}
return NewItem;
}


void Tree::PrintBFS(BTNode* Tree)
{
Queue Q;
BTNode *currentNode = Tree;

Q.AddFromRear (currentNode);
cout <<  currentNode->Data << " , ";


while (currentNode)
{
if (currentNode->Left != NULL) 
Q.AddFromRear(currentNode->Left);
if (currentNode->Right != NULL) 
Q.AddFromRear(currentNode->Right);
Q.DeleteFront (); 
currentNode = (BTNode*) Q.FrontofQueue ();

if (currentNode)
cout << currentNode->Data << " , ";
}
}
void Tree::PrintDFS(BTNode* Tree)
{
BTNode *currentNode = Tree;
cout <<  currentNode->Data << " , ";

if (currentNode->Left != NULL) 
PrintDFS(currentNode->Left);
if (currentNode->Right != NULL) 
PrintDFS(currentNode->Right);
}


BTNode *Tree::FindNode (BTNode *root, int value)
{
BTNode *current = new BTNode;
current = root;
while (current)
{
if (current->Data = value)
return current;
else if (value < current->Data)
return FindNode(current->Left , value);
else if (value > current->Data)
return FindNode(current->Right , value);
}
return NULL;
}


//  Remove
void Tree::Remove(BTNode* root,int value)
{
//Find Value
BTNode *current = root;

while (current)
{
if (current->Left->Data = value)
{
BTNode* DeleteMe = new BTNode;
DeleteMe->Left = current->Left->Left;
DeleteMe->Right = current->Left->Right;


current->Left = DeleteMe->Left;


//Find a position for the Right node under current
//Check right (Left is not needed since it was originally less than this value)

}
else if (current->Right->Data = value)
{
current->Right = current->Right->Left;
BTNode* TMP = current->Left;
current->Left = current;
current->Left = current->Right->Right;
current->Right->Right = TMP;
}
else if (value < current->Data) //Advance
current = current->Left;
else if (value > current->Data) //Advance
current = current->Right;
}
}
// Count
// Max
// Largest Depth