Read a list of names from a file. Insert the names into a binary search tree tha

Question

Read a list of names from a file. Insert the names into a binary search tree that is a little different from what we discussed in class. For this tree, the left side will contain the larger values and the right side will contain the smaller values. In essence, it is the exact opposite of a normal binary search tree Our tree will also be able to store duplicate names. Aside from a left and a right pointer for each node, we will have another pointer variable that will point to a linked list. Each node in the linked list will contain the additional duplicate name Once the nodes have been inserted, give the user a chance to search for a name. Display your search path as you are searching through the tree and indicate if the name was found. If the name is found and there are duplicates, indicate how many duplicates of the name exist in the tree Here is an example Given the following names in the file Dan Your tree would look like the following Dan, Phil, Angela, Ayesha, Kai, Zia, Troy, Troy, Troy, roy

Explanation / Answer

Source Code

#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>

using namespace std;

struct BinaryTree
{
    string key;
    struct BinaryTree *left;
    struct BinaryTree *right;
    int h;
    int count;
};

int max(int a, int b);

int h(struct BinaryTree *N)
{
    if (N == NULL)
        return 0;
    return N->h;
}

int max(int a, int b)
{
    return (a > b) ? a : b;
}

struct BinaryTree* newBinaryTree(const string& key)
{
    struct BinaryTree* node = (struct BinaryTree*)
        malloc(sizeof(struct BinaryTree));
    node->key = key;
    node->left = nullptr;
    node->right = nullptr;
    node->count = 0;
    node->h = 1;
    return(node);
}

struct BinaryTree *rightRotate(struct BinaryTree *y)
{
    struct BinaryTree *x = y->left;
    struct BinaryTree *T2 = x->right;

    x->right = y;
    y->left = T2;

    y->h = max(h(y->left), h(y->right)) + 1;
    x->h = max(h(x->left), h(x->right)) + 1;

    return x;
}

struct BinaryTree *leftRotate(struct BinaryTree *x)
{
    struct BinaryTree *y = x->right;
    struct BinaryTree *T2 = y->left;

    y->left = x;
    x->right = T2;

    x->h = max(h(x->left), h(x->right)) + 1;
    y->h = max(h(y->left), h(y->right)) + 1;

    return y;
}

int getBalance(struct BinaryTree *N)
{
    if (N == NULL)
        return 0;
    return h(N->left) - h(N->right);
}

struct BinaryTree* insert(struct BinaryTree* node, string key)

{
    if (node == NULL)
        return(newBinaryTree(key));

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
    {
        node->count++;
        return node;
    }
    node->h = 1 + max(h(node->left),
        h(node->right));

    int bal = getBalance(node);

    if (bal > 1 && key < node->left->key)
        return rightRotate(node);

    if (bal < -1 && key > node->right->key)
        return leftRotate(node);

    if (bal > 1 && key > node->left->key)
    {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if (bal < -1 && key < node->right->key)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}
void preOrder(struct BinaryTree *root)
{
    if (root)
    {
        cout << root->key << endl;;
        preOrder(root->left);
        preOrder(root->right);
    }
}

/* Drier program to test above function*/
int main()
{
    struct BinaryTree *root = nullptr;

    /* Constructing tree given in the above figure */

    root = insert(root, "a");
    root = insert(root, "bc");
    root = insert(root, "DE");
    root = insert(root, "op");
    root = insert(root, "lo");
    root = insert(root, "mp");

    /*root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);*/

    printf("Preorder traversal of the constructed AVL"
        " tree is ");
    preOrder(root);

    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.