遍历树结构

本文关键字：结构 遍历 | 更新日期: 2023-09-27 18:31:22

我正在尝试了解如何遍历树形数据结构，但我在执行此操作时遇到了问题，尤其是当我尝试使用IEnumerable时。我希望树作为字典，以便我可以通过字符串名称引用节点。树将包含不同的类对象，但由于这些对象都实现了接口IMyInterface，树的类型将是IMyInterface接口。

我有一棵树：

internal class Tree<T>
{
    private TreeNode<T> root;
    internal Tree(T value)
    {
        if (value == null)
        {
            throw new ArgumentNullException(
                "Cannot use a null value to construct a tree.");
        }
        this.root = new TreeNode<T>(value);
    }
    internal Tree(T value, params Tree<T>[] children) : this(value)
    {
        foreach (Tree<T> child in children)
        {
            this.root.AddChild(child.root);
        }
    }
    internal TreeNode<T> Root
    {
        get { return this.root; }
    }
    private void PrintDFS(TreeNode<T> root, int spaces)
    {
        if (spaces < 0)
        {
            throw new ArgumentOutOfRangeException(
                "The number of spaces used to represent the parent-child relation in a tree must be greater than or equal to zero.");
        }
        if (this.root == null)
        {
            return;
        }
        StringBuilder sb = new StringBuilder();
        sb.Append(' ', spaces);
        sb.Append(root.Value);
        TreeNode<T> child = null;
        foreach (Tree<T> child in this.root)     // <--- this generates an error
        {
            PrintDFS(child, spaces);
        }
    }
    // Traverses and prints the tree in
    // Depth-First Search (DFS) manner
    internal void TraverseDFS()
    {
        this.PrintDFS(this.root, 0);
    }
}

我的节点类是：

internal class TreeNode<T> : IEnumerable<TreeNode<T>>
{
    private T value;
    private bool hasParent;
    private readonly Dictionary<string, TreeNode<T>> children = new Dictionary<string, TreeNode<T>>();
    internal TreeNode(T value)
    {
        if (value == null)
        {
            throw new ArgumentNullException(
                "Cannot insert null values for a tree node!");
        }
        this.value = value;
        this.children = new Dictionary<string, TreeNode<T>>();      // dictionary that holds the children of each node
    }
    internal T Value
    {
        get { return this.value; }
        set { this.value = value; }
    }
    internal int ChildrenCount
    {
        get
        {
            return this.children.Count;
        }
    }
    internal void AddChild(TreeNode<T> child)
    {
        if (child == null)
        {
            throw new ArgumentNullException(
                "Cannot insert null value as child node.");
        }
        if (child.hasParent)
        {
            throw new ArgumentException(
                "The child node already has a parent.");
        }
        child.hasParent = true;
        this.children.Add(child.ToString(), child);
    }
    internal TreeNode<T> GetChild(string nodeName)
    {
        return this.children[nodeName];
    }
    internal IEnumerator<TreeNode<T>> GetEnumerator()
    {
        return this.children.Values.GetEnumerator();
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
    IEnumerator<TreeNode<T>> IEnumerable<TreeNode<T>>.GetEnumerator()
    {
        throw new NotImplementedException();
    }
}

问题似乎是代码：

foreach (Tree<T> child in this.root)     // <--- this generates an error
{
    PrintDFS(child, spaces);
}

（来自 Tree 类的代码片段）任何建议将不胜感激。

编辑

我收到错误消息：

错误 669 名为"child"的局部变量不能在此作用域中声明，因为它会给"child"赋予不同的含义，"child"已在"父或当前"作用域中用于表示其他内容。

错误 672 无法将类型 TreeNode<T> 转换为 Tree<T>

和警告消息：

警告 668 TreeNode<T>不实现"集合"模式。 TreeNode<T>.GetEnumerator()要么是静态的，要么不是公开的。

遍历树结构

问题 #1

错误 669 无法在此声明名为"child"的局部变量 范围，因为它会给"孩子"赋予不同的含义，即 已在"父级或当前"范围内用于表示其他内容。

TreeNode<T> child = null;
foreach (Tree<T> child in this.root)     // <--- this generates an error
{
     PrintDFS(child, spaces);
}

您已经有一个child变量。您需要以不同的方式命名它们。这个错误是不言自明的。

对于这种情况，只需从foreach上方删除child，因为它在那里毫无用处。

foreach (var child in this.root) 
{
     PrintDFS(child, spaces);
}

我想你想要TreeNode<T>，但不确定应该从root中实际返回什么。

问题 #2

错误 672 无法将类型树节点转换为树

如果你应该循环TreeNode<T>，而不是像错误状态那样Tree<T>。只需使用var，除非您实际上尝试迭代树而不是节点。

问题 #3

警告 668 TreeNode 未实现"集合"模式。TreeNode.GetEnumerator（） 要么是静态的，要么不是公共的。

它必须是公开的。内部不会削减它，因为它需要遵守 IEnumerable 合同。看起来你已经解决了这个问题，尽管通过它的显式实现。

首先，将 3 个 GetEnumertor 函数替换为以下 2 个：

public IEnumerator<TreeNode<T>> GetEnumerator()
{
  return this.children.Values.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
  return this.GetEnumerator();
}

然后更改 PrintDFS 循环的最后一部分，如下所示：

//TreeNode<T> child = null;
foreach (var child in this.root)
{
  PrintDFS(child, spaces);
}

编译。

相关文章：