0

我有一段地狱般的时间试图弄清楚这一点。在我所见的任何地方，我似乎都只是在解释如何以非递归方式实际遍历列表（我真正理解的部分）。那里的任何人都可以敲定我最初如何准确地浏览列表并找到实际的前任/后继节点，以便我可以在节点类中标记它们吗？我需要能够创建一个简单的二叉搜索树并浏览列表并将空链接重新路由到前任/继任者。我有一些类似于以下的解决方案的运气：

thread(node n, node p) {
     if (n.left !=null)
        thread (n.left, n);
     if (n.right !=null) {
        thread (n.right, p);
     }
     n.right = p;
}
4

1 回答 1

1

根据您的描述，我假设您有一个结构类似于以下内容的节点：

Node {
  left
  right
}

...并且你有一个使用左右设置的二叉树，并且你想重新分配左右值，以便它从深度优先遍历创建一个双链表树。

到目前为止，您所拥有的根（没有双关语）问题是遍历期间传递的“节点 p”（previous 的缩写？）需要独立于您当前在树中的位置 - 它总是需要包含之前访问过的节点。为此，每次运行线程时，它都需要引用相同的“先前”变量。我用一个 C-ism 编写了一些 Python 式的伪代码——如果你不熟悉，' & ' 表示“引用”（或 C# 中的“ref”），而 '*' 表示“取消引用并给我它指向的对象”。

Node lastVisited
thread(root, &lastVisisted)

function thread(node, lastVisitedRef)
  if (node.left)
    thread(node.left, lastVisitedRef)
  if (node.right)
    thread(node.right, lastVisitedRef)

  // visit this node, reassigning left and right
  if (*lastVisitedRef)
    node.right = *lastVisitedRef
    (*lastVisitedRef).left = node
  // update reference lastVisited
  lastVisitedRef = &node

如果你打算在 C 中实现这个，你实际上需要一个双指针来保存引用，但想法是一样的——你需要在整个遍历过程中保持“最后访问的节点”的位置。

于 2009-07-31T04:36:04.950 回答