morris 遍历的用例

Question

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

\n\n

我认为使用线程二叉树的 morris 遍历的复杂度为 O(NlogN)，而递归中序遍历的复杂度为 O(N)，所以显然 morris 遍历将花费更多时间。\n我的问题如下：

\n\n

\n
• 我提到的时间复杂度正确吗？
\n
• 如果 morris 遍历在这里非常慢，那么在递归并不真正昂贵的 Java 世界中，它的用例是什么。
\n
• 我关于递归在javawrt 语言中成本不高的断言C是否正确？\n提前致谢。
\n

\n\n

代码示例：

\n\n

public class ThreadedBinaryTree<T extends Comparable<T>>\n{\nprivate TreeNode root;\n\npublic void morrisTraverse()\n{\n    TreeNode current = root;\n    if(current == null)\n    {\n        return;\n    }\n\n    while(current != null)\n    {\n        if(current.left != null)\n        {\n            TreeNode temp = current.left;\n            while(true)\n            {\n                if(temp.right == null) break;\n                if(temp.right == current) break;\n                temp = temp.right;\n            }\n\n            if(temp.right == null)\n            {\n                //create the link to predecessor\n                temp.right = current;\n                current = current.left;\n            }\n            else\n            {\n                //remove the link\n                temp.right = null;\n                //System.out.println(current.t);\n                current = current.right;\n            }\n        }\n        else\n        {\n            //System.out.println(current.t); \n            current = current.right;\n        }\n    }\n}\n\npublic void inorder()\n{\n    inorder(root);\n}\n\nprivate void inorder(TreeNode node)\n{\n    if(node != null)\n    {\n        inorder(node.left);\n        //System.out.println(node.t);\n        inorder(node.right);\n    }\n}\n\nprivate static class TreeNode<T extends Comparable<T>>\n{\n    private T t;\n    private TreeNode left;\n    private TreeNode right;\n\n    private TreeNode(T t)\n    {\n        this.t = t;\n    }\n}\n}\n

\n\n

驱动程序：

\n\n

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

\n

Answer 1

我提到的时间复杂度正确吗？

不，莫里斯遍历也是线性的。

如果 morris 遍历在这里非常慢，那么在递归并不真正昂贵的 Java 世界中，它的用例是什么

莫里斯没有使用额外的空间。递归使用堆栈空间。如果这就是有足够内存和没有足够内存之间的区别，那么您可能一开始就不应该选择 Java。

我关于在像 C 这样的 java wrt 语言中递归成本不高的断言是否正确？

这是评估的属性，而不是语言规范。不存在任何特定的实施困难可以先验地表明其中一个比另一个更有效。