Need program in C++. Write a program that will create an AVL tree by reading cha
ID: 3696955 • Letter: N
Question
Need program in C++. Write a program that will create an AVL tree by reading character data from lab9.dat, print the number of nodes, print the nodes with an inorder, preorder, and postorder traversal. Use avlTree.h file, along with lab9.dat file. Need a .cpp file to run.
PreOrder Traversal Result: MDBACJIKTRNSWX
InOrder Traversal Result: ABCDIJKMNRSTWX
PostOrder Traversal Result: ACBIKJDNSRXWTM
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
avlTree.h
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef H_AVLTree
#define H_AVLTree
#include <iostream>
using namespace std;
template <class elemT>
class AVLNode
{
public:
elemT info;
int bfactor; // balance factor
AVLNode *llink;
AVLNode * rlink;
};
template <class elemT>
class AVLTreeType
{
public:
void insert(const elemT &newItem);
void rotateToLeft(AVLNode<elemT>* &root);
void rotateToRight(AVLNode<elemT>* &root);
void balanceFromLeft(AVLNode<elemT>* &root);
void balanceFromRight(AVLNode<elemT>* &root);
void insertIntoAVL(AVLNode<elemT>* &root,
AVLNode<elemT> *newNode,
bool& isTaller);
void preorderTraversal();
void preorderTraversal(ofstream &);
void inorderTraversal();
void inorderTraversal(ofstream &);
void postorderTraversal();
void postorderTraversal(ofstream &);
int length();
AVLTreeType(); //default constructor
private:
AVLNode<elemT>* root;
int numNodes; // Holds the number of nodes
void preorder(AVLNode<elemT> *p);
void preorder(AVLNode<elemT> *p, ofstream &);
void inorder(AVLNode<elemT> *p);
void inorder(AVLNode<elemT> *p, ofstream &);
void postorder(AVLNode<elemT> *p);
void postorder(AVLNode<elemT> *p, ofstream &);
};
template <class elemT>
void AVLTreeType<elemT>::rotateToLeft(AVLNode<elemT>* &root)
{
AVLNode<elemT> *p; //pointer to the root of the
//right subtree of root
if (root == NULL)
cerr << "Error in the tree" << endl;
else if (root->rlink == NULL)
cerr << "Error in the tree:"
<<" No right subtree to rotate." << endl;
else
{
p = root->rlink;
root->rlink = p->llink; //the left subtree of p becomes
//the right subtree of root
p->llink = root;
root = p; //make p the new root node
}
}//rotateLeft
template <class elemT>
void AVLTreeType<elemT>::rotateToRight(AVLNode<elemT>* &root)
{
AVLNode<elemT> *p; //pointer to the root of
//the left subtree of root
if (root == NULL)
cerr << "Error in the tree" << endl;
else if (root->llink == NULL)
cerr << "Error in the tree:"
<< " No left subtree to rotate." << endl;
else
{
p = root->llink;
root->llink = p->rlink; //the right subtree of p becomes
//the left subtree of root
p->rlink = root;
root = p; //make p the new root node
}
}//end rotateRight
template <class elemT>
void AVLTreeType<elemT>::balanceFromLeft(AVLNode<elemT>* &root)
{
AVLNode<elemT> *p;
AVLNode<elemT> *w;
p = root->llink; //p points to the left subtree of root
switch (p->bfactor)
{
case -1:
root->bfactor = 0;
p->bfactor = 0;
rotateToRight(root);
break;
case 0:
cerr << "Error: Cannot balance from the left." << endl;
break;
case 1:
w = p->rlink;
switch (w->bfactor) //adjust the balance factors
{
case -1:
root->bfactor = 1;
p->bfactor = 0;
break;
case 0:
root->bfactor = 0;
p->bfactor = 0;
break;
case 1:
root->bfactor = 0;
p->bfactor = -1;
}//end switch
w->bfactor = 0;
rotateToLeft(p);
root->llink = p;
rotateToRight(root);
}//end switch;
}//end balanceFromLeft
template <class elemT>
void AVLTreeType<elemT>::balanceFromRight(AVLNode<elemT>* &root)
{
AVLNode<elemT> *p;
AVLNode<elemT> *w;
p = root->rlink; //p points to the left subtree of root
switch (p->bfactor)
{
case -1:
w = p->llink;
switch (w->bfactor) //adjust the balance factors
{
case -1:
root->bfactor = 0;
p->bfactor = 1;
break;
case 0:
root->bfactor = 0;
p->bfactor = 0;
break;
case 1:
root->bfactor = -1;
p->bfactor = 0;
}//end switch
w->bfactor = 0;
rotateToRight(p);
root->rlink = p;
rotateToLeft(root);
break;
case 0:
cerr << "Error: Cannot balance from the left." << endl;
break;
case 1:
root->bfactor = 0;
p->bfactor = 0;
rotateToLeft(root);
}//end switch;
}//end balanceFromRight
template <class elemT>
void AVLTreeType<elemT>::insertIntoAVL(AVLNode<elemT>* &root,
AVLNode<elemT> *newNode,
bool& isTaller)
{
if (root == NULL)
{
root = newNode;
isTaller = true;
numNodes++; // Increment numNodes
}
else if (root->info == newNode->info)
cerr << "No duplicates are allowed." << endl;
else if (root->info > newNode->info) //newItem goes in
//the left subtree
{
insertIntoAVL(root->llink, newNode, isTaller);
if (isTaller) //after insertion, the subtree grew in height
switch (root->bfactor)
{
case -1:
balanceFromLeft(root);
isTaller = false;
break;
case 0:
root->bfactor = -1;
isTaller = true;
break;
case 1:
root->bfactor = 0;
isTaller = false;
}//end switch
}//end if
else
{
insertIntoAVL(root->rlink, newNode, isTaller);
if (isTaller) //after insertion, the subtree grew in
//height
switch (root->bfactor)
{
case -1:
root->bfactor = 0;
isTaller = false;
break;
case 0:
root->bfactor = 1;
isTaller = true;
break;
case 1:
balanceFromRight(root);
isTaller = false;
}//end switch
}//end else
}//insertIntoAVL
template<class elemT>
void AVLTreeType<elemT>::insert(const elemT &newItem)
{
bool isTaller = false;
AVLNode<elemT> *newNode;
newNode = new AVLNode<elemT>;
newNode->info = newItem;
newNode->bfactor = 0;
newNode->llink = NULL;
newNode->rlink = NULL;
insertIntoAVL(root, newNode, isTaller);
}
template<class elemT>
void AVLTreeType<elemT>::inorderTraversal()
{
inorder(root);
}
template<class elemT>
void AVLTreeType<elemT>::inorderTraversal(ofstream &outputFile)
{
inorder(root, outputFile);
}
template<class elemT>
void AVLTreeType<elemT>::inorder(AVLNode<elemT> *p)
{
if (p != NULL)
{
inorder(p->llink);
cout << p->info << " ";
inorder(p->rlink);
}
}
template<class elemT>
void AVLTreeType<elemT>::inorder(AVLNode<elemT> *p, ofstream &outputFile)
{
if (p != NULL)
{
inorder(p->llink, outputFile);
outputFile << p->info << " ";
inorder(p->rlink, outputFile);
}
}
template<class elemT>
void AVLTreeType<elemT>::preorderTraversal()
{
preorder(root);
}
template<class elemT>
void AVLTreeType<elemT>::preorderTraversal(ofstream &outputFile)
{
preorder(root, outputFile);
}
template<class elemT>
void AVLTreeType<elemT>::preorder(AVLNode<elemT> *p)
{
if (p != NULL)
{
cout << p->info << " ";
preorder(p->llink);
preorder(p->rlink);
}
}
template<class elemT>
void AVLTreeType<elemT>::preorder(AVLNode<elemT> *p, ofstream &outputFile)
{
if (p != NULL)
{
outputFile << p->info << " ";
preorder(p->llink, outputFile);
preorder(p->rlink, outputFile);
}
}
template<class elemT>
void AVLTreeType<elemT>::postorderTraversal()
{
postorder(root);
}
template<class elemT>
void AVLTreeType<elemT>::postorderTraversal(ofstream &outputFile)
{
postorder(root, outputFile);
}
template <class elemT>
void AVLTreeType<elemT>::postorder(AVLNode<elemT> *p)
{
if (p != NULL)
{
postorder(p->llink);
postorder(p->rlink);
cout << p->info << " ";
}
}
template <class elemT>
void AVLTreeType<elemT>::postorder(AVLNode<elemT> *p, ofstream &outputFile)
{
if (p != NULL)
{
postorder(p->llink, outputFile);
postorder(p->rlink, outputFile);
outputFile << p->info << " ";
}
}
template<class elemT>
int AVLTreeType<elemT>::length() {
return numNodes;
}
template<class elemT>
AVLTreeType<elemT>::AVLTreeType()
{
root = NULL;
numNodes = 0;
}
#endif
//////////////////////////////////////////////////////////////
lab9.dat
////////////////////////////////////////////////////////////
D
M
W
T
A
R
X
S
J
B
N
C
K
I
Explanation / Answer
main.cpp
#include <iostream>
#include <string>
#include <fstream>
#include "avlTree.h"
using namespace std;
int main(int argc, char *argv[])
{
ifstream datafile;
char getData;
string inputfilename = argv[1];
//objects
AVLTreeType<string> *TreeObj = new AVLTreeType<string>();
if (argc < 1) {
std::cerr << "EXECUTE ERR!!" << endl << endl;
std::cerr << "Usage: " << argv[0] << " <filename.dat>" << endl << endl;
return 1;
}
//object creation opens outputfile
//inputfile specified inside function
//outputs Pre-Order traversal
TreeObj->readFromFile(inputfilename);
//covers post and inorder traversals
TreeObj->writeMethods();
cout << endl << endl << "DONE WITH AVL TRANSACTIONS! " << endl << endl;
//this is turned to a function inside class
/*
//read data from lab8.dat into array
datafile.open(argv[1]);
if (datafile.is_open()) {
while (datafile >> getData)
{
//handle preOrder
//insert node by node into AVL TREE
Treeobj.insert(getData);
}
//debug
cout << "great. your letters are inserted into the AVL" << endl < endl;
datafile.close();
*/
delete TreeObj;
return 0;
}
avlTree.h
#ifndef H_AVLTree
#define H_AVLTree
#include <iostream>
#include <fstream>
#include <string>
#include <cassert>
using namespace std;
template <class elemT>
class AVLNode
{
public:
elemT info;
int bfactor; // balance factor
AVLNode* llink;
AVLNode* rlink;
};
template <class elemT>
class AVLTreeType
{
public:
void InOrder(AVLNode<elemT>* &root);
void rotateToLeft(AVLNode<elemT>* &root);
void rotateToRight(AVLNode<elemT>* &root);
void balanceFromLeft(AVLNode<elemT>* &root);
void balanceFromRight(AVLNode<elemT>* &root);
void insert(const elemT &newItem); //this will call the below function
void insertIntoAVL(AVLNode<elemT>* &root, AVLNode<elemT> *newNode, bool& isTaller);
//read from File
void readFromFile(string);
//write to file
void writeMethods();
//show nodecount (should be 14)
void showCounter();
//for lab9
void outputPostOrder(AVLNode<elemT>* &root);
//constructor
AVLTreeType(); //default constructor
~AVLTreeType();
AVLNode<elemT>* root;
private:
int counter;
ofstream outputFile;
};
/*
IMPLEMENTATION
*/
template <class elemT>
void AVLTreeType<elemT>::rotateToLeft(AVLNode<elemT>* &root)
{
AVLNode<elemT> *p; //pointer to the root of the
//right subtree of root
if (root == NULL)
cerr << "Error in the tree" << endl;
else if (root->rlink == NULL)
cerr << "Error in the tree:"
<<" No right subtree to rotate." << endl;
else
{
p = root->rlink;
root->rlink = p->llink; //the left subtree of p becomes
//the right subtree of root
p->llink = root;
root = p; //make p the new root node
}
}//rotateLeft
template <class elemT>
void AVLTreeType<elemT>::rotateToRight(AVLNode<elemT>* &root)
{
AVLNode<elemT> *p; //pointer to the root of
//the left subtree of root
if (root == NULL)
cerr << "Error in the tree" << endl;
else if (root->llink == NULL)
cerr << "Error in the tree:"
<< " No left subtree to rotate." << endl;
else
{
p = root->llink;
root->llink = p->rlink; //the right subtree of p becomes
//the left subtree of root
p->rlink = root;
root = p; //make p the new root node
}
}//end rotateRight
template <class elemT>
void AVLTreeType<elemT>::balanceFromLeft(AVLNode<elemT>* &root)
{
AVLNode<elemT> *p;
AVLNode<elemT> *w;
p = root->llink; //p points to the left subtree of root
switch (p->bfactor)
{
case -1:
root->bfactor = 0;
p->bfactor = 0;
rotateToRight(root);
break;
case 0:
cerr << "Error: Cannot balance from the left." << endl;
break;
case 1:
w = p->rlink;
switch (w->bfactor) //adjust the balance factors
{
case -1:
root->bfactor = 1;
p->bfactor = 0;
break;
case 0:
root->bfactor = 0;
p->bfactor = 0;
break;
case 1:
root->bfactor = 0;
p->bfactor = -1;
}//end switch
w->bfactor = 0;
rotateToLeft(p);
root->llink = p;
rotateToRight(root);
}//end switch;
}//end balanceFromLeft
template <class elemT>
void AVLTreeType<elemT>::balanceFromRight(AVLNode<elemT>* &root)
{
AVLNode<elemT> *p;
AVLNode<elemT> *w;
p = root->rlink; //p points to the left subtree of root
switch (p->bfactor)
{
case -1:
w = p->llink;
switch (w->bfactor) //adjust the balance factors
{
case -1:
root->bfactor = 0;
p->bfactor = 1;
break;
case 0:
root->bfactor = 0;
p->bfactor = 0;
break;
case 1:
root->bfactor = -1;
p->bfactor = 0;
}//end switch
w->bfactor = 0;
rotateToRight(p);
root->rlink = p;
rotateToLeft(root);
break;
case 0:
cerr << "Error: Cannot balance from the left." << endl;
break;
case 1:
root->bfactor = 0;
p->bfactor = 0;
rotateToLeft(root);
}//end switch;
}//end balanceFromRight
template <class elemT>
void AVLTreeType<elemT>::insertIntoAVL(AVLNode<elemT>* &root,
AVLNode<elemT> *newNode,
bool& isTaller)
{
if (root == NULL)
{
root = newNode;
isTaller = true;
}
else if (root->info == newNode->info)
cerr << "No duplicates are allowed." << endl;
else if (root->info > newNode->info) //newItem goes in
//the left subtree
{
//RECURSIVE CALL
insertIntoAVL(root->llink, newNode, isTaller);
if (isTaller) //after insertion, the subtree grew in height
switch (root->bfactor)
{
case -1:
balanceFromLeft(root);
isTaller = false;
break;
case 0:
root->bfactor = -1;
isTaller = true;
break;
case 1:
root->bfactor = 0;
isTaller = false;
}//end switch
}//end if
else
{
insertIntoAVL(root->rlink, newNode, isTaller);
if (isTaller) //after insertion, the subtree grew in
//height
switch (root->bfactor)
{
case -1:
root->bfactor = 0;
isTaller = false;
break;
case 0:
root->bfactor = 1;
isTaller = true;
break;
case 1:
balanceFromRight(root);
isTaller = false;
}//end switch
}//end else
}//insertIntoAVL
template<class elemT>
void AVLTreeType<elemT>::insert(const elemT &newItem)
{
bool isTaller = false;
AVLNode<elemT> *newNode;
newNode = new AVLNode<elemT>;
newNode->info = newItem;
newNode->bfactor = 0;
newNode->llink = NULL;
newNode->rlink = NULL;
insertIntoAVL(root, newNode, isTaller);
}
/*
CONSTRUCTOR & DESTRUCTOR
*/
template <class elemT>
AVLTreeType<elemT>::AVLTreeType()
{
root = NULL;
//add outputfile creation
outputFile.open("cheilmanlab9.out");
cout << "output cheilmanlab9.out created" << endl;
}
template <class elemT>
AVLTreeType<elemT>::~AVLTreeType()
{
cout << "Closing ouputfile:::" << endl;
outputFile.close();
}
/*
CUSTOM METHODS & IMPLEMENTATIONS
*/
//pass argv[1] as string
template <class elemT>
void AVLTreeType<elemT>::readFromFile(string argFile) {
ifstream datafile;
string dataList;
string getData;
cout << "Reading data from Argument..." << endl << endl;
outputFile << "Reading data from Argument..." << endl << endl;
//read data from lab8.dat into array
datafile.open(argFile);
if (datafile.is_open())
{
cout << "PreOrder: ";
outputFile << "PreOrder: ";
int c = 0;
while (datafile >> getData)
{
//outputfile already created on object creation
//handle preOrder writeout
//dataList[c] = getData;
insert(getData); //insert info int AVL TREE
cout << getData;
outputFile << getData;
//c++;
counter++; //nodecounter (private var)
}
cout << endl << "------------------------------" << endl;
outputFile << endl << "------------------------------" << endl;
}
else{
cout << "ERROR OPENING DATA FILE!!!. EXITING NO POINT TO LIFE. NO 42..." << endl;
assert(1 == 2);
}
datafile.close();
}
//outputfile writing
//ofstream outputFile (private var)
template <class elemT>
void AVLTreeType<elemT>::writeMethods(){
//output
outputFile.open("cheilmanlab9.out");
//try adrian's method
//INORDER PRINTOUT
cout << "InOrder: ";
outputFile << "InOrder: ";
InOrder(root);
cout << endl << "------------------------------" << endl;
outputFile << endl << "------------------------------" << endl;
//POSTORDER PRINTOUT
cout << "PostOrder: ";
outputFile << "PostOrder: ";
outputPostOrder(root);
cout << endl << "------------------------------" << endl;
outputFile << endl << "------------------------------" << endl;
}
//counter (private val)
template<class elemT>
void AVLTreeType<elemT>::showCounter()
{ cout << "TOTAL NODES: " << counter << endl; }
//inOrder function
//recursion
template<class elemT>
void AVLTreeType<elemT>::InOrder(AVLNode<elemT>* &root)
{
if (root->llink != NULL)
{
InOrder(root->llink);
} //move to left node
cout << root->info;
outputFile << root->info;
if (root->rlink != NULL)
{
//if right node exists, check for left & right leafs
if (root->rlink->llink != NULL)
InOrder(root->rlink->llink);
//if left leaf, move to it
cout << root->rlink->info;
outputFile << root->rlink->info;
if(root->rlink->rlink != NULL) //same as left leaf but with right
InOrder(root->rlink->rlink);
}
}
//postorder output traversal for lab 9
//recursively
template<class elemT>
void AVLTreeType<elemT>::outputPostOrder(AVLNode<elemT>* &root)
{
if (root->llink != NULL)
{ outputPostOrder(root->llink); } //move to node[0]
if (root->rlink != NULL)
{ outputPostOrder(root->rlink); } //move to rightnode
outputFile << root->info;
cout << root->info;
}
#endif
lab9.dat
D
M
W
T
A
R
X
S
J
B
N
C
K
I
AvlTree-arod.h
#ifndef H_AVLTree
#define H_AVLTree
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
template <class Type>
class Node
{
public:
Type info;
int bfactor; // balance factor
Node* left;
Node* right;
};
template <class Type>
class AVLTree
{
public:
void insert(const Type &item);
void initializeTree();
void rotateLeft(Node<Type>* &root);
void rotateRight(Node<Type>* &root);
void balanceLeft(Node<Type>* &root);
void balanceRight(Node<Type>* &root);
void insertIntoAVL(Node<Type>* &root, Node<Type> *newNode, bool& isTaller);
string readFile(); //return collected string to main file
void writeFile();
void showCounter();
void outputInOrder(Node<Type>* &root);
void outputPostOrder(Node<Type>* &root);
AVLTree(); //default constructor
~AVLTree();
Node<Type>* root;
private:
int counter; //total nodes in tree
ofstream outputFile; //arodriguez108lab9.out
};
template<class Type>
AVLTree<Type>::~AVLTree()
{
cout << "Closing output file: arodriguez108lab9.out" << endl;
outputFile.close();
}
template<class Type>
void AVLTree<Type>::initializeTree()
{
cout << "Creating output file: cheilmanlab9.out" << endl;
outputFile.open("cheilmanlab9.out");
}
template <class Type>
void AVLTree<Type>::rotateLeft(Node<Type>* &root)
{
Node<Type> *p; //pointer to the root of the
//right subtree of root
if (root == NULL)
cerr << "Error in the tree" << endl;
else if (root->right == NULL)
cerr << "Error in the tree:"
<<" No right subtree to rotate." << endl;
else
{
p = root->right;
root->right = p->left; //the left subtree of p becomes
//the right subtree of root
p->left = root;
root = p; //make p the new root node
}
}//rotateLeft
template <class Type>
void AVLTree<Type>::rotateRight(Node<Type>* &root)
{
Node<Type> *p; //pointer to the root of
//the left subtree of root
if (root == NULL)
cerr << "Error in the tree" << endl;
else if (root->left == NULL)
cerr << "Error in the tree:"
<< " No left subtree to rotate." << endl;
else
{
p = root->left;
root->left = p->right; //the right subtree of p becomes
//the left subtree of root
p->right = root;
root = p; //make p the new root node
}
}//end rotateRight
template <class Type>
void AVLTree<Type>::balanceLeft(Node<Type>* &root)
{
Node<Type> *p;
Node<Type> *w;
p = root->left; //p points to the left subtree of root
switch (p->bfactor)
{
case -1:
root->bfactor = 0;
p->bfactor = 0;
rotateRight(root);
break;
case 0:
cerr << "Error: Cannot balance from the left." << endl;
break;
case 1:
w = p->right;
switch (w->bfactor) //adjust the balance factors
{
case -1:
root->bfactor = 1;
p->bfactor = 0;
break;
case 0:
root->bfactor = 0;
p->bfactor = 0;
break;
case 1:
root->bfactor = 0;
p->bfactor = -1;
}//end switch
w->bfactor = 0;
rotateLeft(p);
root->left = p;
rotateRight(root);
}//end switch;
}//end balanceFromLeft
template <class Type>
void AVLTree<Type>::balanceRight(Node<Type>* &root)
{
Node<Type> *p;
Node<Type> *w;
p = root->right; //p points to the left subtree of root
switch (p->bfactor)
{
case -1:
w = p->left;
switch (w->bfactor) //adjust the balance factors
{
case -1:
root->bfactor = 0;
p->bfactor = 1;
break;
case 0:
root->bfactor = 0;
p->bfactor = 0;
break;
case 1:
root->bfactor = -1;
p->bfactor = 0;
}//end switch
w->bfactor = 0;
rotateRight(p);
root->right = p;
rotateLeft(root);
break;
case 0:
cerr << "Error: Cannot balance from the left." << endl;
break;
case 1:
root->bfactor = 0;
p->bfactor = 0;
rotateLeft(root);
}//end switch;
}//end balanceFromRight
template <class Type>
void AVLTree<Type>::insertIntoAVL(Node<Type>* &root, Node<Type> *newNode, bool& isTaller)
{
if (root == NULL)
{
root = newNode;
isTaller = true;
}
else if (root->info == newNode->info)
cerr << "No duplicates are allowed." << endl;
else if (root->info > newNode->info) //newItem goes in
//the left subtree
{
insertIntoAVL(root->left, newNode, isTaller);
if (isTaller) //after insertion, the subtree grew in height
switch (root->bfactor)
{
case -1:
balanceLeft(root);
isTaller = false;
break;
case 0:
root->bfactor = -1;
isTaller = true;
break;
case 1:
root->bfactor = 0;
isTaller = false;
}//end switch
}//end if
else
{
insertIntoAVL(root->right, newNode, isTaller);
if (isTaller) //after insertion, the subtree grew in
//height
switch (root->bfactor)
{
case -1:
root->bfactor = 0;
isTaller = false;
break;
case 0:
root->bfactor = 1;
isTaller = true;
break;
case 1:
balanceRight(root);
isTaller = false;
}//end switch
}//end else
}//insertIntoAVL
template<class Type>
void AVLTree<Type>::insert(const Type &item)
{
bool isTaller = false;
Node<Type> *newNode;
newNode = new Node<Type>;
newNode->info = item;
newNode->bfactor = 0;
newNode->left = NULL;
newNode->right = NULL;
insertIntoAVL(root, newNode, isTaller);
}
template<class Type>
AVLTree<Type>::AVLTree()
{
root = NULL;
counter = 0;
}
template<class Type>
void AVLTree<Type>::showCounter()
{
cout << "Total Nodes: " << counter << endl;
outputFile << "Total Nodes: " << counter << endl;
}
template<class Type>
string AVLTree<Type>::readFile()
{
cout << "Reading data from: lab9.dat" << endl;
outputFile << "Reading data from: lab9.dat" << endl;
ifstream inputFile("lab9.dat"); //open file: lab9.dat
Type sym; //hold char input
string line; //hold line of input
cout << "PreOrder: ";
outputFile << "PreOrder: ";
int n = 0; //index
while(inputFile >> sym)
{
line[n] = sym;
insert(line[n]); //insert info into AVLTree
cout << line[n];
outputFile << line[n];
n++;
counter++; //count total nodes in tree
}
cout << endl;
outputFile << endl;
inputFile.close();
return line;
}
template<class Type>
void AVLTree<Type>::writeFile()
{
//InOrder
cout << "InOrder: ";
outputFile << "InOrder: ";
outputInOrder(root);
outputFile << endl;
cout << endl;
//PostOrder
cout << "PostOrder: ";
outputFile << "PostOrder: ";
outputPostOrder(root);
outputFile << endl;
cout << endl;
cout << "Finished..." << endl;
}
//NEED THIS FOR LAB
template<class Type>
void AVLTree<Type>::outputInOrder(Node<Type>* &root)
{
if(root->left != NULL)
outputInOrder(root->left); //advance to left node
cout << root->info;
outputFile << root->info;
if(root->right != NULL)
{
if(root->right->left != NULL) //if the right node exists, check if it has a left leaf
{ outputInOrder(root->right->left); } //if true, move to that leaf
cout << root->right->info;
outputFile << root->right->info;
if(root->right->right != NULL) //if the right node exists, check if it has a right leaf
{ outputInOrder(root->right->right); } //if true, move to that leaf
}
}
//NEED THIS FOR LAB
template<class Type>
void AVLTree<Type>::outputPostOrder(Node<Type>* &root)
{
if(root->left != NULL)
{
outputPostOrder(root->left); //advance to node[0]
}
if(root->right != NULL)
{
outputPostOrder(root->right); //advance to right node
}
outputFile << root->info;
cout << root->info;
}
#endif
cheilmanlab9.out
Reading data from Argument...
PreOrder: DMWTARXSJBNCKI
------------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.