Можем ли мы использовать обход Морриса для заказа после заказа?

Question

Я посетил многие сайты, но не смог найти алгоритм для обхода Morris postOrder. Я знаю, что мы можем использовать алгоритм Морриса для preOrder и inOrder. Это будет очень полезно, если кто-то укажет мне на алгоритм postOrder Morris, если он существует.

Answer 1

Я попытаюсь объяснить, как мы можем добиться обхода после заказа с использованием метода Морриса. Предварительное требование: Перед тем, как объяснять, послепорядок обход, позволяет пересмотреть обход в порядке.

В обходном пути, начинайте с корневого узла 1. Если текущий узел оставил дочернее устройство, найдите его предшественника в порядке и сделайте root как правый дочерний элемент и переместите его влево от корня. [чтобы найти предшественника, найдите элемент max в его левом поддереве] 2. Если текущий узел не имеет дочернего элемента, затем распечатайте данные и переместите их вправо.

Восстановить дерево: главное, что следует соблюдать, заключается в том, что при выполнении шага 1 мы достигнем точки, где дочерний правый предшественник является самим текущим узлом, это происходит только тогда, когда весь оставшийся ребенок выключен, и мы начинаем печатать данные оттуда. [когда вы не нашли левого дочернего узла текущего узла] Итак, для этого случая нам нужно вырезать правый дочерний элемент этого узла.

void MorriesInorder(BTnode root) { 
if(root == null) return; 
BTnode temp; 
while (root!=null){ 
    //case 2: when left child does not exist 
     if (root.left == null) { 
       print(root.data); 
       root = root.right; 
    }else { 
      //find predecessor 
      temp = root.left; 
      while (temp.right!=null && 
         temp.right!=root) // to check restore case 
        temp = temp.right; 

      if (temp.right == null) //predecessor found, converting 
      { 
         temp.right = root; 
         root = root.left; 
      } else { 
        print root.data; 
        temp.right = null; // cut right child off 
        root = root.right; 
      } 
    } 

}} 

Так что теперь вернемся к первоначальному вопросу, как мы проводим обход послесловия. Мы будем использовать вышеуказанную концепцию с незначительными изменениями для достижения обхода после ордера. Сначала позволяет иметь фиктивный узел и делать целым деревом в качестве левого дочернего элемента фиктивного узла и сделать правильный дочерний пустым. [ Зачем? Bec, если мы предположим, что нет правильного дочернего элемента root, тогда prinitng останется дочерним, а затем root станет обходным путем, Right;)] Теперь что дальше? Мы закончили, No ... Выполнение только на новом дереве не имеет никакого смысла, оно все равно печатает обход оригинального дерева, за которым следует фиктивный узел.

сначала удалить печать данных из корпуса 2 [обсуждается в заказовМои обходе]

Критическая часть: Теперь внимательно наблюдать внутренний блок еще, этот кусок кода, который требует внимания. Поскольку это временное расширенное дерево является объектом обхода, как в обходном порядке, за исключением того, что во внутреннем клаузе, после нахождения временного родителя, узлы между p.left (включены) и p (исключены) расширены вправо в модифицированном дерево обрабатывается в обратном порядке. Чтобы обрабатывать их в постоянное время, цепочка узлов сканируется вниз, а ссылки справа обращаются к родителям узлов. Затем та же цепочка сканируется вверх, каждый узел посещается, а правильные ссылки восстанавливаются до их первоначальной настройки.

//This is Post Order :children before node(L ,R , N) 
void morrisPostorderTraversal(Node *root){ 

// Making our tree left subtree of a dummy Node 
Node *dummyRoot = new Node(0); 
dummyRoot->left = root; 

//Think of P as the current node 
Node *p = dummyRoot, *pred, *first, *middle, *last; 
while(p!=NULL){   

    if(p->left == NULL){ 
     p = p->right; 
    } else{ 
     /* p has a left child => it also has a predeccessor 
      make p as right child predeccessor of p  
     */ 
     pred = p->left; 
     while(pred->right!=NULL && pred->right != p){ 
      pred = pred->right; 
     } 

     if(pred->right == NULL){ 

      // predeccessor found for first time 
      // modify the tree 

      pred->right = p;  
      p = p->left; 

     }else {       

      // predeccessor found second time 
      // reverse the right references in chain from pred to p 
      first = p; 
      middle = p->left;    
      while(middle!=p){    
       last = middle->right; 
       middle->right = first; 
       first = middle; 
       middle = last; 
      } 

      // visit the nodes from pred to p 
      // again reverse the right references from pred to p  
      first = p; 
      middle = pred; 
      while(middle!=p){ 

       cout<<" "<<middle->data; 
       last = middle->right;   
       middle->right = first; 
       first = middle; 
       middle = last; 
      } 

      // remove the pred to node reference to restore the tree structure 
      pred->right = NULL;  
      p = p-> right; 
     } 
    } 
}  
}