New Topic/Question
Reply
I am having a trouble understanding why I am not able to insert the the trees I have made into a priority queue. The PriorityQ, Node and Tree classes are from Lafore's Data Structures text. I am trying to build a Huffman algorithm and am hung up on this step. I believe it is because the are incompatible types, inorder to insert a Tree object into the PriorityQ, the PriorityQ should be declared with "private Tree[] queArray;" instead of "private int[] queArray;" Is this assumption correct?
Error Message is as follows:
----jGRASP exec: javac -g Assignment5.java
HuffmanTesting.java:377: insert(int) in PriorityQ cannot be applied to (Tree)
thePQ.insert(theTree);
^
Note: HuffmanTesting.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error
----jGRASP wedge: exit code for process is 1.
----jGRASP: operation complete.
import java.util.*;
import java.io.*;
import java.util.*; // for Stack class
////////////////////////////////////////////////////////////////
class PriorityQ
{
// array in sorted order, from max at 0 to min at size-1
private int maxSize;
private int[] queArray;
private int nItems;
//-------------------------------------------------------------
public PriorityQ(int s) // constructor
{
maxSize = s;
queArray = new int[maxSize];
nItems = 0;
}
//-------------------------------------------------------------
public void insert(int item) // insert item
{
int j;
if(nItems==0) // if no items,
queArray[nItems++] = item; // insert at 0
else // if items,
{
for(j=nItems-1; j>=0; j--) // start at end,
{
if( item > queArray[j] ) // if new item larger,
queArray[j+1] = queArray[j]; // shift upward
else // if smaller,
break; // done shifting
} // end for
queArray[j+1] = item; // insert it
nItems++;
} // end else (nItems > 0)
} // end insert()
//-------------------------------------------------------------
public int remove() // remove minimum item
{
return queArray[--nItems]; }
//-------------------------------------------------------------
public int peekMin() // peek at minimum item
{
return queArray[nItems-1]; }
//-------------------------------------------------------------
public boolean isEmpty() // true if queue is empty
{
return (nItems==0); }
//-------------------------------------------------------------
public boolean isFull() // true if queue is full
{
return (nItems == maxSize); }
//-------------------------------------------------------------
} // end class PriorityQ
/**************************************************************/
/**************************************************************/
class Node
{
public int iData; // data item (key)
public double dData; // data item
public Node leftChild; // this node's left child
public Node rightChild; // this node's right child
public void displayNode() // display ourself
{
System.out.print('{');
System.out.print(iData);
System.out.print(", ");
System.out.print(dData);
System.out.print("} ");
}
} // end class Node
/**************************************************************/
class Tree
{
private Node root; // first node of tree
// -------------------------------------------------------------
public Tree() // constructor
{ root = null; } // no nodes in tree yet
// -------------------------------------------------------------
public Node find(int key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
while(current.iData != key) // while no match,
{
if(key < current.iData) // go left?
current = current.leftChild;
else // or go right?
current = current.rightChild;
if(current == null) // if no child,
return null; // didn't find it
}
return current; // found it
} // end find()
// -------------------------------------------------------------
public void insert(int id, double dd)
{
Node newNode = new Node(); // make new node
newNode.iData = id; // insert data
newNode.dData = dd;
if(root==null) // no node in root
root = newNode;
else // root occupied
{
Node current = root; // start at root
Node parent;
while(true) // (exits internally)
{
parent = current;
if(id < current.iData) // go left?
{
current = current.leftChild;
if(current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
current = current.rightChild;
if(current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------
public boolean delete(int key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.iData != key) // search for node
{
parent = current;
if(key < current.iData) // go left?
{
isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
// if no children, simply delete it
if(current.leftChild==null &&
current.rightChild==null)
{
if(current == root) // if root,
root = null; // tree is empty
else if(isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}
// if no right child, replace with left subtree
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // two children, so replace with inorder successor
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child's left descendents
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
// -------------------------------------------------------------
public void traverse(int traverseType)
{
switch(traverseType)
{
case 1: System.out.print("\nPreorder traversal: ");
preOrder(root);
break;
case 2: System.out.print("\nInorder traversal: ");
inOrder(root);
break;
case 3: System.out.print("\nPostorder traversal: ");
postOrder(root);
break;
}
System.out.println();
}
// -------------------------------------------------------------
private void preOrder(Node localRoot)
{
if(localRoot != null)
{
System.out.print(localRoot.iData + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void inOrder(Node localRoot)
{
if(localRoot != null)
{
inOrder(localRoot.leftChild);
System.out.print(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void postOrder(Node localRoot)
{
if(localRoot != null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.iData + " ");
}
}
// -------------------------------------------------------------
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
"......................................................");
while(isRowEmpty==false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j=0; j<nBlanks; j++)
System.out.print(' ');
while(globalStack.isEmpty()==false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
System.out.print(temp.iData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild != null ||
temp.rightChild != null)
isRowEmpty = false;
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for(int j=0; j<nBlanks*2-2; j++)
System.out.print(' ');
} // end while globalStack not empty
System.out.println();
nBlanks /= 2;
while(localStack.isEmpty()==false)
globalStack.push( localStack.pop() );
} // end while isRowEmpty is false
System.out.println(
"......................................................");
} // end displayTree()
// -------------------------------------------------------------
} // end class Tree
////////////////////////////////////////////////////////////////
/**************************************************************/
/**************************************************************/
/**************************************************************/
/**************************************************************/
////////////////////////////////////////////////////////////////
public class HuffmanTesting {
/** Main method */
public static void main(String[] args) throws Exception {
// Create a File instance
java.io.File file = new java.io.File("Huffmantext.txt");
// Create a Scanner for the file
java.util.Scanner input = new java.util.Scanner(file);
String s = input.next();
// Invoke the countLetters method to count each letter
int[] counts = countLetters(s);
Tree theTreeA = new Tree();
theTreeA.insert(counts[0], 65);
theTreeA.displayTree();
Tree theTreeB = new Tree();
theTreeB.insert(counts[1], 66);
theTreeB.displayTree();
Tree theTreeC = new Tree();
theTreeC.insert(counts[2], 67);
theTreeC.displayTree();
Tree theTreeD = new Tree();
theTreeD.insert(counts[3], 68);
theTreeD.displayTree();
Tree theTreeE = new Tree();
theTreeE.insert(counts[4], 69);
theTreeE.displayTree();
Tree theTreeF = new Tree();
theTreeF.insert(counts[5], 70);
theTreeF.displayTree();
Tree theTreeG = new Tree();
theTreeG.insert(counts[6], 71);
theTreeG.displayTree();
Tree theTree = new Tree();
PriorityQ thePQ = new PriorityQ(7);
thePQ.insert(theTree);
} //End main
// Count each letter in the string
public static int[] countLetters(String s) {
int[] counts = new int[7];
for (int i = 0; i < s.length(); i++) {
if (Character.isLetter(s.charAt(i)))
counts[s.charAt(i) - 'A']++;
}
return counts;
}
}
MultiQuote
| 