使用中序二叉树实现的列表

Question

在这个新的计算机科学作业中，我们需要用一个中序二叉树来实现一个列表或数组。我只是想要一些建议，而不是直接的解决方案。

这个想法是创建一个二叉树，让我们可以通过索引来访问它的节点，比如说：

t = ListTree()
t.insert(2,0) # 1st argument is the value, 2nd the index to insert at
t.get(0) # returns 2

存储值的节点类是不能修改的，但它有一个属性 size，这个属性包含了下面所有孩子节点的总数，还有 left、right 和 value，分别指向孩子节点并存储相应的值。

我现在面临的主要问题是如何跟踪索引——因为我们不能在节点内部存储索引，所以我必须依靠遍历来跟踪它。由于我在遍历时总是从左节点开始，我还没有想出一个递归的方法来确定我们当前处于哪个索引。

任何建议都非常欢迎。

谢谢！

Answer 1

树一定要平衡吗？算法需要高效吗？

如果不需要的话，最简单的办法就是做一棵树，所有的左孩子都是空的，也就是说，这棵树其实就变成了一条链表。

插入的时候，可以递归地往右孩子走，然后在返回的过程中更新节点的大小。可以想象成这样（伪代码）：

function insert(node, value, index, depth)
    if depth < index
        create the rightchild if necessary
        insert( rightchild, value, index, depth + 1)
    if depth == size
        node.value = value
    node.size = rightchild.size + 1

当你把这个弄好之后，可以修改一下让它更平衡。当列表变长时，可以根据左右孩子哪个少，往那个方向添加节点，并在递归返回时更新大小。

如果想要让它更高效，就需要从二进制的角度来处理索引。

比如说，一个空列表有一个节点，没有孩子，值是空，大小是0。

假设你想在索引1034的位置插入“hello”。那么你希望得到的树的根节点有两个孩子，大小分别是1024和10。左孩子没有实际的孩子，但右孩子有一个右孩子，大小是2。（左边的大小8是隐含的。）那个节点又有一个右孩子，大小是0，值是“hello”。（这个列表是从1开始计数的，但从0开始的索引也是类似的。）

所以你需要递归地把索引拆分成二进制的部分，并根据需要添加节点。在查找列表的时候，经过一个没有孩子的节点时要小心。

Answer 2

我觉得你不需要存储索引，而是应该存储每个子树的大小。比如说，如果你想查找列表中的第10个元素，而左边和右边的子树各有7个元素，那么你就知道根节点是第8个元素（因为这是中序遍历的二叉树），右边子树的第一个元素就是第9个。掌握了这些信息后，你就可以进入右边的子树，去寻找第2个元素。

希望这对你有帮助。

Answer 3

你其实不想把它存储在节点本身上，因为那样的话，每次插入新节点时，所有比新节点索引小的节点的索引都得更新。其实真正的问题是怎么进行中序遍历。你可以试着让你的递归函数返回它左边节点的数量。