Обход PreOrder и PostOrder путем модификации обхода morris

Question

Обходный путь morris отлично подходит для обхода InOrder с временем O (n) и O (1). Можно ли просто изменить несколько вещей, чтобы добиться обхода PreOrder и PostOrder с использованием того же алгоритма.

Answer 1

Я знаю решение для Preorder с использованием morison Algo.

вот ява код

public static void morisonPreOrder(TreeNode root) { 
    TreeNode curr = root, tmp=null; 

    while (curr != null) { 
     if(curr.leftNode == null) { 
      System.out.print(curr.value + " "); 
      curr = curr.rightNode; 
     } else { 
      tmp = curr.leftNode; 
      while (tmp.rightNode != null && tmp.rightNode != curr) { 
       tmp = tmp.rightNode; 
      } 

      if(tmp.rightNode == null) { 
       System.out.print(curr.value + " "); 
       tmp.rightNode = curr; 
       curr = curr.leftNode; 
      } else { 
       tmp.rightNode = null; 
       curr = curr.rightNode; 
      } 
     } 
    } 
} 

Answer 2

Вот пример код для предварительного заказа обхода с использованием модифицированного Моррисом обхода.

Аналогичным образом можно изменить левую ссылку правого предшественника для обхода после ордера.

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

void preOrderNonRecursive(BSTNode* root) 
{ 
    if(!root) 
     return; 
    BSTNode* cur = root; 

    while(cur) 
    { 
     bool b = false; 
     BSTNode* pre = NULL; 
     if (cur->left) 
     { 
      pre = cur->left; 
      while(pre->right && pre->right != cur) 
       pre = pre->right; 
      if(!pre->right) 
      { 
       pre->right = cur; 
       b = true; 
      }    
      else 
       pre->right = NULL; 
     } 
     else 
      printf("%d\n",cur->val); 

     if(b) 
     { 
      printf("%d\n",cur->val); 
      cur = cur->left;   
     } 
     else    
      cur = cur->right; 
    } 
} 

Answer 3

/PREORDER Реализация без стека и рекурсии/

private static void morrisPreorder(){ 
     while(node != null){ 
      System.out.println(node.getData()); 
      if (node.getLeftNode() == null){ 
       node = node.getRightNode(); 
      } else { 
       Node rightnode = node.getRightNode(); 
       Node current = node.getLeftNode(); 
       while(current.getRightNode() != null && current.getRightNode().getData() != node.getData()) 
        current = current.getRightNode(); 
       if(current.getRightNode() == null){ 
        current.setRightNode(node.getRightNode()); 
        node = node.getLeftNode(); 
       } else { 
        node = node.getRightNode(); 
       } 
      } 
     } 
    } 

Answer 4

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

   1 
      /\ 
      2 3 
     /\ 
     4 5 

мы может создать поток на правом узле 4, указывающем на узел 5. Мы можем создать поток на правом узле 5, указывающем на узел 2.

Но на узле 2 нет пустых указателей для создания любых потоков. У узла 2 уже есть указатели, указывающие на узел 4 & 5.

Answer 5

Обследование на предрядке было рассмотрено выше.

Для последующего обхода ответ «Да» также.

Единственные изменения, которые вам нужны: 1. Когда право ребенка предшественника является текущий узел, установить правильный ребенок Null и обратно выходные все узлы с левого потомка текущего узла к предшественнику , 2. Настройте фиктивный узел и установите его левый дочерний элемент в корень дерева.

Java-код написан здесь:

private void printPostTraverse(List<Integer> traverseList, TreeNode start, TreeNode end) { 
     TreeNode node = start; 
     int insertIndex = traverseList.size(); 
     while (node != end) { 
      traverseList.add(insertIndex, node.val); 
      node = node.right; 
     } 
     traverseList.add(insertIndex, node.val); 
    } 

    public List<Integer> postorderMorrisTraversal(TreeNode root) { 
     List<Integer> traverseList = new ArrayList<>(); 
     TreeNode dummy = new TreeNode(-1); 
     dummy.left = root; 
     TreeNode cur = dummy, prev = null; 
     while (cur != null) { 
      if (cur.left == null) { 
       cur = cur.right; 
      } else { 
       prev = cur.left; 
       while (prev.right != null && prev.right != cur) 
        prev = prev.right; 

       if (prev.right == null) { 
        prev.right = cur; 
        cur = cur.left; 
       } else { 
        // Modification on get the traversal list 
        printPostTraverse(traverseList, cur.left, prev); 
        prev.right = null; 
        cur = cur.right; 
       } 
      } 
     } 
     return traverseList; 
    }