如何为二叉搜索树编写 GetEnumerator()

本文关键字：GetEnumerator 搜索树 | 更新日期: 2023-09-27 18:34:10

我有一个BinaryTree类和一个用于保存节点的BinaryTreeNode，我已经制作了树并为其编写了前序、后序和按顺序的方法。
但我不知道如何为它编写IEnumerator<T>（我只想按顺序使用GetEnumerator()方法）。问题是inOrder方法的返回类型是void 。我想让它IEnumerator<T>而不是MessageBox返回数据。

我该怎么做？

public void PreOrder(BinaryTreeNode<T> node)
{
    if (node != null)
    {
        MessageBox.Show(node.Value.ToString());
        PreOrder(node.Left);
        PreOrder(node.Right);
    }
}
public void PostOrder(BinaryTreeNode<T> node)
{
    if (node != null)
    {
        PostOrder(node.Left);
        PostOrder(node.Right);
        MessageBox.Show(node.Value.ToString());
    }
}
public void InOrder(BinaryTreeNode<T> node)
{
    if (node != null)
    {
        InOrder(node.Left);
        MessageBox.Show(node.Value.ToString());
        InOrder(node.Right);
    }
}
public void Clear()
{
    root = null;
    Count = 0;
}
public IEnumerator<T> GetEnumerator()
{
    InOrder(root);
    return null; // error in forerach loop
}
IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}

我认为我的这部分代码就足够了。
这就是我定义BinaryTree类的方式：

public class BinaryTree<T> : IEnumerable<T> where T : IComparable<T>

这就是我对BinaryTreeNode的定义：

public class BinaryTreeNode<T> : IComparable<T> where T : IComparable<T>

如何为二叉搜索树编写 GetEnumerator()

这是一种方法，使用 yield ：

public IEnumerator<T> GetEnumerator()
{
    if (Left != null)
    {
        foreach(var v in Left)
        {
            yield return v;
        }
    }
    yield return Value;
    if (Right != null) 
    {
        foreach (var v in Right)
        {
            yield return v;
        }
    }
}

下面是使用 Linq 的更简洁的方法：

public IEnumerator<T> GetEnumerator()
{
    var leftEnumerable = (IEnumerable<T>)Left ?? new T[0];
    var rightEnumerable = (IEnumerable<T>)Right ?? new T[0];
    return leftEnumerable.Concat(new T[] { Value })
                         .Concat(rightEnumerable)
                         .GetEnumerator();
}

编辑：由于您似乎有单独的BinaryTree类和BinaryTreeNode类，您可以将上述任何一个放在BinaryTreeNode中，并将以下内容放在BinaryTree：

public IEnumerator<T> GetEnumerator()
{
    return Root.GetEnumerator();
}
相关文章：