I developed a binary search tree, and I'm trying to insert 10,000 unique random integers into an array. I was able to make an array of random integers, but Now I want to find the 500th entry in the tree, but I'm still not sure how to do that. If you could help me with this, I would very much appreciate it. Here's my main code, followed by the functions for contain, getentry, and findNode.
#include <iostream>
#include <string>
#include "BinarySearchTree.h" // ADT binary tree operations
#include "BinaryNode.h"
#include <ctime>
using namespace std;
void display(int& anItem)
{
cout << "Displaying item - " << anItem << endl;
}
void check(const bool success)
{
if (success)
cout << "Done." << endl;
else
cout << " Entry not in tree." << endl;
}
void main()
{
int array[10000];
BinarySearchTree<int>* treePtr = new BinarySearchTree<int>();
int total = 10000;
srand(time(NULL));
for (int i=0; i < total; i++)
{
array[i]=rand() % 10000 + 1;
treePtr->add(array[i]);
}
int numCompares = 0;
treePtr->contains(array[0]);
cout << "It took " << numCompares << " comparisons" << endl;
system("pause");
}
template<class ItemType>
BinaryNode<ItemType>*
BinarySearchTree<ItemType>::findNode(BinaryNode<ItemType>* subTreePtr,
const ItemType& target) const
{
// Uses a binary search
if (subTreePtr == nullptr)
return nullptr; // Not found
else if (subTreePtr->getItem() == target)
return subTreePtr; // Found
else if (subTreePtr->getItem() > target)
// Search left subtree
return findNode(subTreePtr->getLeftChildPtr(), target);
else
// Search right subtree
return findNode(subTreePtr->getRightChildPtr(), target);
} // end findNode
template<class ItemType>
ItemType BinarySearchTree<ItemType>::getEntry(const ItemType& anEntry) const throw(NotFoundException)
{
BinaryNode<ItemType>* nodeWithEntry = findNode(rootPtr, anEntry);
if (nodeWithEntry == nullptr)
throw NotFoundException("Entry not found in tree.");
else
return nodeWithEntry->getItem();
} // end getEntry
// Override contains to use our improved findNode:
template<class ItemType>
bool BinarySearchTree<ItemType>::contains(const ItemType& anEntry) const
{
return (findNode(rootPtr, anEntry) != nullptr) ? true : false; // nullptr is same as false
} // end contains
Aucun commentaire:
Enregistrer un commentaire