0

我正在尝试创建包含两个 int 值和一个按字典顺序排序的字符串值的二叉树，但我不知道该怎么做。我创建了一个已经排序的数组列表，但是二叉树必须是基于引用的，未排序，我正在考虑在创建列表时对其进行排序。有人能帮忙吗？任何简短的想法将不胜感激。

4

3 回答 3

2

二叉树是递归的东西。创建一个名为 BinaryTree 的类（我希望您使用 C++、.NET 或 JAVA），它有两个对其他两个 BinaryTrees 的引用（默认情况下为 null）。然后创建一个递归的插入函数。

我不知道您要完成什么，但是在构建二叉树时，通常找不到数组。

于 2010-06-04T13:14:35.783 回答
0

听起来您已经有一个数据结构来存储两个 int 值和一个字符串（因为您已将它们排序在数组列表中）。您可以将此数据结构包含在“树节点”中。一个节点通常有一个指向父节点（除非它是根节点）和 2 个子节点的引用指针。

由于您希望对树进行排序，因此您真正想要的是一种称为堆的特殊形式的二叉树。下面的 Binary Heap 维基百科页面的链接有一个算法来展示如何对二进制堆进行排序。

http://en.wikipedia.org/wiki/Binary_heap

这里有一些关于堆和树的更一般的信息。

http://en.wikipedia.org/wiki/Binary_tree

http://en.wikipedia.org/wiki/Heap_(data_structure)

编辑：您不必使用文字树结构以树形式存储数据。使用数组构建树是完全可以接受的。您可以计算数组的索引，而不是使用引用指针（父节点和 1 或 2 个子节点）。每组孩子都被认为是树中的一个“行”。根元素在零行上。第一排是两个孩子。根的孩子的孩子在第二行，依此类推。

使用这种模式，可以使用 array[2*n+1] 和 array[2*n+2] 找到任何节点的子节点，其中 n 是父节点的行。任何节点的父节点都可以使用 array[floor( (n-1)/2)] 找到。

于 2010-06-04T13:15:44.617 回答
0

您首先应该创建一个类来存储您的数据并实现Comparable或使用Comparator.

public class Data { // Implement Comparable...
    private String s;
    private int n1;
    private int n2;

    // Implement constructors, getters, setters based on what you need...

    // Implement compareTo (+ equals + hashCode) unless your going with Comparator
}

然后使用一个Collection实现SortedSet来存储你的数据，TreeSet 是一个不错的选择。中的对象SortedSet是通过引用存储的，因此如果您修改在局部变量中设置的值，它也会在集合中被修改。

编辑：如果我正确理解了您关于基于引用的列表的问题，那么在 Java 中可能会出现以下问题。

List<Data> dataList = // Create list and add data into it.
Data data = dataList.get(4);
data.setS(103); // Modifies S in the local data-object and in dataList because they are reference based.
于 2010-06-04T13:33:03.433 回答