Что такое обход Морриса?

Обход Морриса (InOrder) — это алгоритм обхода дерева, который не использует рекурсию или стек. В этом обходе ссылки создаются как преемники, и узлы печатаются с использованием этих ссылок. Наконец, изменения отменяются, чтобы восстановить исходное дерево.

Содержание

Алгоритм
Демо
Код

Алгоритм

Инициализировать root как текущий узел curr .
Пока curr не NULL проверьте, есть ли у curr левый дочерний элемент.
Если curr не имеет левый дочерний элемент, выведите curr и обновите его, чтобы он указывал на узел справа от curr.
Иначе, сделайте curr правым потомком самого правого узла в левом поддереве curr .
Обновите curr до этого левого узла.

Демо

Давайте возьмем двоичное дерево, приведенное ниже, и пройдемся по нему. обход Морриса (InOrder).

4 4 4 — это корень, поэтому он инициализируется как curr . 44 4 имеет левый дочерний элемент, поэтому он становится самым правым дочерним элементом своего левого поддерева (непосредственный предшественник 4 4 4 в обходе InOrder). Наконец, 44 4 становится правым потомком 33 3 и curr имеет значение 2 2 2.

{ 2 2 2} выше относится на 22 2 и все его дети. Теперь, когда в дереве есть обратная ссылка на 4 4 семантика> 4, обход продолжается.

1 1 1 печатается, поскольку у него нет левого дочернего элемента и curr возвращается в 2 2 2, который был преобразован в 1 1 Правый дочерний элемент 1 в предыдущей итерации. На следующей итерации 22 2 имеет обоих потомков. Однако двойное условие цикла заставляет его останавливаться, когда он достигает самого себя; это признак того, что его левое поддерево уже было пройдено. Итак, он печатает себя и продолжает свое правое поддерево ( 3 3 3). 33 3 печатает себя , а curr становится 3 3 3 и проходит тот же процесс проверки, что и 2 2 2 сделал. Он также понимает, что его левое поддерево было пройдено, и продолжает 4 4 аннотация> 4. Остальная часть дерева следует тому же шаблону.

Код

Вышеупомянутый алгоритм реализован в приведенном ниже коде:

C ++

C ++

Python

Python

Java

Java

 #include  с использованием пространства имен std;  struct Node {int data;  struct Node * left_node;  struct Node * right_node;  };  void Morris (struct Node * root) {struct Node * curr, * prev;  если (корень == NULL) возврат;  curr = корень;  while (curr! = NULL) {если (curr-> left_node == NULL) {cout  data  right_node;  } else {/* Найти предыдущий (предыдущий) curr */prev = curr-> left_node;  while (prev-> right_node! = NULL && prev-> right_node! = curr) prev = prev-> right_node; /* Сделать curr правым потомком своего предыдущего */if (prev-> right_node == NULL) {prev-> right_node = curr;  curr = curr-> left_node;  }/* исправляем правый дочерний элемент предыдущего */else {prev-> right_node = NULL;  cout  data  right_node;  }}}} struct Node * add_node (int data) {struct Node * node = новый узел;  узел-> данные = данные;  узел-> left_node = NULL;  узел-> right_node = NULL;  возврат (узел);  } int main () {узел структуры * root = add_node (4);  корень-> left_node = add_node (2);  корень-> right_node = add_node (5);  корень-> left_node-> left_node = add_node (1);  корень-> left_node-> right_node = add_node (3);  Моррис (корень);  возврат 0;  }