Method morris

src/tree/binary/traverse.rs:151–195

# Safety This is highly unsafe, due to pointer 时间复杂度 O(n), 空间复杂度 O(1) 大概思路：当一个node有left subtree时，需要遍历left subtree 的各节点，完成left subtree的遍历，需要回溯到node，这个回 溯指针记录在left_child.right中 点评：利用tree本身的node记录回溯指针（避免用栈记录回溯）， 使得空间复杂度由 O(n) => O(1)

(tree: &mut Tree<K, V>)

    /// 点评：利用tree本身的node记录回溯指针（避免用栈记录回溯），
    /// 使得空间复杂度由 O(n) => O(1)
    pub unsafe fn morris<K, V>(tree: &mut Tree<K, V>) -> Vec<K>
    where
        K: Copy,
    {
        let mut results = vec![];
        let mut cur = tree.root;

        while let Some(node) = cur {
            match node.as_ref().left {
                Some(left) => {
                    let mut record = left;

                    //traverse right subtree, find前驱node
                    loop {
                        match record.as_ref().right {
                            Some(r) if r != node => record = r,
                            _ => break,
                        }
                    }

                    match record.as_ref().right {
                        Some(_r) => {
                            //已线索化
                            cur = node.as_ref().right;
                            record.as_mut().right = None;
                        }
                        None => {
                            results.push(node.as_ref().key);

                            //未线索化
                            record.as_mut().right = cur;
                            cur = Some(left);
                        }
                    }
                }
                None => {
                    results.push(node.as_ref().key);
                    //无left subtree, 直接跨到right subtree
                    cur = node.as_ref().right;
                }
            }
        }

        results
    }

    /// # Safety
    ///