在LUA中，如何编写二叉树的迭代器？

Question

在LUA中，如何编写二叉树的迭代器。例如所以我可以做类似的事情：

for node in tree:visit() do ... end

我一直在尝试，但我能做的最好的事情就是在树上行走，携带一些功能

fun

作为有效负载。例如

function klass(s,    t) t={ako=s}; t.__index=t; return t end

NODE=klass"NODE"
function NODE.new(x,l,r) return setmetatable( {x=x, left=l, right=r},NODE) end

function NODE:visit(fun,  lvl)
  lvl=lvl or 0
  fun(lvl,self)
  for _,kid in pairs{self.left, self.right} do 
    if kid then kid:visit(fun, lvl+1) end end end

--- eg -----------------------------
function eg(x,stop,     node)
  node = NODE.new(x)
  if x < stop/2 then
    node.left = eg(2*x,stop)
    node.right = eg(2*x+1,stop) end
  return node end 

tree=eg(1,32)
tree:visit( function(lvl,node) print(('|.. '):rep(lvl)..node.x) end )

这会产生我想要的输出：

1
|.. 2
|.. |.. 4
|.. |.. |.. 8
|.. |.. |.. |.. 16
|.. |.. |.. |.. 17
|.. |.. |.. 9
|.. |.. |.. |.. 18
|.. |.. |.. |.. 19
|.. |.. 5
|.. |.. |.. 10
|.. |.. |.. |.. 20
|.. |.. |.. |.. 21
|.. |.. |.. 11
|.. |.. |.. |.. 22
|.. |.. |.. |.. 23
|.. 3
|.. |.. 6
|.. |.. |.. 12
|.. |.. |.. |.. 24
|.. |.. |.. |.. 25
|.. |.. |.. 13
|.. |.. |.. |.. 26
|.. |.. |.. |.. 27
|.. |.. 7
|.. |.. |.. 14
|.. |.. |.. |.. 28
|.. |.. |.. |.. 29
|.. |.. |.. 15
|.. |.. |.. |.. 30
|.. |.. |.. |.. 31

但是我该如何编写它才能将其放入

for

循环中？

我想避免两种解决方案：

• 我不想使用

  pairs

  来遍历通过上面的代码生成的节点列表（因为我想支持任意深度的树的增量遍历）
• 我希望答案比 https://github.com/guicaulada/lua-bintrees/blob/main/bintrees/iterator.lua 简单得多

Answer 1

如果需要将递归函数转换为循环，那么就需要一个栈来模拟递归过程中的调用栈。

Lua中的for-in语句要求函数返回3个参数，一个迭代器函数，一个状态（这里的节点堆栈）和一个初始值（这里省略）：

function NODE:visit()
  return function (stack)
    if #stack == 0 then return nil end
    local node = table.remove(stack)
    if node.right then stack[#stack + 1] = node.right end
    if node.left then stack[#stack + 1] = node.left end
    return stack, node;
  end, {self}
end

用法：

for _, node in tree:visit() do
  print(node.x)
end