我使用二叉搜索树创建了一个单词计数器。当一个单词被多次添加时，该单词的计数会增加。我的问题在于我想要有两个toString（）函数：一个按字母顺序打印单词及其计数（我已经想到了），还有一个用降序计数打印单词及其计数如果单词的计数相同，则按升序字母顺序排序。
我正在努力使用第二个toString（）函数。我设置了一种方法来比较节点的计数值与左右节点的计数值，并返回最大节点的计数。但是，我收到了一些错误，我不确定我是否在这里正确的方向。
这是我的代码，其中包括我的Node容器类，Add函数和我的工作基本toString（）函数。
public class WordCounter extends BinarySearchTree<String, Integer>
{
public String word;
public int size;
// node container class
public class Node<String>
{
public String data;
public int count = 1;
public Node<String> left, right;
public Node(String data)
{
this.data = data;
left = null;
right = null;
}
}
private Node<String> root;
public WordCounter()
{
root = null;
size = 0;
}
// add function
public void Add(String word)
{
root = recAdd(root, new Node<String>(word));
}
private Node<String> recAdd(Node<String> node, Node<String> newNode)
{
// base case - found open slot
if (node == null)
{
return newNode;
}
// general case - add to right
final int comparison = newNode.data.compareTo(node.data);
if (comparison > 0)
{
node.right = recAdd(node.right, newNode);
}
// general case - add to left
else if (comparison < 0)
{
node.left = recAdd(node.left, newNode);
}
// if word values are the same, increment word count
else
{
node.count++;
}
return node;
}
// toString() function
public String toString()
{
return recInOrderToString(root);
}
private String recInOrderToString(Node<String> node)
{
if (node == null)
{
return "";
}
return recInOrderToString(node.left) + "\n word: " + node.data.toString() + "\t count: " + node.count + recInOrderToString(node.right);
}
这是我正在努力的功能。
public String toStringByCount()
{
return recToStringByCount(root);
}
private String recToStringByCount(Node<String, Integer> node)
{
// to be thorough in comparisons, I went through every possible case
// counts are compared first; if any are the same, their data must be compared
// larger counts are printed first, then ascending alphabetical order for those with the same counts
// node is null, return empty string
if (node == null)
return "";
// both nodes are null, return current node
if (node.left == null && node.right == null)
{
return "\n word: " + node.data.toString() + "\t count: " + node.count;
}
// right node is null, left is not null
if (node.right == null && node.left != null)
{
if (node.count > node.left.count)
{
return "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.left);
} else if (node.count < node.left.count)
{
return recToStringByCount(node.left) + "\n word: " + node.data.toString() + "\t count: " + node.count;
} else if (node.count == node.left.count)
{
if (node.data.compareTo(node.left.data) < 0)
{
return recToStringByCount(node.left) + "\n word: " + node.data.toString() + "\t count: " + node.count;
} else if (node.data.compareTo(node.left.data) > 0) {
return "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.left);
}
}
}
//left node is null, right is not null
if (node.left == null && node.right != null)
{
if (node.count > node.right.count)
{
return "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.right);
} else if (node.count < node.right.count)
{
return recToStringByCount(node.right) + "\n word: " + node.data.toString() + "\t count: " + node.count;
} else if (node.count == node.right.count)
{
if (node.data.compareTo(node.right.data) < 0)
{
return recToStringByCount(node.right) + "\n word: " + node.data.toString() + "\t count: " + node.count;
} else if (node.data.compareTo(node.right.data) > 0) {
return "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.right);
}
}
}
// both nodes are valid
if ((node.left != null) && (node.right != null))
{
// counts are the same
if ((node.count == node.left.count) && (node.count == node.right.count))
{
// must compare data
// data is greater than left and right
if ((node.data.compareTo(node.left.data) > 0) && (node.data.compareTo(node.right.data) > 0))
{
if (node.left.data.compareTo(node.right.data) > 0)
{
return "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.left) + recToStringByCount(node.right);
} else if (node.left.data.compareTo(node.right.data) < 0) {
return "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.right) + recToStringByCount(node.left);
}
}
// data is less than left and right
else if ((node.data.compareTo(node.left.data) < 0) && (node.data.compareTo(node.right.data) < 0))
{
if (node.left.data.compareTo(node.right.data) > 0)
{
return recToStringByCount(node.left) + recToStringByCount(node.right) + "\n word: " + node.data.toString() + "\t count: " + node.count;
} else if (node.left.data.compareTo(node.right.data) < 0) {
return recToStringByCount(node.right) + recToStringByCount(node.left) + "\n word: " + node.data.toString() + "\t count: " + node.count;
}
}
// data is less than left, greater than right
else if ((node.data.compareTo(node.left.data) < 0) && (node.data.compareTo(node.right.data) > 0))
{
return recToStringByCount(node.left) + "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.right);
}
// data is greater than left, less than right
else if ((node.data.compareTo(node.left.data) > 0) && (node.data.compareTo(node.right.data) < 0))
{
return recToStringByCount(node.right) + "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.left);
}
}
// left is same, smaller than right
else if ((node.count == node.left.count) && (node.count < node.right.count))
{
// must compare data
// data greater than left
if (node.data.compareTo(node.left.data) > 0)
{
return recToStringByCount(node.right) + "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.left);
}
// data smaller than left
else if (node.data.compareTo(node.left.data) < 0)
{
return recToStringByCount(node.right) + recToStringByCount(node.left) + "\n word: " + node.data.toString() + "\t count: " + node.count;
}
}
// left is same, greater than right
else if ((node.count == node.left.count) && (node.count > node.right.count))
{
// must compare data
// data greater than left
if (node.data.compareTo(node.left.data) > 0)
{
return "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.left) + recToStringByCount(node.right);
}
// data smaller than left
else if (node.data.compareTo(node.left.data) < 0)
{
return recToStringByCount(node.left) + "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.right);
}
}
// right is same, smaller than left
else if ((node.count == node.right.count) && (node.count < node.left.count))
{
// must check data
// data greater than right
if (node.data.compareTo(node.right.data) > 0)
{
return recToStringByCount(node.left) + "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.right);
}
// data smaller than right
else if (node.data.compareTo(node.right.data) < 0)
{
return recToStringByCount(node.left) + recToStringByCount(node.right) + "\n word: " + node.data.toString() + "\t count: " + node.count;
}
}
// right is same, greater than left
else if ((node.count == node.right.count) && (node.count > node.right.count))
{
// must compare data
// data greater than right
if (node.data.compareTo(node.right.data) > 0)
{
return "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.right) + recToStringByCount(node.left);
}
// data smaller than right
else if (node.data.compareTo(node.right.data) < 0)
{
return recToStringByCount(node.right) + "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.left);
}
}
// greater than right & left
else if ((node.count > node.left.count) && (node.count > node.right.count))
{
// must compare right & left count
// right greater than left
if (node.right.count > node.left.count)
{
return "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.right) + recToStringByCount(node.left);
}
// right smaller than left
else if (node.right.count < node.left.count)
{
return "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.left) + recToStringByCount(node.right);
}
// right equal to left
else if (node.right.count == node.left.count)
{
// must compare data
if (node.right.data.compareTo(node.left.data) > 0)
{
return "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.right) + recToStringByCount(node.left);
} else if (node.right.data.compareTo(node.left.data) < 0) {
return "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.left) + recToStringByCount(node.right);
}
}
}
// less than right & left
else if ((node.count < node.left.count) && (node.count < node.right.count))
{
// must compare right & left counts
// right greater than left
if (node.right.count > node.left.count)
{
return recToStringByCount(node.right) + recToStringByCount(node.left) + "\n word: " + node.data.toString() + "\t count: " + node.count;
}
// right less than left
if (node.right.count < node.left.count)
{
return recToStringByCount(node.left) + recToStringByCount(node.right) + "\n word: " + node.data.toString() + "\t count: " + node.count;
}
// right equal to left
if (node.right.count == node.left.count)
{
// must compare data
if (node.right.data.compareTo(node.left.data) > 0)
{
return recToStringByCount(node.right) + recToStringByCount(node.left) + "\n word: " + node.data.toString() + "\t count: " + node.count;
} else if (node.right.data.compareTo(node.left.data) < 0) {
return recToStringByCount(node.left) + recToStringByCount(node.right) + "\n word: " + node.data.toString() + "\t count: " + node.count;
}
}
}
// greater than left, less than right
else if ((node.count > node.left.count) && (node.count < node.right.count))
{
return recToStringByCount(node.right) + "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.left);
}
// smaller than left, greater than right
else if ((node.count < node.left.count) && (node.count > node.right.count))
{
return recToStringByCount(node.left) + "\n word: " + node.data.toString() + "\t count: " + node.count + recToStringByCount(node.right);
}
}
return "";
}
就像我说的，不确定我是否正确接近这一点。我在compareCountLeft和compareCountRight上也遇到“int not beedferenced”的错误，并且在我的return语句中“int不能转换为String”。
一些问题：
1.在使用node.left函数之前，你需要测试node.right和compareTo不为null
2.您将返回整数而不是字符串。你错过了数据本身的返回：
private String recToStringByCount(Node<String> node) {
if (node == null)
return "";
if (node.left == null && node.right == null)
return "\n word: " + node.data.toString() + "\t count: " + node.count;
if语句中而不是返回count，你应该做类似你的第一个toString：return recToStringByCount(node.left) + recToStringByCount(node) + recToStringByCount(node.right);