Description

A binary search tree (BST) is a binary tree, whose internal nodes each store a key and each have two sub-trees, commonly denoted left and right. The tree additionally satisfies the property: the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in the right sub-tree.

 

Let’s see how the BST data structure can be realized in C++ using a linked structure. We define three classes and use polymorphism as follows:

 

function.h

#ifndef function_h #define function_h #include <iostream> #include <math.h> using namespace std; class BST{ public: BST():Height(0){} virtual ~BST() {} virtual void insert(const int &) = 0; virtual void print() const = 0; int height() const { return Height; }// An empty tree has height of 0. A tree with only root node has height of 1. protected: int Height; }; class ListNode{ friend class List_BST; //make List_BST a friend public: ListNode(const int &info):key( info ),left( NULL ),right( NULL ) //constructor { }//end ListNode constructor private: int key; ListNode *left; ListNode *right; };//end class ListNode class List_BST : public BST{ public: List_BST() : BST(), root(NULL) { } virtual ~List_BST() {} virtual void insert(const int &) override; virtual void print() const override{ printIncOrder(root); } private: ListNode *root; // private member functions ListNode* createLeaf(int key) const; //new a ListNode and return its address void printIncOrder(ListNode* Ptr) const { if(Ptr!=NULL) { printIncOrder(Ptr->left); cout<<Ptr->key<<" "; printIncOrder(Ptr->right); } } }; #endif /* function_h */

main.cpp

#include <iostream> #include <string.h> #include "function.h" using namespace std; void BSTManipulator(BST& bstobj, char cmd ){ int n; if (cmd == 'I') { cin >> n; bstobj.insert(n); }else if (cmd == 'H'){ cout << bstobj.height() << endl;; }else if (cmd == 'P'){ bstobj.print(); cout << endl; } } int main(){ List_BST bst; char cmd; while (cin >> cmd) BSTManipulator(bst, cmd); return 0; }

 

where

1. Class BST serves as the abstract base class for realizing polymorphism
2. List_ BST provide an approach to implementing the BST data structure

 

REQUIREMENTS:

1. Implement the insert and createLeaf member functions of the List_ BST class.

Note:

1.      This problem involves three files.

• function.h: Class definitions.
• function.cpp: Member-function definitions.
• main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp and function.h, and asked to implement function.cpp.

 

2.      For OJ submission:

       Step 1. Submit only your function.cpp into the submission block.

       Step 2. Check the results and debug your program if necessary.

 

Input

There are three kinds of commands:

• “I A”: insert a node with int value A(A>0) into the BST. If the key already exists, you simply do nothing.
• “P”: show the current content of the BST.
• “H”: print the BST’s height. Remember if the BST is empty, the height is 0 and you should print “0”.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output shows the result of each command.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11022.cpp

Partial Judge Header

11022.h

Tags

Discuss

Description

A queue is an abstract data type that serves as a collection of elements, where nodes are removed only from the head of the queue and are inserted only at the tail of the queue. Two principal operations can be used to manipulate a queue: enqueue, which inserts an element at the tail, and dequeue, which removes the element at the head of the collection.

 

Let’s see how the queue data structure can be realized in C++.We have an approach to implement queue: linked list. Thus, we define two classes as follows:

 

class Queue{

    friend std::ostream &operator<<(std::ostream &, Queue &);

    public:

        virtual ~Queue() {};

        virtual void enqueue(const int &) = 0;

        virtual int dequeue() = 0;

        virtual void print(std::ostream &output)=0;

};

class List_queue : public Queue{

    public:

        List_queue();

        virtual ~List_queue();

        void enqueue(const int &);

        int dequeue();

        void print(std::ostream &output);

    private:

        ListNode *head;

        ListNode *tail;

};

where

1. Class Queue serves as the abstract base class for realizing polymorphism
2. List_queue implements the queue data structure

Besides, we also overload the stream insertion operator (<<) to print the content of a queue object polymorphically.

 

REQUIREMENTS:

1. Implement the enqueue(), dequeue() and print() member functions of the List_queue class.
2. Implement the overloaded stream insertion operator (<<), which will call the correct member function print() polymorphically.

Note:

1.This problem involves three files.

• function.h: Class definitions.
• function.cpp: Member-function definitions.
• main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp and function.h, and asked to implement function.cpp.

<code>function.h</code>

#ifndef FUNCTION_H
#define FUNCTION_H
#include <iostream>
class ListNode
{
    friend class List_queue; //make List_queue a friend
public:
    ListNode( const int &info ) //constructor
    : data( info ), nextPtr( NULL ), prevPtr( NULL )
    {
    } //end ListNode constructor
private:
    int data; //data
    ListNode *nextPtr; // next node in list
    ListNode *prevPtr;
}; //end class ListNode
class Queue{
    friend std::ostream &operator<<(std::ostream &, Queue &);
    public:
        virtual ~Queue() {};
        virtual void enqueue(const int &) = 0;
        virtual int dequeue() = 0;
        virtual void print(std::ostream &output)=0;
};
class List_queue : public Queue{
    public:
        List_queue();
        virtual ~List_queue();
        void enqueue(const int &);
        int dequeue();
        void print(std::ostream &output);
    private:
        ListNode *head;
        ListNode *tail;
};
#endif // FUNCTION_H

<code>main.cpp</code>

#include <iostream>
#include <string.h>
#include "function.h"
using namespace std;
int main(){
    List_queue L_queue;
    char command[10];
    int n;
    while(cin>>command){
        if(strcmp(command,"dequeue")==0){
            L_queue.dequeue();
        }else if(strcmp(command,"enqueue")==0){
            cin >> n;
            L_queue.enqueue(n);
        }else if(strcmp(command, "print") == 0){
            cout << L_queue << endl;
        }
    }
    return 0;
}

2.For OJ submission:

       Step 1. Submit only your function.cpp into the submission block.

       Step 2. Check the results and debug your program if necessary.

Input

There are three kinds of commands:

• “enqueue integerA” represents inserting an element with int value A at the tail of the queue.

• “dequeue” represents removing the element at the head of the queue.

• “print” represents showing the current content of the queue.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output should consist of the current state of the queue.

When the queue is empty, you don’t need to print anything except a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11930.cpp

Partial Judge Header

11930.h

Tags

Discuss