Может ли кто-нибудь помочь мне понять следующий алгоритм обхода дерева порядка Морриса без использования стеков или рекурсии? Я пытался понять, как это работает, но это просто ускользало от меня.
1. Initialize current as root
2. While current is not NULL
If current does not have left child
a. Print current’s data
b. Go to the right, i.e., current = current->right
Else
a. In current's left subtree, make current the right child of the rightmost node
b. Go to this left child, i.e., current = current->left
Я понимаю , что дерево модифицируется таким образом , что current node
, сделано right child
из max node
в right subtree
и использовать это свойство для заказовМои обходе. Но кроме этого, я потерялся.
РЕДАКТИРОВАТЬ: нашел этот сопровождающий код С ++. Мне было трудно понять, как дерево восстанавливается после модификации. Магия заключается в else
предложении, которое выполняется после изменения правого листа. Смотрите код для деталей:
/* Function to traverse binary tree without recursion and
without stack */
void MorrisTraversal(struct tNode *root)
{
struct tNode *current,*pre;
if(root == NULL)
return;
current = root;
while(current != NULL)
{
if(current->left == NULL)
{
printf(" %d ", current->data);
current = current->right;
}
else
{
/* Find the inorder predecessor of current */
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;
/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}
// MAGIC OF RESTORING the Tree happens here:
/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre->right = NULL;
printf(" %d ",current->data);
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}
c++
binary-tree
tree-traversal
brainydexter
источник
источник
pre->right = NULL;
Ответы:
Если я правильно понимаю алгоритм, это должен быть пример того, как он работает:
Во-первых,
X
это корень, поэтому он инициализируется какcurrent
.X
имеет левый дочерний элемент, поэтому онX
становится крайним правым дочерним элементомX
левого поддерева - непосредственным предшественникомX
в обходе по порядку. ТакX
делается правильный потомокB
, затемcurrent
устанавливается значениеY
. Теперь дерево выглядит так:(Y)
выше относится кY
и всем его дочерним элементам, которые опущены из-за проблем с рекурсией. Важная часть все равно указана. Теперь, когда у дерева есть обратная ссылка на X, обход продолжается ...Затем
A
выводится, потому что у него нет левого дочернего элемента, иcurrent
возвращаетсяY
, что было сделаноA
правым дочерним элементом в предыдущей итерации. На следующей итерации у Y будут оба потомка. Однако двойное условие цикла заставляет его останавливаться, когда он достигает самого себя, что указывает на то, что его левое поддерево уже было пройдено. Итак, он печатает себя и продолжает правое поддерево, которое естьB
.B
печатает себя, а затемcurrent
становитсяX
, который проходит тот же процесс проверки, что иY
сделал, также понимая, что его левое поддерево было пройдено, продолжая сZ
. Остальная часть дерева следует той же схеме.Никакой рекурсии не требуется, потому что вместо того, чтобы полагаться на возврат через стек, обратная ссылка на корень (под) дерева перемещается в точку, в которой она будет доступна в рекурсивном алгоритме обхода дерева порядка в любом случае - после его левое поддерево закончено.
источник
Рекурсивный обход в-заказ:
(in-order(left)->key->in-order(right))
. (это похоже на DFS)Когда мы выполняем DFS, нам нужно знать, куда возвращаться (вот почему мы обычно храним стек).
Когда мы проходим через родительский узел, к которому нам нужно будет вернуться, мы находим узел, от которого нам нужно будет вернуться, и обновляем его ссылку на родительский узел.
Когда мы отступим? Когда мы не можем идти дальше. Когда мы не сможем пойти дальше? Когда нет левого ребенка.
Куда мы вернемся? Примечание: ПРЕЕМНИКУ!
Итак, когда мы следуем за узлами по левому дочернему пути, на каждом шаге устанавливаем предшественника, указывающего на текущий узел. Таким образом, у предшественников будут ссылки на преемников (ссылка для возврата).
Мы идем налево, пока можем, пока нам не нужно отступить. Когда нам нужно вернуться, мы печатаем текущий узел и переходим по правильной ссылке к преемнику.
Если мы только что вернулись назад -> нам нужно следовать за правым потомком (мы закончили с левым потомком).
Как определить, что мы только что отступили? Получите предшественника текущего узла и проверьте, есть ли у него правильная ссылка (на этот узел). Если есть - то мы за ним следили. удалите ссылку, чтобы восстановить дерево.
Если не было левой ссылки => мы не возвращаемся назад и должны продолжить, следуя левым дочерним элементам.
Вот мой код Java (извините, это не C ++)
источник
Я сделал анимацию для алгоритма здесь: https://docs.google.com/presentation/d/11GWAeUN0ckP7yjHrQkIB0WT9ZUhDBSa-WR0VsPU38fg/edit?usp=sharing
Надеюсь, это поможет понять. Синий кружок - это курсор, а каждый слайд - это итерация внешнего цикла while.
Вот код для обхода Морриса (я скопировал и модифицировал его у гиков для гиков):
источник
print(cursor.value)
послеpre.right = None
строкиЯ думаю, что этот код было бы лучше понять, просто используйте null, чтобы избежать бесконечных циклов, не нужно использовать магию еще. Его можно легко изменить на предзаказ.
источник
temp.left = null
дерево будет потеряно.Я нашел очень хорошее иллюстрированное объяснение Морриса Траверсала .
источник
Я надеюсь, что приведенный ниже псевдокод более показателен:
Ссылаясь на код C ++ в вопросе, внутренний цикл while находит упорядоченного предшественника текущего узла. В стандартном двоичном дереве правый дочерний элемент предшественника должен быть нулевым, в то время как в многопоточной версии правый дочерний элемент должен указывать на текущий узел. Если правый дочерний элемент имеет значение NULL, он устанавливается на текущий узел, эффективно создавая потоки , которые используются в качестве точки возврата, которая в противном случае должна была бы храниться, обычно в стеке. Если правый дочерний элемент не равен нулю, то алгоритм гарантирует, что исходное дерево восстановлено, а затем продолжает обход в правом поддереве (в этом случае известно, что левое поддерево было посещено).
источник
Сложность времени решения Python: O (n) Сложность пространства: O (1)
Отличное объяснение обхода Морриса Inorder
источник
PFB Объяснение обхода по порядку Морриса.
источник