algorithm - 大树列表递归程序

Question

我遇到了一个有趣的问题，称为大树列表问题。问题如下:

在有序二叉树中，每个节点包含一个数据元素和指向子树的“small”和“large”指针.“小”子树中的所有节点都小于或等于父节点中的数据。 “大”子树中的所有节点都大于父节点。一个循环双向链表由previous和next指针组成。

问题是取一个有序的二叉树并重新排列内部指针以从中生成一个循环双向链表。 “small”指针应该扮演“previous”的角色，“large”指针应该扮演“next”的角色”。该列表应按节点递增顺序排列。我必须编写一个递归函数并将头指针返回到新列表。

操作应该在 O(n) 时间内完成。

我知道递归会沿着树向下，但是如何递归地将小子树和大子树变成列表，我还必须将这些列表与父节点一起附加。

我应该如何解决这个问题？..我只需要一个解决问题的方向!

Answer 1

想法是创建一种方法，将包含子树(子节点)的树节点转换为循环。给定一个已转换子节点的节点(例如，在递归调用返回后)，您通过将最大节点的大指针(下一个)指向最小节点，将最小节点的小指针指向最大节点来创建一个新循环节点。

可能不完整，但接近于此:

tree_node {
    small
    large
}

convert(node){
    //base case 1, if leaf node
    if node.small == null && node.large == null
        return (self, self)

    //recursively convert children
    if node.small !=null
        smallest, larger = convert(node.small)
    else
        smallest = larger = self

    if node.large !=null
        smaller, largest = convert(node.large)
    else
        smaller = largest = self

    //wrap the ends of the chain
    largest.large = smallest
    smallest.small = largest
    //wrap the mid part
    smaller.small = larger
    larger.large = small

    //return pointers to the absolute smallest and largest of this subtree
    return (smallest, largest)
}

//actually doing it 
convert(tree.root)