lundi 22 mai 2017

How to I count the number of Comparisons in a Binary Search Tree?

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