Правильный поток в двоичном дереве

Question

У меня адское время, когда я пытаюсь понять это. Куда бы я ни посмотрел, мне кажется, что я сталкиваюсь только с объяснениями того, как на самом деле обходить список нерекурсивно (часть, которую я на самом деле понимаю). Кто-нибудь может подсказать, как именно я могу сначала пройти по списку и найти фактические узлы-предшественники / преемники, чтобы я мог пометить их в классе узлов? Мне нужно иметь возможность создать простое дерево двоичного поиска, просмотреть список и перенаправить нулевые ссылки на предшественника / преемника. Мне повезло с решением, похожим на следующее:

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

Answer 1

Из вашего описания я предполагаю, что у вас есть узел со структурой, похожей на:

Node {
  left
  right
}

... и что у вас есть двоичное дерево этих параметров, настроенное с использованием левого и правого каналов, и что вы хотите переназначить значения влево и вправо так, чтобы он сначала создавал двойной-связанный список из глубины обход дерева.

Основная (без каламбура) проблема с тем, что у вас так далеко, состоит в том, что «узел p» (сокращение от предыдущего?), Который передается во время обхода, должен быть независимым от того, где в дереве вы находитесь - он всегда должен содержать ранее посещенный узел. Для этого каждый раз, когда поток запускается, он должен ссылаться на одну и ту же «предыдущую» переменную. Я сделал некоторый псевдокод Python-ish с одним C-ism - если вы не знакомы, « & » означает «ссылка на» (или «ref» в C #) и «*» означает «разыменование и дай мне объект, на который он указывает».

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, на самом деле вам понадобился бы двойной указатель для хранения ссылки, но идея та же - вам нужно сохранить местоположение «последнего посещенного узла» в течение всего обхода .