<p>我有一个保存玩家对象的AVL树。每个玩家都有一个名字和等级。树节点根据玩家等级排序。我首先遍历树的深度,然后将每个节点附加到按排名排序的玩家列表中(按降序,因此是从右向左遍历)</p>
<p>我读到的所有东西都告诉我,AVL树的复杂度为O(logn),但当我查看顺序遍历函数时,我注意到它递归调用自己两次,我认为这会使它成为O(2^n)。有没有更有效的方法来遍历我不知道的树?还是我的大O计算错了</p>
<pre><code>def traverseRightToLeft(node, array = []):
# Base case
if node is None:
return
# Recursively check if there are any right child nodes, append the current node data to the list then recursively check if there are any left child nodes
else:
traverseRightToLeft(node.right, array)
array.append(node.data)
traverseRightToLeft(node.left, array)
return array
</code></pre>