遍历一个树形结构 [英] Traversing a Tree Structure

问题描述

我想了解如何遍历树的数据结构，我有这样做的一个问题，尤其是当我试图使用的IEnumerable 。我想树作为一个字典，所以我可以通过自己的字符串名称引用的节点。树将持有不同的类对象，但这些对象都实现一个接口 IMyInterface的，输入树将在 IMyInterface的接口

我有树：

 内部类树< ; T> 
 {
私人树节点< T>根; 
 
内部树（T值）
 {
如果（价值== NULL）
 {
抛出新的ArgumentNullException（
无法使用一个空值来构造一棵树）。 
} 
 
 this.root =新的TreeNode< T>（值）; 
} 
 
内部树（T值，则params树< T> []小孩）：这个（值）
 {
的foreach（树< T>儿童在子女）
 {
 this.root.AddChild（child.root）; 
} 
} 
 
内部树节点< T>根
 {
 {返回this.root; } 
} 
 
私人无效PrintDFS（树节点< T>根，诠释空格）
 {
如果（空格℃下）
 {
抛出新ArgumentOutOfRangeException（
用于表示在一个树中的父 - 子的关系必须是大于或等于零的空间的数目。）; 
} 
 
如果（this.root == NULL）
 {
的回报; 
} 
 
 StringBuilder的SB =新的StringBuilder（）; 
 sb.Append（''，空格）; 
 sb.Append（root.Value）; 
 
树节点< T>孩子= NULL; 
 
的foreach（树< T>儿童在this.root）//< ---这将产生错误
 {
 PrintDFS（儿童，空格）; 
} 
} 
 
 //导线中，并打印在
树//深度优先搜索（DFS）的方式
内部空隙TraverseDFS（）
 {
 this.PrintDFS（this.root，0）; 
} 
} 
  

和我的节点类是：

 内部类树节点< T> ：IEnumerable的<&树节点LT; T>> 
 {
私人的T值; 
私人布尔hasParent; 
 
私人只读字典<字符串，树节点< T>>孩子=新词典与LT;字符串，树节点< T>>（）; 
 
内部树节点（T值）
 {
如果（价值== NULL）
 {
抛出新的ArgumentNullException（
无法插入对于树节点空值）！; 
} 
 
 THIS.VALUE =价值; 
 this.children =新词典<字符串，树节点< T>>（）; //字典保存每个节点
的孩子} 
 
内部吨价
 {
 {返回THIS.VALUE; } 
集合{THIS.VALUE =价值; } 
} 
 
内部INT ChildrenCount 
 {
得到
 {
返回this.children.Count; 
} 
} 
 
内部空隙的AddChild（树节点< T>儿童）
 {
如果（孩子== NULL）
 {
抛出新的ArgumentNullException（
无法插入空值的子节点。）; 
} 
 
如果（child.hasParent）
 {
抛出新的ArgumentException（
的子节点已经有一个父。）; 
} 
 
 child.hasParent = TRUE; 
 this.children.Add（child.ToString（），子女）; 
} 
 
内部树节点< T> GetChild（字符串节点名称）
 {
返回this.children [节点名称]; 
} 
 
内部的IEnumerator<&树节点LT; T>>的GetEnumerator（）
 {
返回this.children.Values.GetEnumerator（）; 
} 
 
的IEnumerator IEnumerable.GetEnumerator（）
 {
返回this.GetEnumerator（）; 
} 
 
&的IEnumerator LT;树节点< T>> IEnumerable的<&树节点LT; T>> .GetEnumerator（）
 {
抛出新NotImplementedException（）; 
} 
} 
  

这个问题似乎是代码：

 的foreach（树< T>儿童在this.root）//< ---这将产生错误
 {
 PrintDFS（儿童，空格）; 
} 
  

（代码从树类片段）的任何建议，将不胜感激。

修改

我得到的错误信息：

错误669命名为'孩子'的局部变量不能在此范围内声明，因为它会给予不同的意义，这已经是一个'父母或现在的范围用来表示一些'孩子'， 。否则

错误672无法将类型树节点< T> 到树< T>

和警告消息：

警告668 树节点< T> 并没有实现集合的模式。 树节点< T> .GetEnumerator（）是静态或不公开

解决方案

问题＃1

错误669命名为'孩子'的局部变量不能在这个
范围内声明，因为它会赋予不同的含义，以'孩子'，这是一个'父母或现在的范围已用来表示别的

 树节点< T>孩子= NULL; 
 
的foreach（树< T>儿童在this.root）//< ---这将产生错误
 {
 PrintDFS（儿童，空格）; 
} 
  

您已经有一个孩子变量。你需要以不同的名字。该错误是相当自我解释。

对于这种情况，只是删除孩子从上面的的foreach ，因为它是无用的存在。

 的foreach（VAR孩子this.root）
 {
 PrintDFS（儿童，空格）; 
} 
  

我想你想树节点< T> ，但不知道什么应该根的实际回报了。

问题＃2

错误672不能键入树节点转换为树

如果你应该可以遍历树节点< T> ，而不是树< T> 作为错误状态。只需使用 VAR ，除非你实际上是试图遍历树而不是节点。

问题＃3

警告668的TreeNode没有实现集合的模式。 TreeNode.GetEnumerator（）是静态或不公开。

它需要公众。因为它需要坚持IEnumerable的合同内不剪。看起来你有与明确的实施解决了它，虽然。

I am trying to understand how to traverse a tree data structure, and I am having a problem doing it, especially as I am trying to use IEnumerable. I want the tree as a dictionary so I can refer to the nodes by their string names. The tree will hold different class objects but as these objects all implement an interface IMyInterface, type of the tree will be the IMyInterface interface.

I have the tree:

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);
    }
}

And my node class is:

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();
    }
}

The issue seems to be the code:

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

(Code snippet from the Tree class) Any suggestions would be greatly appreciated.

EDIT

I get the error messages:

Error 669 A local variable named 'child' cannot be declared in this scope because it would give a different meaning to 'child', which is already used in a 'parent or current' scope to denote something else.

Error 672 Cannot convert type TreeNode<T> to Tree<T>

And the warning message:

Warning 668 TreeNode<T> does not implement the 'collection' pattern. TreeNode<T>.GetEnumerator() is either static or not public.

解决方案

Issue #1

Error 669 A local variable named 'child' cannot be declared in this scope because it would give a different meaning to 'child', which is already used in a 'parent or current' scope to denote something else.

TreeNode<T> child = null;

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

You already have a child variable. You need to name them differently. The error is pretty self explanatory.

For this situation, just remove child from above the foreach since it is useless there.

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

I think you wanted TreeNode<T>, but not sure what was supposed to actually return out of root.

Issue #2

Error 672 Cannot convert type TreeNode to Tree

If you're supposed to be looping over TreeNode<T>, not Tree<T> as the error states. Just use var unless you are actually trying to iterates trees and not nodes.

Issue #3

Warning 668 TreeNode does not implement the 'collection' pattern. TreeNode.GetEnumerator() is either static or not public.

It needs to be public. Internal does not cut it because it needs to adhere to the IEnumerable contract. Looks like you have that solved though with the explicit implementation of it.

这篇关于遍历一个树形结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！