Blog. Morris 树遍历算法 [blog/data-structure/morris]

/// Traditional recursive inorder traversal
pub fn[A] inorder_recursive(root : Node[A]?, f : (A) -> Unit) -> Unit {
  match root {
    None => ()
    Some({ left, data, right }) => {
      inorder_recursive(left, f)
      f(data)
      inorder_recursive(right, f)
    }
  }
}

/// Traditional iterative inorder traversal using stack
pub fn[A] inorder_iterative(root : Node[A]?, f : (A) -> Unit) -> Unit {
  let stack : Array[Node[A]] = []
  let mut current = root
  
  while not(stack.is_empty()) || current is Some(_) {
    while current is Some(_) {
      stack.push(current.unwrap())
      current = current.unwrap().left
    }
    
    let node = stack.unsafe_pop()
    f(node.data)
    current = node.right
  }
}

pub fn[A] morris_tree_traversal_pattern_match(
  root : Node[A]?,
  f : (A) -> Unit,
) -> Unit {
  loop root {
    None => break
    // This part of the code is responsible for transforming the tree into a right-skewed tree
    Some({ left: Some(_) as left, .. } as cur_) as cur => {
      // The rightmost node of the left subtree is the predecessor of the last node visited in the left subtree during inorder traversal, where the last node is the root of the left subtree
      guard right_most_node(left) is Some(left_subtree_last_visited_node)
      // Create a back edge here so that after visiting the left subtree, we can return to the root of the left subtree
      left_subtree_last_visited_node.right = cur
      let cur_left = cur_.left

      // This step prevents infinite loops when traversing through the previously created back edge
      cur_.left = None

      // Continue visiting the left subtree
      continue cur_left
    }
    Some(cur_) => {
      // At this point the tree has become a right-skewed tree, with no more left subtrees
      f(cur_.data)
      // Simply continue visiting the right subtree
      continue cur_.right
    }
  }
}