hi expert. this is what i need help with: write a test program but generate only

Question

hi expert. this is what i need help with: write a test program but generate only 40 random integer numbers less than 100. Then create only an AVL tree therefore no need for comparison. In addition write methods to accomplish the following tasks: Show all the leaf nodes Show all the duplicated nodes, if any, while during insertion but don't insert the duplicates into the AVL tree. Show all the nodes in PreOrder, InOrder and PostOrder traversals. You have to use the class AVLTree that is in your textbook. Show all the non-leaf nodes Show the height of the tree

Explanation / Answer

class AVLNode { AVLNode left, right; int data; int height; public AVLNode() { left = null; right = null; data = 0; height = 0; } public AVLNode(int n) { left = null; right = null; data = n; height = 0; } } class AVLTree { private AVLNode root; public AVLTree() { root = null; } public boolean isEmpty() { return root == null; } public void makeEmpty() { root = null; } public void insert(int data) { root = insert(data, root); } private int height(AVLNode t ) { return t == null ? -1 : t.height; } private int max(int lhs, int rhs) { return lhs > rhs ? lhs : rhs; } private AVLNode insert(int x, AVLNode t) { if (t == null) t = new AVLNode(x); else if (x t.right.data) t = rotateWithRightChild( t ); else t = doubleWithRightChild( t ); } else ; t.height = max( height( t.left ), height( t.right ) ) + 1; return t; } private AVLNode rotateWithLeftChild(AVLNode k2) { AVLNode k1 = k2.left; k2.left = k1.right; k1.right = k2; k2.height = max( height( k2.left ), height( k2.right ) ) + 1; k1.height = max( height( k1.left ), k2.height ) + 1; return k1; } private AVLNode rotateWithRightChild(AVLNode k1) { AVLNode k2 = k1.right; k1.right = k2.left; k2.left = k1; k1.height = max( height( k1.left ), height( k1.right ) ) + 1; k2.height = max( height( k2.right ), k1.height ) + 1; return k2; } private AVLNode doubleWithLeftChild(AVLNode k3) { k3.left = rotateWithRightChild( k3.left ); return rotateWithLeftChild( k3 ); } private AVLNode doubleWithRightChild(AVLNode k1) { k1.right = rotateWithLeftChild( k1.right ); return rotateWithRightChild( k1 ); } public int countNodes() { return countNodes(root); } private int countNodes(AVLNode r) { if (r == null) return 0; else { int l = 1; l += countNodes(r.left); l += countNodes(r.right); return l; } } public boolean search(int val) { return search(root, val); } private boolean search(AVLNode r, int val) { boolean found = false; while ((r != null) && !found) { int rval = r.data; if (val rval) r = r.right; else { found = true; break; } found = search(r, val); } return found; } public void inorder() { inorder(root); } private void inorder(AVLNode r) { if (r != null) { inorder(r.left); System.out.print(r.data +" "); inorder(r.right); } } public void preorder() { preorder(root); } private void preorder(AVLNode r) { if (r != null) { System.out.print(r.data +" "); preorder(r.left); preorder(r.right); } } public void postorder() { postorder(root); } private void postorder(AVLNode r) { if (r != null) { postorder(r.left); postorder(r.right); System.out.print(r.data +" "); } } } class AVLTreeTest { public static void main(String[] args) { AVLTree avlt = new AVLTree(); System.out.println("AVLTree Tree Test "); for(int i=0; i

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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