二叉树O（n）的InOrder树遍历的时间复杂度？ [英] Time Complexity of InOrder Tree Traversal of Binary Tree O(n)?

问题描述

public void iterativePreorder(Node root) {
        Stack nodes = new Stack();
        nodes.push(root);

        Node currentNode;

        while (!nodes.isEmpty()) {
                currentNode = nodes.pop();
                Node right = currentNode.right();
                if (right != null) {
                        nodes.push(right);
                }
                Node left = currentNode.left();
                if (left != null) {
                        nodes.push(left);      
                }
                System.out.println("Node data: "+currentNode.data);
        }
}

资料来源：Wiki Tree Traversal

Source: Wiki Tree Traversal

时间复杂度是O（n）吗？如果使用递归完成，时间复杂度是否相同？

Is the time complexity going to be O(n)? And is the time complexity going to be the same if it was done using recursion?

新问题：
如果我使用上面的代码来查找来自TreeA的某个节点创建另一个树TreeB，它将拥有与TreeA一样多的节点，那么创建TreeB的复杂性将是O（n ^ 2），因为它是n个节点，并且每个节点将使用上面的代码O（ n）？

New Question: If I were to use to above code to find a certain node from a TreeA to create another tree TreeB which will have as much nodes as TreeA, then would the complexity of creating TreeB be O(n^2) since it is n nodes and each node would use the above code which is O(n)?

推荐答案

自二叉树的遍历（与搜索相对而言其他树操作）要求处理所有树节点，任何遍历算法的最小复杂度为O（n），即线性wrt树中的节点数。这是一个不可改变的事实，除非有人建造量子计算机或其他东西，否则不会改变......

Since the traversal of a binary tree (as opposed to the search and most other tree operations) requires that all tree nodes are processed, the minimum complexity of any traversal algorithm is O(n), i.e. linear w.r.t. the number of nodes in the tree. That is an immutable fact that is not going to change in the general case unless someone builds a quantum computer or something...

至于递归，唯一的区别是递归方法调用通过将调用帧推送到JVM堆栈来隐式构建堆栈，而示例代码显式构建堆栈。我宁愿不推测两者之间的任何性能差异 - 您应该为每个特定用例场景分析和基准两种备选方案。

As for recursion, the only difference is that recursive method calls build the stack implicitly by pushing call frames to the JVM stack, while your sample code builds a stack explicitly. I'd rather not speculate on any performance difference among the two - you should profile and benchmark both alternatives for each specific use case scenario.

这篇关于二叉树O（n）的InOrder树遍历的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！