我在计算机科学课上有一项家庭作业，涉及组合不同的数据结构以明显提高效率
TL;DR --- 向下滚动
“”“”构建一个行为类似于链表的数据结构，并以二叉树作为索引结构。它应该能够用作链表并继承以构造索引队列和索引堆栈。您可以假设将放入此数据结构中的所有内容都是可比较的，因此索引树将充当二叉搜索树。您应该构建一类迭代器来促进与此数据结构的交互。可以在列表迭代器指定的位置“之后”插入列表(有时可以通过 find 方法返回)。当然，在继承的索引队列中，插入只会在队列的后面，但是通过树的索引需要保留二叉搜索树的顺序，对于继承的索引堆栈也是如此。您应该有插入和删除的方法，以及查找(返回迭代器)和排序的方法(任何排序技术都足以解决这个问题，尽管您可能很想利用从树派生的固有排序信息!!) 。使用与人一起玩的主要方法来测试这个结构(也许通过高度进行比较？)。""""
TL;DR --- 让二叉搜索树节点包含与双向链表节点相同的对象有什么好处？
此外，继承如何处理这样的列表？
最佳答案
What are the benefits of having Binary Search Tree nodes containing the same Objects as doubly linked list nodes?
提出同一问题的更好方法可能是“将二叉搜索树 (BST) 的节点与附加链接连接起来以从相同节点构建链表有什么好处？”
添加额外链接的好处是能够使用 O(1) 内存迭代整个树。如果没有这个附加链接，您将需要 O(Log(N)) 内存来迭代树，因为您需要保留每个级别的位置。
为此的“代价”是为链接使用额外的O(N)内存块，以及用于维护数据结构的稍微复杂的算法。当您多次迭代同一棵树时，这可能是一个公平的交易，而插入和修改通常很少见。
How would inheritance work with such a list?
您可以为列表和树实现接口(interface)，而不是从列表和树继承。
关于algorithm - 混合数据结构对效率的好处，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24892270/