Write a program that will create an AVL tree by reading character data from lab9

Question

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 (functions are missing
in avlTree.h) traversal.

PreOrder Traversal Result: MDBACJIKTRNSWX
InOrder Traversal Result: ABCDIJKMNRSTWX
PostOrder Traversal Result: ACBIKJDNSRXWTM
Design your output (to YourIslandIDlab9.out) to be pleasing and
informative.

-------------------------------------------------------------.h file---------------------------------------------

#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);

AVLTreeType(); //default constructor

private:
AVLNode<elemT>* root;

};

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
{
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>
AVLTreeType<elemT>::AVLTreeType()
{
root = NULL;
}

#endif

Explanation / Answer

void bstree::preorder(nodeptr p) { if (p!=NULL) { coutleft); coutright); coutright = NULL; p->height=0; if (p==NULL) { coutelement) { p=srl(p); } else { p = drl(p); } } } else if (x>p->element) { insert(x,p->right); if ((bsheight(p->right) - bsheight(p->left))==2) { if (x > p->right->element) { p=srr(p); } else { p = drr(p); } } } else { coutleft == NULL) && (p->right == NULL)) { d=p; free(d); p=NULL; coutright)) + 1; p2->height = max(bsheight(p2->left),p1->height) + 1; return p2; } nodeptr bstree:: srr(nodeptr &p1) { nodeptr p2; p2 = p1->right; p1->right = p2->left; p2->left = p1; p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1; p2->height = max(p1->height,bsheight(p2->right)) + 1; return p2; } nodeptr bstree:: drl(nodeptr &p1) { p1->left=srr(p1->left); return srl(p1); } nodeptr bstree::drr(nodeptr &p1) { p1->right = srl(p1->right); return srr(p1); } int bstree::nonodes(nodeptr p) { int count=0; if (p!=NULL) { nonodes(p->left); nonodes(p->right); count++; } return count; } int main() { //clrscr(); nodeptr root,root1,min,max;//,flag; int a,choice,findele,delele; char ch='y'; bstree bst; //system("clear"); root = NULL; root1=NULL; cout

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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