java - 我需要一个数据结构来保存两种数据类型

Question

我正在制作一棵二叉树，当我向树中添加一个新的字符串节点时，我必须首先搜索该节点是否已经存在。如果是这样，我需要将其值增加一，而不是将其添加到不同的节点。

哪种数据结构最适合这样做？

Answer 1

巴尼的回答很好。但要更具体地回答您的问题，您可能希望您的节点类看起来像：

public class Node
{
    String value;
    int count;

    Node leftChild;
    Node rightChild;
}

您将为您的树创建这些实例。这些实例之一将是“根”。leftChild所有其他实例将通过和直接或间接地挂起路由rightChild。

祝你好运！

Answer 2

除非我误解了你，否则你的问题很简单。只需创建一个包含两个成员变量的类：

public class Node {
    v1 data_type_1;
    v2 data_type_2;
}

将其用作二叉树的节点。

Answer 3

呵呵，基本上可能

https://github.com/JohannesLichtenberger/sirix/tree/master/bundles/sirix-core/src/main/java/org/sirix/index/avltree

有帮助。它是 AVLTree 的实现，一种平衡的二叉树。我会用泛型类型（我有）来实现它，这样你也可以存储其他内容。

在我的情况下，它被用作索引结构，它应该能够大部分存储在主内存中（但也可以使用使用版本控制算法的磁盘表示）。我正在存储一个字符串/路径组合（键）和一组属于路径（值）的简单 ID。

但是，您可能必须存储两个指向两个子节点的“指针”或对两个节点对象的内存引用。

编辑：您还可以仔细看看 Google Guava 即将推出的 BinaryTreeTraverser：https ://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/collect/BinaryTreeTraverser .java

Answer 4

因此，结构的座右铭是通过减少重复次数来最小化内存。并按排序顺序存储数据。

那么这个节点可能对你的树有一些用处。

public class node
{
   String value;
   int count;
   node left;
   node right;
}

但是即使它是 TreeMap 也有更好的解决方案，因为这里的搜索需要 O(1) （重复计数增量相当于搜索），在前一种情况下为 O(log(n))。

Map testTreeMap = new TreeMap();
if(testTreeMap.get(MyString)!=null)
{
testTreeMap.put(MyString, testTreeMap.get(MyString) +1)
}
else
{
testTreeMap.put( MyString , Integer(count) ) // count=1
}

有了这个你就完成了..!!

http://tutorialswithexamples.com/java-treemap-tutorial-and-examples/