二叉树遍历的复杂性 [英] Complexities of binary tree traversals

问题描述

数据结构中二叉树的中序、后序和前序遍历的时间复杂度是多少??是 O(n) 还是 O(log n) 或 O(n^2)??

What is the time complexity of inorder,postorder and preorder traversal of binary trees in data structures?? Is it O(n) or O(log n) or O(n^2)??

推荐答案

中序、前序和后序遍历是深度优先遍历.

In-order, Pre-order, and Post-order traversals are Depth-First traversals.

对于图，深度优先遍历的复杂度为 O(n + m)，其中 n 是节点数，m 是边数.

For a Graph, the complexity of a Depth First Traversal is O(n + m), where n is the number of nodes, and m is the number of edges.

因为二叉树也是图，这里同样适用.每个深度优先遍历的复杂度都是 O(n+m).

Since a Binary Tree is also a Graph, the same applies here. The complexity of each of these Depth-first traversals is O(n+m).

由于在二叉树的情况下可以源自节点的边数限制为 2，所以二叉树中的最大边总数为 n-1，其中 n 是节点总数.

Since the number of edges that can originate from a node is limited to 2 in the case of a Binary Tree, the maximum number of total edges in a Binary Tree is n-1, where n is the total number of nodes.

复杂度变为 O(n + n-1)，也就是 O(n).

The complexity then becomes O(n + n-1), which is O(n).

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