如何编写中序遍历的迭代器?

我这里在 README 中已经提到这个问题,并写出了相关代码 https://github.com/nesteiner/BinaryTree.jl#org8339a96
本来是在 Slack 问的,可是没人理我 :sob:


这里简单说一下,我定义了一个二叉树节点类型

abstract type BinaryTreeNode{T} end
mutable struct BinaryTreeNil{T} <: BinaryTreeNode{T} end

mutable struct BinaryTreeCons{T} <: BinaryTreeNode{T}
  data::T
  left::Union{BinaryTreeCons{T}, BinaryTreeNil{T}}
  right::Union{BinaryTreeCons{T}, BinaryTreeNil{T}}
end

我又自定义了迭代器类型,比如中序遍历迭代器

mutable struct InOrderIterator{T} <: BinaryTreeIterator{T}
  node::BinaryTreeNode{T}
  length::Int
end

inorder(tree::AbstractBinaryTree{T}) where T = InOrderIterator{T}(tree.root, length(tree))

现在的问题是,我写的中序遍历方法出问题了,使用 collect(inorder(tree)) 的时候有好几个数据是 #undef
这是我参考 Java 迭代器写的代码

function iterate(iterator::InOrderIterator{T}) where T
  current = iterator.node

  if isnil(current)
    return nothing
  end

  stack = Stack(BinaryTreeNode{T})
  while !isnil(current)
    push!(stack, current)
    current = left(current)
  end

  result = top(stack)
  pop!(stack)
  
  # assign back
  iterator.node = right(result)
  # return statement

  return result, stack
end

function iterate(iterator::InOrderIterator{T}, stack::Stack{BinaryTreeNode{T}}) where T
  current = iterator.node
  if isempty(stack)
    return nothing
  end

  while !isnil(current)
    push!(stack, current)
    current = left(current)
  end

  result = top(stack)
  pop!(stack)
  # assign back
  iterator.node = right(result)
  # return
  return result, stack
end

教程在这里 实现二叉树中序Iterator_天下任我行-CSDN博客
现在的问题是如何修正我的代码,哪位大佬能绑下忙

Stack 在这里 https://github.com/nesteiner/LinkedList.jl

测试案例

using BinaryTree, Test

@testset "test every walk work status" begin
  tree = BSTree(Int)
  nums = [46, 76, 39, 99, 66, 64, 78, 2, 38, 81]
  # nums = 1:10
  for i in nums    
    insert!(tree, i)
  end

  @show nums
  # @show collect(map(dataof, preorder(tree)))
  # @show collect(map(dataof, postorder(tree)))
  # @show collect(map(dataof, levelorder(tree)))
  # @show collect(map(dataof, inorder(tree)))
  @show collect(map(dataof, inorder(tree)))

  # @show collect(map(dataof, preorder(tree)))
  # @show collect(preorder(tree))
  # @test collect(map(dataof, preorder(tree))) |> unique |> sort ==
  #   collect(map(dataof, postorder(tree))) |> unique |> sort ==
  #   collect(map(dataof, levelorder(tree))) |> unique |> sort ==
  #   collect(map(dataof, inorder(tree))) |> unique |> sort

  # @test length(preorder(tree)) == length(inorder(tree)) == length(postorder(tree)) == length(levelorder(tree))
end

Stack是没有问题的,因为二叉树的其他遍历方法都测试过了,没有问题,唯一出错的是中序遍历

我修好了,:yum: 文档已更新

1 个赞