列表索引超出范围 - BST 的预序遍历

Question

我正在尝试预先遍历我以数组形式获得的 BST：

示例输入： ["5","2","6","1","9","#","8","#","#","#","#","4","#"] 其中 # 是树中不存在的节点

我的输出应该是前序遍历的结果：

5 2 1 9 6 8 4

到目前为止我已经成功了，除了最后一个节点，我得到的索引超出了范围。到目前为止，这是我的代码：

 def traverse(strArr):
  strArr.insert(0, '#')

  def preorder(arr, ind):
    if ind <= len(arr) and arr[ind] != '#':
      print(arr[ind])
      preorder(arr, 2*ind)
      preorder(arr, 2*ind+1)

  preorder(strArr, 1)

traverse(["5","2","6","1","9","#","8","#","#","#","#","4","#"])

我需要更改什么才能使最后一个节点（在本例中为 4）显示无误？

Answer 1

嗯，有两个问题。

数组是zero-based： if ind <= len(arr) and arr[ind] != '#': 允许 ind 变成 len(arr) ，它比 arr 的最后一个元素的索引更大。在同一行中，您使用 ind 作为索引来访问数组 arr[ind]，结果是 IndexError。这里的修复是检查 ind 是否小于 len(arr):

if ind < len(arr) and arr[ind] != '#':

4 索引错误：它目前位于索引 11，但应该位于索引 13。修复这里：

traverse(["5","2","6","1","9","#","8","#","#","#","#","#","#","4","#"])

列表索引超出范围 - BST 的预序遍历

list index out of range - pre-order traversal of BST

python

algorithm

tree

binary-search-tree

traversal