大树列表递归程序
我遇到了一个有趣的问题叫做“伟大的树列表问题”。问题如下：
在有序二叉树中，每个节点包含一个数据元素，以及指向子树的“小”和“大”指针.All“小”子树中的节点小于或等于父节点中的数据。“大”子树中的所有节点都大于父节点。循环双链接列表由前一个和下一个指针组成。
问题是取一棵有序的二叉树，并重新排列内部指针，从而形成一个循环的双链接列表。“小”指针应该扮演“先前”的角色，“大”指针应该扮演“下一步”的角色。应该对列表进行排列，使节点按递增顺序排列。我必须编写一个递归函数&返回指向新列表的head指针。
手术应在O(n)时间内完成。
我知道递归会在树下进行，但是如何递归地将小的和大的子树转换成列表，我还必须将这些列表与父节点一起附加。
我该怎么处理这个问题？我只需要一个方向来解决这个问题！
回答 3
Stack Overflow用户
发布于 2013-07-03 19:16:34
其思想是创建一个方法，将包含子树(子节点)的树节点转换为循环。如果一个节点已经转换了子节点(例如，递归调用返回后)，则通过将最大节点的大指针(下一步)指向最小节点，将最小节点的小指针指向最大节点，从而创建一个新的循环。
可能不完整，但它将接近于这一点：
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)Stack Overflow用户
发布于 2013-07-03 19:59:51
递归编程的关键是想象您已经有了解决方案。
因此，您已经有了一个函数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;完成边缘箱(空子枝等)。:)
Stack Overflow用户
发布于 2013-07-03 18:57:28
假设您有一个由3个节点组成的简单树
B <--- A ---> C沿着左边和右边走，获取每个节点的指针，然后有
B -> C
B <- C由于您的树是二进制的，它将由三个节点“子树”组成，这些节点“子树”可以递归地使用此策略。
https://stackoverflow.com/questions/17455871
复制相似问题
腾讯云开发者
