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

综合讨论区 Julia入门
1

我这里在 README 中已经提到这个问题，并写出了相关代码 GitHub - nesteiner/BinaryTree.jl: 二叉树 written in Julia
本来是在 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

教程在这里 https://blog.csdn.net/u010157717/article/details/41266873
现在的问题是如何修正我的代码，哪位大佬能绑下忙

3

Stack 在这里 GitHub - nesteiner/LinkedList.jl: Julia 链表

测试案例

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是没有问题的，因为二叉树的其他遍历方法都测试过了，没有问题，唯一出错的是中序遍历

4

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

1 个赞