我编写了一个程序，它使用 morris 遍历来遍历二叉树。出于好奇，我开始在中序遍历和莫里斯遍历之间进行基准测试。我发现在运行 1000 次之后，morris 遍历的平均时间是 5795，而递归中序遍历的平均时间是 2457，这几乎是 morris 遍历的两倍。
我认为使用线程二叉树的 morris 遍历复杂度为 O(NlogN)，递归中序遍历的复杂度为 O(N)，因此显然 morris 遍历需要更多时间。我的问题如下：
- 我提到的时间复杂度是否正确？
- 如果这里的 morris 遍历非常慢，那么在递归并不昂贵的 Java 世界中这个用例是什么。
java我关于递归在wrt 语言中成本不高的断言是否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);
}