4

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

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

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

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

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

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

4

3 回答 3

5

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

可能不完整，但会接近这个：

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)
于 2013-07-03T19:16:34.433 回答
2

递归编程的关键是想象你已经有了解决方案。

因此，您已经有了一个函数recLink(Tree t)，它接收指向树的指针，将该树转换为双向循环列表并返回指向列表头（最左边）节点的指针：

recLink( n={Node: left, elt, right}) =  // pattern match tree to a full node
  rt := recLink( right);                // already
  lt := recLink( left);                 //   have it
  n.right := rt;       n.left := lt.left;        // middle node
  lt.left.right := n;  rt.left.right := lt;      // right edges
  lt.left := rt.left;  rt.left := n;      
  return lt;

完成边缘案例（空子分支等）。:)

于 2013-07-03T19:59:51.863 回答
1

假设您有一个包含 3 个节点的简单树 

B <--- A ---> C

沿着左右两边走，得到每个节点的指针，然后有

B -> C
B <- C

由于您的树是二叉树，它将由可以递归使用此策略的 3 个节点“子树”组成。

于 2013-07-03T18:57:28.853 回答