Question

TkA CHRI - TREE UTH A HEAPOF PRESDNS CENETH CSC 236-Lab 6 (2 programs) trees 1. Given the two binary trees below: 14 18 16) Write a method called swapSubtrees, which swaps all of the left and right subtrees in the above binary trees. Add this method to the class BinaryTree and create a program to test this method for these 2 trees. Show the original trees and the resulting trees. Note: To test your algorithm, first create a binary search tree. Write a method called singleParent, which returns the number of nodes in a binary tree fhd method to the class BinaryTree and create a program to test this method. Note: To test your algorithm, first create a binary search tree. child for the 2 trees qiven in the above, Add this 2. Start with an empty heap, and enter ten items with priorities 1 through 10. Draw the resd entries from the heap that you created in the above - Now remove exercise. Draw the resulting heap, Lab 6 Tree Directions Problem #1: a) Create a TreeNode class with the following methods: default constructor, two ceti eft cotn ctors, copy constructor, getValue, getLeft, getRight, setValue, b) Create a BTInterface with the following abstract methods: getRoot, setRoot, isEmpty, swapSubtrees, singleParent, preorder, postOrder, inOrder, insert c) Create an abstract BinaryTree class that implements the interface. Include the default constructor, a private helper method called checkNode for singleParent() and toString. Make insert an abstract method. constructor, overloaded consteuesom Binary Tree with the following methods: default variable length parameter), insert, d) Derive a BinarySearch Tree class e) Create a TreeDemo class that creates two BinarySearch Tree objects. Use default and overloaded constructors. For tree one: call the methods make Tree (makes a complete tree), print Tree, swapSubtrees, print Tree. Simliar for tree two. Also, print out the number of single parents in each tree. Define make Tree and print Tree in this class,

please do this lab in Java in given instructions by tomorrow morning.

Answer 1

code

solution

Note:please post other questions as a separated

1 // Binary SearchTree.java class Binary SearchTree class Binary_node int nodekey Binary_node node_left, node_right; public Binary_node (int node_item) { = node item; = node_right = null; nodekey node left } Binary_node rootnode; / Constructor Binary SearchTree ( { null rootnode = add Record // void insert (int node key)

add_Record (rootnode, nodekey); rootnode /recursive function Binary_node add_Record (Binary_node rootnode, int nodekey) { / check the treea if (rootnode = null) Binary_node (nodekey); rootnode= new return rootnode; } if (nodekey < rootnode.nodekey) rootnode.node left = add Record (rootnode.node left, nodekey) else if nodekey rootnode.nodekey) rootnode.node right = add_Record (rootnode.node_right, nodekey) return rootnode method to call the InorderRec void inordertravarsel) { inorderRec (rootnode);

void inorderRec (Binary_node rootnode) if (rootnode != null) inorderRec (rootnode.node left); System.out.println(rootnode.nodekey); inorderRec (rootnode.node_right); } void swap ( swap Sub trees (rootnode); swap of subtrees Binarynode swap_Sub_trees (Binary_node Nnde) { if (Nnde == null) return Nnde Binary node node left Binary_node node_right = swap Sub trees (Nnde.node right); swap Sub trees (Nnde.node left); node_right; Nnde.node right = node left; Nnde.node left

return Nnde; single node parent private int single_ParentHelp (Binary_node rootnode, int count) { if (rootnode=null||(rootnode.node left==null & &rootnode.node righ t=null )) return count; single ParentHelp (rootnode.node left, count); if (rootnode.node_left==null||rootnode.node_right==null) count = count ++; single_ParentHelp (rootnode.node_right, count), count return count; 1 public int single Parent ( return single_ParentHelp(rootnode, 0); // main method public static void main (String [] args) { Binary SearchTree Binary SearchTree ); Binary SearchTree tree 1 = Binary SearchTree tree 2 = new new

tree 1.insert (1) tree 1.insert (2); tree 1.insert (4); tree 1.insert (5); tree_1.insert (3); tree_1.insert (6); System.out.println ("Tree 1"); tree 1.inordertravarsel (); tree_1.swap (); System.out.println("tree_1 in swapped order"); tree 1.inordertravarsel (); System.out.println("single parent in tree_1 : "tree 1.single Parent )); tree 2.insert (14); tree 2.insert (4); tree 2.insert (3); tree 2.insert (9); tree 2.insert (7); tree 2.insert (5); tree 2.insert (15) tree_2.insert (18); tree 2.insert (16) tree 2.insert (17); tree_2.insert (20);

System.out.println"Tree 2"); tree 2.inordertravarsel ); tree 2.swap (); System.out.println("tree_2 in swapped order"); tree 2.inordertravarsel); System.out.println("single parent in tree_2 : "tree_2.single_Parent ()); 1 }

