Great Tree列表递归程序

Question

我遇到了一个被称为Great Tree-List问题的有趣问题.问题如下:

在有序二进制树中,每个节点包含一个数据元素和指向子树的" 小 "和" 大 "指针."小"子树中的所有节点都小于或等于父节点中的数据."大"子树中的所有节点都大于父节点.而一个循环双向链表包括以前和未来的指针.

问题是采用一个有序的二叉树并重新排列内部指针,从而形成一个循环的双向链表." 小 "指针应扮演" 前一个 " 的角色," 大 "指针应扮演" 下一个 " 的角色.应该安排列表,以便节点按递增顺序排列.我必须写一个递归函数并将头指针返回到新列表.

操作应在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)