1. consider the following sequence of integer keys to be hashed into a has table

Question

1. consider the following sequence of integer keys to be hashed into a has table (size is 7) using the hash function H(key)= key module tablesize (or H(key) = key/ tablesize) 11,5,4,11,25,21. Insert each key above from left to right into hash tables using chaining to resolve collisions.

2. write a text file for a C++ function bool search(node *root, int target) which which finds if an integer "target" is stored in a BST a with the root node is pointed to pointer root. The node class is defined below.

Class Node

{

Public:

int data;

Node *left,*right;

}.

3. write a text file for a recursive algorithm bool check(node *r) that takes only a pointer r to the root of a binary ree and checks if the tree is a binary search tree. You may assume that keys in the tree are all distinct.

struct Node{

int key;

Node *left;

Node *right;

);

---------------------------------------------------------------------------------------------------------------------------------------------------------Good answer needed. thank you

Explanation / Answer

This has lot of subparts. can you please post one more question. I am answering 2 and 3.

questions 3

full working solution with function

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

struct Node
{
    int key;
    struct Node* left;
    struct Node* right;
};

int isBSTUtil(struct Node* Node, int min, int max);

int isBST(struct Node* Node)
{
return(isBSTUtil(Node, INT_MIN, INT_MAX));
}

int isBSTUtil(struct Node* Node, int min, int max)
{

/* an empty tree is BST */
if (Node==NULL)
     return 1;
     

if (Node->key < min || Node->key > max)
     return 0;


return
    isBSTUtil(Node->left, min, Node->key-1) && // Allow only distinct values
    isBSTUtil(Node->right, Node->key+1, max); // Allow only distinct values
}

struct Node* newNode(int key)
{
struct Node* Node = (struct Node*)
                       malloc(sizeof(struct Node));
Node->key = key;
Node->left = NULL;
Node->right = NULL;

return(Node);
}

int main()
{
struct Node *root = newNode(4);
root->left        = newNode(2);
root->right       = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(3);

if(isBST(root))
    printf("Is BST");
else
    printf("Not a BST");
   
getchar();
return 0;
}

question 2:

#include<iostream>
using namespace std;

struct Node
{
int data;
Node *left;
Node *right;
};

class tree
{
public:
    Node *head;    //pointer to root
    int count;     //stores number of elements in tree
    tree();
    void addNode(int);
    void deleteNode(int);
    bool search(int);
    int minimum();
    int maximum();
    void inorder();
    void preorder();
    void postorder();
    void printtree();
    int mthlargest();     //finds 'm'th largest element
    int mthsmallest();    //finds 'm'th smallest element
    void convert();       //converts binary tree to linked list
};

tree::tree()
{
   head=NULL;
   count =0;
}

void tree::addNode(int num)
{
   Node *temp= new Node;
   temp->data=num;
   temp->left=NULL;
   temp->right=NULL;

   Node **ptr=&head;          //double pointer

   while(*ptr!=NULL)
   {
      if(num>(*ptr)->data)
         ptr=&((*ptr)->right);

      if(num<(*ptr)->data)
         ptr=&((*ptr)->left);
   }

   *ptr=temp;
}

bool tree::search(int num)
{
    Node *temp = head;

    while (temp != NULL)
    {
        if (temp->data == num)
            break;

        if (num > temp->data)
            temp = temp->right;
        else               
        if (num < temp->data)
            temp = temp->left;
    }

    if (temp == NULL)
        return false;

    if (temp->data == num)
        return true;

    return false;
}

void display(bool a)
{
   if (a==1)
   cout<<"element found in the tree ";
   else
   cout<<"element not present in the tree ";
}

int main()
{
   bool a;  
   tree ob;
   ob.addNode(2);

   a=ob.search(2);
   display(a);

   a=ob.search(3);
   display(a);
   ob.search(-1);
   display(a);
   cout<<endl<<endl;

   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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