Question

I need to do a tree sort method but the treesortMethod is not working

/****Binarytree class****\

package Tree;

public class BinaryTree

{

private TreeNode root; // head of the list

  

//constructor - create an empty binary tree

public BinaryTree()

{

root = null;

  

}

  

//isEmpty() - return true if tree is empty, false otherwise

public boolean isEmpty()

{

return (root == null);

}

  

//deleteTree() - remove all items from tree

public void deleteList()

{

root = null;

}

  

//binSearch() - wrapper method to call the recursive bin search helper method

public TreeNode binSearch(Object key)

{

if (isEmpty())

return null;

  

return binSearchHelper(key, root);

}

  

//binSearchHelper() - recursive method to conduct binary search

public TreeNode binSearchHelper(Object key, TreeNode p)

{

if (p == null)

return null;

  

Object data = p.item;

//this is the key, so return the node p

if (key.equals(data))

return p;

  

//else, key < data, so search left subtree

if (((Comparable)key).compareTo((Comparable)data) < 0)

return binSearchHelper(key, p.left);

  

//else, key > data, so search right subtree

return binSearchHelper(key, p.right);

}

  

//insert() - inserts a new node containing given data according to bin search rules

public void insert(Object data)

{

TreeNode newNode = new TreeNode(data);

  

TreeNode curr = root; // lead node

TreeNode trail = null; // train node, should be the leaf node when we reach the end

  

//traverse the binary search, keep track of the trail node

while (curr != null)

{

trail = curr; // catch up trail

  

if (((Comparable)data).compareTo((Comparable)curr.item) < 0)

curr = curr.left; // if smaller, go left

else

curr = curr.right;

}

  

//figure out where the new node goes in relation to the leaf

if (trail == null)

root = newNode;

else if (((Comparable)data).compareTo((Comparable)trail.item) < 0)

trail.left = newNode;

else

trail.right = newNode;

}

  

//remove() - remove node containing data (if found)

public void remove(Object data)

{

TreeNode p = root;

TreeNode trailP = null;

  

//if tree is empty just announce and exit

if (isEmpty())

{

System.out.println("Data not found -- tree is empty");

return;

}

  

//run binary search protocol to locate data

while (p != null && !p.item.equals(data))

{

trailP = p;

if (((Comparable)data).compareTo((Comparable)p.item) < 0)

p = p.left; // if smaller, go left

else

p = p.right;

}

  

//if p is null, we know data is not in tree

if (p == null)

{

System.out.println("Data not found");

return;

}

  

// data ws found and is in p; trailP is p's parent

//case 1: p is a leaf node

if (p.left == null && p.right == null)

{

//p is the root - list is now empty

if (p == root)

root = null;

  

//p was trailP's left child

else if (trailP.left == p)

trailP.left = null;

  

//else p was trailP's right child

else

trailP.right = null;

}

//case 2A: p has 1 (left) child

else if (p.right == null)

{

//p is the root -- then p's left child is the new root

if (p == root)

root = p.left;

  

//p was trailP's left child

else if (trailP.left == p)

trailP.left = p.left;

  

//else p was trailP's right child

else

trailP.right = p.left;

}

//case 2B: p has 1 (right) child

else if (p.left == null)

{

//p is the root -- then p's right child is the new root

if (p == root)

root = p.right;

  

//p was trailP's left child

else if (trailP.left == p)

trailP.left = p.right;

//else p was trailP's right child

else

trailP.right = p.right;

}

//case 3: p has 2 children

else

{

//find next largest data -- leftmost tree in p's right subtree

TreeNode q = p.right;

TreeNode trailQ = p;

  

//keep going left as long as q has a left child

while (q.left != null)

{

trailQ = q;

q = q.left;

}

  

//at this point q is the node containing the next largest value after data

//swap q and p's data

p.item = q.item;

q.item = data;

  

//now remove q according to above rules

if(q.left == null && q.right == null)

trailQ.left = null;

else if (q.right == null)

trailQ.left = q.left;

else

trailQ.left = q.right;

  

  

  

}

}

  

//travInOrder() - recursively traverse binary tree INORDER

public void travInOrder()

{

if (isEmpty())

System.out.println("Tree is empty");

else

travInOrderHelper(root);

  

System.out.println();

}

  

public void travInOrderHelper(TreeNode p)

{

if (p != null)

{

travInOrderHelper(p.left);

System.out.print(p.item + "\t");

travInOrderHelper(p.right);

}

}

//treeSort() - Uses a binary search tree to sort the data items in the given array

// Returns the sorted array

public static Object[] treeSort(Object[] data) THIS METHOD IS NOT WORKING

{

// We create a new BinaryTree object, which each element

BinaryTree sortedData = new BinaryTree();

    // For each Object in the array...

for(Object o: data)

// We insert a new TreeNode into sortedData that contains

// the same value as the respective element of Object[] data.

sortedData.insert(o);

// After exiting our helper, for when q is not empty...

for (int i = 0; !q.isEmpty(); i++)

{

// Transfer each value of q back into the original Object[] data.

data[i] = q.remove();

}

// And return data.

return data;   

}

//HELPER METHOD TO DO THE IN ORDER TRAVERSAL

private static void inOrder(TreeNode node)

{  

}

}

the treeSort method is not working and as well as the helper method it has to be IN ORDER traversal meaning that sorts the left subtree then the root node then the right subtree.

This is in java, and no int data node types because it has object data types.

Answer 1

I have a new program of Tree Sort with me in java,I would like to request you to see it

/* Tree Sort is an algorithm which is based on "Binary Search Tree(BST)" data structure */ class TreeSort {    /* class "node" is used to keep right,left nodes */ class node { int key; node right,left;    public node(int item) { key = item; /* Initialize left and right node as null */ left = right = null; } }    /* root node of binary search tree */ node root;       TreeSort() { /* Initializing root node to null */ root = null; }    /* This method is for calling insertRec() function */ void insert(int key) { root = insertRec(root, key); }    /* this recursive function is used to insert a new key in binary search tree */ node insertRec(node root, int key) {    /* If the tree is empty, return a new node */ if (root == null) { root = new node(key); return root; }    /* Else, recur down the tree */ if (key < root.key) root.left = insertRec(root.left, key); else if (key > root.key) root.right = insertRec(root.right, key);    /* returning the root */ return root; }    /* The function to do inorder traversal of binary search tree */ void inorderRec(node root) { if (root != null) { inorderRec(root.left); System.out.print(root.key + " "); inorderRec(root.right); } } void treeins(int arr[]) { for(int i = 0; i < arr.length; i++) { insert(arr[i]); }    } public static void main(String[] args) { // Creating new object TreeSort tree = new TreeSort(); // Give values to the array int arr[] = {9, 11, 5, 3, 12}; tree.treeins(arr); System.out.println("The result is: "); tree.inorderRec(tree.root); } }

Output:

The result is: 3 5 9 11 12