Home Binary search Tree using templates and reading in text files
Reply: 0

Binary search Tree using templates and reading in text files

Hanna369
1#
Hanna369 Published in 2017-12-07 01:57:40Z

I am completely lost on how to do this project. I have done what I know and searched the internet for things to help me finish this project, but I am almost hopeless at this point. If anyone could help me out and give me a very strong push in the right direction, that would be much appreciated. Okay here it is:

Create a template based binary search tree, then use this tree as the storage for a dictionary of words used to check the spelling of documents. The binary tree must have the following characteristics:

It must be a binary search tree (BST), relying on the order of the < > operators provided by whatever type the user of the tree chooses (in other words, you don't have to do anything special, just use those operators correctly).

Public methods:

bool insert(T value) : inserts a value into the tree, does not allow duplicates.  If the value is already in the tree do notadd the duplicate and return false, true otherwise.

void remove(T value) : deletes a value from the tree.

bool search(T value) : tests to see if a value exists in the tree.

void display() : Performs an in-order traversal of the tree, displaying the value at each node.

unsigned int numberNodes() : returns a count of all nodes in the tree.

unsigned int numberLeafNodes() : returns a count of all the leaf nodes in the tree.

unsigned int height() : returns the height of the tree.

Write a driver program that reads the file “dictionary.txt”, where each word is on a separate line, and stores these words into your binary search tree. After reading the dictionary into your tree, have your program report the number of nodes, the number of leaf nodes, and height (depth) of the tree.

The following is an example report:

-- Tree Stats --

Total Nodes: 13643 Leaf Nodes: 4545 Tree Height: 30

Next, read the file “letter.txt” and output to the console all the misspelled words (meaning any word not found in the dictionary), keep in mind the graders will use a different file when doing the grading. You'll need to remove case from the words and remove any punctuation characters from the words in the letter; the following characters should be sufficient: “ , : . ! ? ( )

One problem you need to resolve: The dictionary is in alphabetic order. If you insert the words in alphabetic order, your tree will essentially be a linked list and of not much use (with respect to performance). The words must be inserted in random order to make a tree that can be efficiently searched. A suggestion is to use the std::random_shuffle algorithm in the C++ standard library. This will randomly organize the values in a vector. Then, you can iterate through the vector and add items to your tree, resulting in a reasonably balanced and efficient binary search tree.

Here is all I got:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

template <class T>

class Tree
{
    struct TreeNode
    {
        T data;
        TreeNode* left;
        TreeNode* Right;

        TreeNode(T value) :data(value), left(NULL), right(NULL)
        {
            //empty
        }
    };
    TreeNode* root;
public:
    Tree();
    ~Tree();
    bool insert(T value);
    void remove(T value);
    bool search(T value);
    void display();
    unsigned int numberNodes();
    unsigned int numberLeafNodes();
    unsigned int height();

};

template <class T>
Tree<T>::Tree() :root(NULL) 
{
  //empty
}

template <class T>
Tree<T>::~Tree()
{
    if (node == NULL)
        return;
    if (node->left)
        freeMemory(node->left);
    if (root->right)
        freeMemory(node->right);
    delete node;
}


template <class T>

bool Tree<T>::insert(T value)
{
    TreeNode* treeNode = NULL;

    temp = root;
    while (temp)
    {
        prev = temp;
        if (temp->data < treeNode->data)
        {
            temp = temp->right;
            return true;
        }
        else
        {
            temp = temp->left;
            return true;
        }
    }
    if (prev == NULL)
    {
        root = treeNode;
        return true;
    }
    else
    {
        if (prev->data < treeNode->data)
        {
            prev->right = treeNode;
            return true;
        }
        else
        {
            prev->left = treeNode;
            return true;
        }
    }
}


template<class T>
void Tree<T>::remove(T value)
{

}

template<class T>
bool Tree<T>::search(T value)
{
    return false;
}

template<class T>
void Tree<T>::display()
{

}

template<class T>
unsigned int Tree<T>::numberNodes()
{
    return 0;
}

template<class T>
unsigned int Tree<T>::numberLeafNodes()
{
    return 0;
}

template<class T>
unsigned int Tree<T>::height()
{
    return 0;
}


int main()
{



    system("PAUSE");
    return 0;
}
You need to login account before you can post.

About| Privacy statement| Terms of Service| Advertising| Contact us| Help| Sitemap|
Processed in 0.324675 second(s) , Gzip On .

© 2016 Powered by mzan.com design MATCHINFO