//output

D:N>javac Binary_SearchT ree.java DENjava Binary_SearchT ree Tree 1 tree_1 in swapped order single parent in tree 1 Tree 2 : 3 14 15 16 7 18 20 tree_2 in swapped order 20 18 17 16 15 14 single parent in tree 2: 4 D:N

//copyable code

1

// Binary_SearchTree.java

class Binary_SearchTree

{

     class Binary_node

    {

         int nodekey;

         Binary_node node_left, node_right;

         public Binary_node(int node_item)

        {

             nodekey = node_item;

             node_left = node_right = null;

         }

     }

  

     Binary_node rootnode;

     // Constructor

     Binary_SearchTree()

    {

         rootnode = null;

     }

     // add_Record()

     void insert(int nodekey)

    {

        rootnode = add_Record(rootnode, nodekey);

     }

   

     // recursive function

     Binary_node add_Record(Binary_node rootnode, int nodekey)

    {

         // check the treea

         if (rootnode == null) {

             rootnode = new Binary_node(nodekey);

             return rootnode;

         }

       

         if (nodekey < rootnode.nodekey)

             rootnode.node_left = add_Record(rootnode.node_left, nodekey);

         else if (nodekey > rootnode.nodekey)

             rootnode.node_right = add_Record(rootnode.node_right, nodekey);

      

         return rootnode;

     }

     // method to call the InorderRec()

     void inordertravarsel()

    {

        inorderRec(rootnode);

     }

     void inorderRec(Binary_node rootnode)

    {

         if (rootnode != null)

        {

             inorderRec(rootnode.node_left);

             System.out.println(rootnode.nodekey);

             inorderRec(rootnode.node_right);

         }

     }

  

  

    void swap()

    {

        swap_Sub_trees(rootnode);

     }

    // swap of subtrees

    Binary_node swap_Sub_trees(Binary_node Nnde)

     {

      

         if (Nnde == null)

             return Nnde;

        

         Binary_node node_left = swap_Sub_trees(Nnde.node_left);

         Binary_node node_right = swap_Sub_trees(Nnde.node_right);

        

         Nnde.node_left = node_right;

         Nnde.node_right = node_left;

         return Nnde;

     }

      

    // single node parent

     private int single_ParentHelp(Binary_node rootnode,int count)

    {

         if(rootnode==null||(rootnode.node_left==null&&rootnode.node_right==null))

             return count;

         count = single_ParentHelp(rootnode.node_left, count);

         if(rootnode.node_left==null||rootnode.node_right==null)

             count ++;

         count = single_ParentHelp(rootnode.node_right, count);

         return count;

     }

  

     public int single_Parent()

    {

         return single_ParentHelp(rootnode, 0);

     }

  

     // main method

     public static void main(String[] args)

    {

         Binary_SearchTree tree_1 = new Binary_SearchTree();

        Binary_SearchTree tree_2 = new Binary_SearchTree();

        

         tree_1.insert(1);

         tree_1.insert(2);

         tree_1.insert(4);

         tree_1.insert(5);

         tree_1.insert(3);

         tree_1.insert(6);

       

   

        System.out.println("Tree 1");

         tree_1.inordertravarsel();

        tree_1.swap();

        System.out.println("tree_1 in swapped order");

        tree_1.inordertravarsel();

        System.out.println("single parent in tree_1 : "+tree_1.single_Parent());

           

         tree_2.insert(14);

         tree_2.insert(4);

         tree_2.insert(3);

         tree_2.insert(9);

         tree_2.insert(7);

         tree_2.insert(5);

         tree_2.insert(15);

         tree_2.insert(18);

         tree_2.insert(16);

         tree_2.insert(17);

         tree_2.insert(20);

       

     

        System.out.println("Tree 2");

         tree_2.inordertravarsel();

        tree_2.swap();

        System.out.println("tree_2 in swapped order");

        tree_2.inordertravarsel();

        System.out.println("single parent in tree_2 : "+tree_2.single_Parent());

     }

}