如何在C＃中使用树型数据结构

我在this SO question找到了一棵树的实现。不幸的是我不知道如何使用它。我也做了更改它，因为链表没有添加方法：如何在C＃中使用树型数据结构

delegate void TreeVisitor<T>(T nodeData); 

class NTree<T> 
{ 
    T data; 
    List<NTree<T>> children; 

    public NTree(T data) 
    { 
     this.data = data; 
     children = new List<NTree<T>>(); 
    } 

    public void AddChild(T data) 
    { 
     children.Add(new NTree<T>(data)); 
    } 

    public NTree<T> GetChild(int i) 
    { 
     return children[i]; 
    } 

    public void Traverse(NTree<T> node, TreeVisitor<T> visitor) 
    { 
     visitor(node.data); 
     foreach (NTree<T> kid in node.children) 
      Traverse(kid, visitor); 
    } 
}

我有类命名的TTable，我想保存它的孩子和他们在这棵树的孙子（...）。我的需要是找到眼前的孩子，而不是遍历整棵树。我也可能需要找一些标准的孩子。比方说，tTable只有名字，我想找到名称符合某些标准的孩子。 tTables构造函数根据int-value给出了一个值（以某种方式）。

如何使用遍历（写代理）如果我有这样的代码;

int i = 0; 
Dictionary<string, NTree<tTable>> tableTreeByRootTableName = 
        new Dictionary<string, NTree<tTable>>(); 
tTable aTable = new tTable(i++); 
tableTreeByRootTableName[aTable.Name] = new NTree(aTable); 
tableTreeByRootTableName[aTable.Name].AddChild(new tTable(i++)); 
tableTreeByRootTableName[aTable.Name].AddChild(new tTable(i++)); 

tableTreeByRootTableName[aTable.Name].GetChild(1).AddChild(new tTable(i++));

来源

2010-03-29 char m

这个NTree类看起来不像一个链表。你确定这就是你需要的吗？ – 2010-03-29 14:27:18

我可以向你保证'LinkedList '有一个Add方法。 – 2010-03-29 14:36:44

'LinkedList '的等价方法是'AddLast' – 2010-03-29 14:47:42

此代码将遍历树并添加所有匹配给定名称的节点。这是C＃3x，对于2.0，您需要使用匿名代理。

NTree<tTable> tree = new NTree<tTable>(table); 

string nameToMatch = "SomeName"; 
LinkedList<tTable> matches = new LinkedList<tTable>(); 

tree.Traverse(tree, data => { 
    if (data.Name == nameToMatch) { 
    matches.AddLast(data); 
    } 
});

来源

2010-03-29 15:02:39

谢谢恩！这个箭头业务是lambda表达式，对吧？我尝试使用匿名代理。如果满足一些条件，我也可以创建另一个方法TraverseInterrupt来中断遍历。我认为在这种情况下，我必须考虑递归，并将一些标志放在该选项上，并在foreach循环之前返回所有递归级别。 – 2010-03-31 12:09:18

是的，如果您希望在找到特定节点时终止此操作，请将返回值添加到TreeVisitor委托中，以便在返回适当的值时停止递归。 – 2010-03-31 19:18:29

要获取用树木在列表或哈希表的任何好处，也必须到位执政规律哪些节点是父节点的孩子，而不是其他的父母，并可能在其兄弟姐妹发生的顺序。例如一个二叉搜索树确保留下的孩子比当前节点少，比当前节点右孩子大。此规则允许二叉搜索树获得O（log n）个搜索时间。同样，一个堆保证根大于它的孩子，这使得它具有出色的排序性能（最坏情况O（n log n））。

您的问题未被充分指定为授予使用树而不是其他数据结构的好处。

来源

2010-03-29 14:40:32

它看起来像这棵树没有用于性能的原因;他使用它来建立项目之间的层次关系（如XML）。树是一个很好的结构。 – 2010-03-29 14:56:00

是的，但他想做一个不完整的遍历来找到符合某些标准的一组节点。这棵树没有特殊的内部结构，所以找到这些节点的唯一方法就是做一个完整的遍历。 – 2010-03-29 15:06:06

虽然这是真的，但我想他比这个单遍历（至少我希望如此）对这棵树有更多的用途，在这种情况下树可能是有利的。 – 2010-03-29 15:20:55

如何在C＃中使用树型数据结构

回答

相关问题