//-----------------------------------------------------------------------------
// Dictionary.h
// Header file for Dictionary ADT based on a Binary Search Tree. Includes a
// built in iterator called current that can perform a smallest-to-largest
// (forward) or a largest-to-smallest (reverse) iteration over all keys.
//-----------------------------------------------------------------------------
#include<iostream>
#include<string>

#ifndef DICTIONARY_H_INCLUDE_
#define DICTIONARY_H_INCLUDE_

// Exported types -------------------------------------------------------------
typedef std::string keyType; // must be comparable using <, <=, >, >=, ==, !=
typedef int       valType;

class Dictionary{

private:

// private Node struct
struct Node{
   // Node fields
   keyType key;
   valType val;
   Node* parent;
   Node* left;
   Node* right;
   // Node constructor
   Node(keyType k, valType v);
};

// Dictionary fields
Node* nil;
Node* root;
Node* current;
int num_pairs;

// Helper Functions (Optional) ---------------------------------------------

// inOrderString()
// Appends a string representation of the tree rooted at R to string s. The
// string appended consists of: "key : value \n" for each key-value pair in
// tree R, arranged in order by keys.
void inOrderString(std::string& s, Node* R) const;

// preOrderString()
// Appends a string representation of the tree rooted at R to s. The appended
// string consists of keys only, separated by "\n", with the order determined
// by a pre-order tree walk.
void preOrderString(std::string& s, Node* R) const;

// preOrderCopy()
// Recursively inserts a deep copy of the subtree rooted at R into this
// Dictionary. Recursion terminates at N.
void preOrderCopy(Node* R, Node* N);

// postOrderDelete()
// Deletes all Nodes in the subtree rooted at R, sets R to nil.
void postOrderDelete(Node* R);

// search()
// Searches the subtree rooted at R for a Node with key==k. Returns
// the address of the Node if it exists, returns nil otherwise.
Node* search(Node* R, keyType k) const;

// findMin()
// If the subtree rooted at R is not empty, returns a pointer to the
// leftmost Node in that subtree, otherwise returns nil.
Node* findMin(Node* R);

// findMax()
// If the subtree rooted at R is not empty, returns a pointer to the
// rightmost Node in that subtree, otherwise returns nil.
Node* findMax(Node* R);

// findNext()
// If N does not point to the rightmost Node, returns a pointer to the
// Node after N in an in-order tree walk. If N points to the rightmost
// Node, or is nil, returns nil.
Node* findNext(Node* N);

// findPrev()
// If N does not point to the leftmost Node, returns a pointer to the
// Node before N in an in-order tree walk. If N points to the leftmost
// Node, or is nil, returns nil.
Node* findPrev(Node* N);

public:

// Class Constructors & Destructors ----------------------------------------

// Creates new Dictionary in the empty state.
Dictionary();

// Copy constructor.
Dictionary(const Dictionary& D);

// Destructor
~Dictionary();

Celsius to Fahrenheit Table Design a program that displays a table...