morris遍历用例

Question

我编写了一个程序，它使用morris遍历来遍历二叉树。出于好奇，我开始在无序遍历和morris遍历之间进行基准测试。我发现，在运行1000倍之后，morris遍历的平均时间为5795，递归顺序遍历的平均时间为2457，几乎是morris遍历的两倍。

我认为使用线程二叉树的morris遍历具有复杂性O(NlogN)，递归顺序遍历具有O(N)，因此显然morris遍历将花费更多的时间。我的问题如下：

• 我刚才提到的时间复杂性是否正确？
• 如果morris遍历在这里非常慢，那么在java世界中，这种遍历的用例是什么?在这里，递归并不是非常昂贵的。
• 我关于递归的断言在java w.r.t中是否代价高昂。像C这样的语言是否正确？提前谢谢。

代码示例：

public class ThreadedBinaryTree<T extends Comparable<T>>
{
private TreeNode root;

public void morrisTraverse()
{
    TreeNode current = root;
    if(current == null)
    {
        return;
    }

    while(current != null)
    {
        if(current.left != null)
        {
            TreeNode temp = current.left;
            while(true)
            {
                if(temp.right == null) break;
                if(temp.right == current) break;
                temp = temp.right;
            }

            if(temp.right == null)
            {
                //create the link to predecessor
                temp.right = current;
                current = current.left;
            }
            else
            {
                //remove the link
                temp.right = null;
                //System.out.println(current.t);
                current = current.right;
            }
        }
        else
        {
            //System.out.println(current.t); 
            current = current.right;
        }
    }
}

public void inorder()
{
    inorder(root);
}

private void inorder(TreeNode node)
{
    if(node != null)
    {
        inorder(node.left);
        //System.out.println(node.t);
        inorder(node.right);
    }
}

private static class TreeNode<T extends Comparable<T>>
{
    private T t;
    private TreeNode left;
    private TreeNode right;

    private TreeNode(T t)
    {
        this.t = t;
    }
}
}

驱动程序：

public static void main(String[] args)
{
    ThreadedBinaryTree binaryTree = new ThreadedBinaryTree();
    binaryTree.insert(500);
    binaryTree.insert(20);
    binaryTree.insert(15);
    binaryTree.insert(25);
    binaryTree.insert(40);
    binaryTree.insert(35);
    ………….
………….. 
…………. some more inserts to tree
    int index = 1;
    long moris = 0;
    long normal = 0;
    while(index <= 1000)
    {
        long start = System.nanoTime();
        binaryTree.morrisTraverse();
        moris += System.nanoTime() -start;
        //System.out.println("__________________________________________________________");
        long start1 = System.nanoTime();
        binaryTree.inorder();
        normal+=System.nanoTime() -start1;
        index++;
    }
    System.out.println(moris/1000);
    System.out.println(normal/1000);
}

Answer 1

我刚才提到的时间复杂性是否正确？

不，Morris遍历也是线性的。

如果morris遍历在这里非常慢，那么在java世界中这种情况的用例是什么，在这里递归并不是很昂贵的。

莫里斯没有多余的空间。递归使用堆栈空间。如果这是拥有足够内存与没有内存之间的区别，那么您可能不应该首先选择Java。

在java w.r.t中，我关于递归的断言是否代价高昂。像C这样的语言是否正确？

这是评估的属性，而不是语言规范。没有任何具体的执行困难会先验地表明其中一项比另一项更有效。