Define a class template for an AVL tree. Create an object of such tree. Create a

Question

Define a class template for an AVL tree.
Create an object of such tree.
Create a menu where you can insert, delete, and find elements.
The menu must also include a print function that will list the preorder, inorder, and postorder
visualization of the tree (Your print function must call all tree traversal types at the same time).
The function insert must have 2 choices: insert_one() and insert_k().
insert_one() will ask the user for one value to get inserted.
insert_k() will ask the user for the size of input (k) and a list of k elements will be read from the console/file.
Both functions must give the option to populate it with: Int, Float or Character values.
(Character values will be ordered based on their ASCII value).
Once a tree of any type is created you must be able to manipulate it at all times.
If a new tree of a different type is created, don't replace your current tree with it.
You can potentially have one tree of each type at any given time.

Write a function to find the depth of a given node and the depth of the tree.

Explanation / Answer

#include #include #include #define FALSE 0 #define TRUE 1 struct AVLNode { int data ; int balfact ; AVLNode *left ; AVLNode *right ; } ; class avltree { private : AVLNode *root ; public : avltree( ) ; AVLNode* insert ( int data, int *h ) ; static AVLNode* buildtree ( AVLNode *root, int data, int *h ) ; void display( AVLNode *root ) ; AVLNode* deldata ( AVLNode* root, int data, int *h ) ; static AVLNode* del ( AVLNode *node, AVLNode* root, int *h ) ; static AVLNode* balright ( AVLNode *root, int *h ) ; static AVLNode* balleft ( AVLNode* root, int *h ) ; void setroot ( AVLNode *avl ) ; ~avltree( ) ; static void deltree ( AVLNode *root ) ; } ; avltree :: avltree( ) { root = NULL ; } AVLNode* avltree :: insert ( int data, int *h ) { root = buildtree ( root, data, h ) ; return root ; } AVLNode* avltree :: buildtree ( AVLNode *root, int data, int *h ) { AVLNode *node1, *node2 ; if ( root == NULL ) { root = new AVLNode ; root -> data = data ; root -> left = NULL ; root -> right = NULL ; root -> balfact = 0 ; *h = TRUE ; return ( root ) ; } if ( data data ) { root -> left = buildtree ( root -> left, data, h ) ; // If left subtree is higher if ( *h ) { switch ( root -> balfact ) { case 1 : node1 = root -> left ; if ( node1 -> balfact == 1 ) { cout left = node1 -> right ; node1 -> right = root ; root -> balfact = 0 ; root = node1 ; } else { cout right ; node1 -> right = node2 -> left ; node2 -> left = node1 ; root -> left = node2 -> right ; node2 -> right = root ; if ( node2 -> balfact == 1 ) root -> balfact = -1 ; else root -> balfact = 0 ; if ( node2 -> balfact == -1 ) node1 -> balfact = 1 ; else node1 -> balfact = 0 ; root = node2 ; } root -> balfact = 0 ; *h = FALSE ; break ; case 0 : root -> balfact = 1 ; break ; case -1 : root -> balfact = 0 ; *h = FALSE ; } } } if ( data > root -> data ) { root -> right = buildtree ( root -> right, data, h ) ; if ( *h ) { switch ( root -> balfact ) { case 1 : root -> balfact = 0 ; *h = FALSE ; break ; case 0 : root -> balfact = -1 ; break ; case -1 : node1 = root -> right ; if ( node1 -> balfact == -1 ) { cout right = node1 -> left ; node1 -> left = root ; root -> balfact = 0 ; root = node1 ; } else { cout left ; node1 -> left = node2 -> right ; node2 -> right = node1 ; root -> right = node2 -> left ; node2 -> left = root ; if ( node2 -> balfact == -1 ) root -> balfact = 1 ; else root -> balfact = 0 ; if ( node2 -> balfact == 1 ) node1 -> balfact = -1 ; else node1 -> balfact = 0 ; root = node2 ; } root -> balfact = 0 ; *h = FALSE ; } } } return ( root ) ; } void avltree :: display ( AVLNode* root ) { if ( root != NULL ) { display ( root -> left ) ; cout data == 13 ) cout left, data, h ) ; if ( *h ) root = balright ( root, h ) ; } else { if ( data > root -> data ) { root -> right = deldata ( root -> right, data, h ) ; if ( *h ) root = balleft ( root, h ) ; } else { node = root ; if ( node -> right == NULL ) { root = node -> left ; *h = TRUE ; delete ( node ) ; } else { if ( node -> left == NULL ) { root = node -> right ; *h = TRUE ; delete ( node ) ; } else { node -> right = del ( node -> right, node, h ) ; if ( *h ) root = balleft ( root, h ) ; } } } } } return ( root ) ; } AVLNode* avltree :: del ( AVLNode *succ, AVLNode *node, int *h ) { AVLNode *temp = succ ; if ( succ -> left != NULL ) { succ -> left = del ( succ -> left, node, h ) ; if ( *h ) succ = balright ( succ, h ) ; } else { temp = succ ; node -> data = succ -> data ; succ = succ -> right ; delete ( temp ) ; *h = TRUE ; } return ( succ ) ; } AVLNode* avltree :: balright ( AVLNode *root, int *h ) { AVLNode *temp1, *temp2 ; switch ( root -> balfact ) { case 1 : root -> balfact = 0 ; break ; case 0 : root -> balfact = -1 ; *h = FALSE ; break ; case -1 : temp1 = root -> right ; if ( temp1 -> balfact left ; temp1 -> left = root ; if ( temp1 -> balfact == 0 ) { root -> balfact = -1 ; temp1 -> balfact = 1 ; *h = FALSE ; } else { root -> balfact = temp1 -> balfact = 0 ; } root = temp1 ; } else { cout left ; temp1 -> left = temp2 -> right ; temp2 -> right = temp1 ; root -> right = temp2 -> left ; temp2 -> left = root ; if ( temp2 -> balfact == -1 ) root -> balfact = 1 ; else root -> balfact = 0 ; if ( temp2 -> balfact == 1 ) temp1 -> balfact = -1 ; else temp1 -> balfact = 0 ; root = temp2 ; temp2 -> balfact = 0 ; } } return ( root ) ; } AVLNode* avltree :: balleft ( AVLNode *root, int *h ) { AVLNode *temp1, *temp2 ; switch ( root -> balfact ) { case -1 : root -> balfact = 0 ; break ; case 0 : root -> balfact = 1 ; *h = FALSE ; break ; case 1 : temp1 = root -> left ; if ( temp1 -> balfact >= 0 ) { cout left = temp1 -> right ; temp1 -> right = root ; if ( temp1 -> balfact == 0 ) { root -> balfact = 1 ; temp1 -> balfact = -1 ; *h = FALSE ; } else { root -> balfact = temp1 -> balfact = 0 ; } root = temp1 ; } else { cout right ; temp1 -> right = temp2 -> left ; temp2 -> left = temp1 ; root -> left = temp2 -> right ; temp2 -> right = root ; if ( temp2 -> balfact == 1 ) root -> balfact = -1 ; else root -> balfact = 0 ; if ( temp2-> balfact == -1 ) temp1 -> balfact = 1 ; else temp1 -> balfact = 0 ; root = temp2 ; temp2 -> balfact = 0 ; } } return ( root ) ; } void avltree :: setroot ( AVLNode *avl ) { root = avl ; } avltree :: ~avltree( ) { deltree ( root ) ; } void avltree :: deltree ( AVLNode *root ) { if ( root != NULL ) { deltree ( root -> left ) ; deltree ( root -> right ) ; } delete ( root ) ; } void main( ) { avltree at ; AVLNode *avl = NULL ; int h ; clrscr(); avl = at.insert ( 20, &h ) ; at.setroot ( avl ) ; avl = at.insert ( 6, &h ) ; at.setroot ( avl ) ; avl = at.insert ( 29, &h ) ; at.setroot ( avl ) ; avl = at.insert ( 5, &h ) ; at.setroot ( avl ) ; avl = at.insert ( 12, &h ) ; at.setroot ( avl ) ; avl = at.insert ( 25, &h ) ; at.setroot ( avl ) ; avl = at.insert ( 32, &h ) ; at.setroot ( avl ) ; avl = at.insert ( 10, &h ) ; at.setroot ( avl ) ; avl = at.insert ( 15, &h ) ; at.setroot ( avl ) ; avl = at.insert ( 27, &h ) ; at.setroot ( avl ) ; avl = at.insert ( 13, &h ) ; at.setroot ( avl ) ; cout

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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