C＃中的树数据结构

Tree data structure in C#

我在C中寻找一个树或图形数据结构，但我想没有提供。使用C 2.0对数据结构进行的广泛检查解释了一点原因。是否有一个方便的库，通常用于提供此功能？也许通过一个策略模式来解决本文中提出的问题。

我觉得实现自己的树有点傻，就像实现自己的数组列表一样。

我只想要一个不平衡的通用树。想想目录树。c5看起来很漂亮，但它们的树结构似乎是作为平衡的红黑树实现的，这比表示节点的层次结构更适合于搜索。

我不想承认，但我最终还是用一个链接列表写了我自己的树类。在一张无关的便条上，我刚刚发现了这个圆形的东西，当它与我称之为"车轴"的东西相连时，可以方便地运输货物。

我最好的建议是，没有标准的树数据结构，因为有太多的方法可以实现它，以至于不可能用一个解决方案覆盖所有的基础。解决方案越具体，就越不可能适用于任何给定的问题。我甚至对LinkedList感到恼火-如果我想要一个循环链接列表呢？

您需要实现的基本结构是一组节点，下面是一些让您开始的选项。假设类节点是整个解决方案的基类。

如果只需要沿着树向下导航，那么节点类需要一个子类列表。

如果需要在树上导航，那么node类需要一个到其父节点的链接。

构建一个addchild方法来处理这两点的所有细节，以及必须实现的任何其他业务逻辑(子限制、对子项排序等)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

delegate void TreeVisitor<T>(T nodeData);

class NTree<T>
{
private T data;
private LinkedList<NTree<T>> children;

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

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

public NTree<T> GetChild(int i)
{
foreach (NTree<T> n in children)
if (--i == 0)
return n;
return null;
}

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

简单递归实现…<40行代码…您只需要在类外保留对树根的引用，或者用另一个类包装它，或者重命名为treenode？？

这是我的，和Aaron Gage的很相似，在我看来有点传统。出于我的目的，我没有遇到任何与List有关的性能问题。如果需要，可以很容易地切换到LinkedList。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

namespace Overby.Collections
{
public class TreeNode<T>
{
private readonly T _value;
private readonly List<TreeNode<T>> _children = new List<TreeNode<T>>();

public TreeNode(T value)
{
_value = value;
}

public TreeNode<T> this[int i]
{
get { return _children[i]; }
}

public TreeNode<T> Parent { get; private set; }

public T Value { get { return _value; } }

public ReadOnlyCollection<TreeNode<T>> Children
{
get { return _children.AsReadOnly(); }
}

public TreeNode<T> AddChild(T value)
{
var node = new TreeNode<T>(value) {Parent = this};
_children.Add(node);
return node;
}

public TreeNode<T>[] AddChildren(params T[] values)
{
return values.Select(AddChild).ToArray();
}

public bool RemoveChild(TreeNode<T> node)
{
return _children.Remove(node);
}

public void Traverse(Action<T> action)
{
action(Value);
foreach (var child in _children)
child.Traverse(action);
}

public IEnumerable<T> Flatten()
{
return new[] {Value}.Concat(_children.SelectMany(x => x.Flatten()));
}
}
}

还有另一种树结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

样品使用情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

TreeNode<string> root = new TreeNode<string>("root");
{
TreeNode<string> node0 = root.AddChild("node0");
TreeNode<string> node1 = root.AddChild("node1");
TreeNode<string> node2 = root.AddChild("node2");
{
TreeNode<string> node20 = node2.AddChild(null);
TreeNode<string> node21 = node2.AddChild("node21");
{
TreeNode<string> node210 = node21.AddChild("node210");
TreeNode<string> node211 = node21.AddChild("node211");
}
}
TreeNode<string> node3 = root.AddChild("node3");
{
TreeNode<string> node30 = node3.AddChild("node30");
}
}

奖金见完全羽化的树：

迭代器
搜索
爪哇/ C

https://github.com/gt4dev/yet-another-tree-structure

通常优秀的c5通用收集库具有几种不同的基于树的数据结构，包括集合、包和字典。如果您想研究它们的实现细节，可以使用源代码。(我在生产代码中使用了c5集合，结果很好，尽管我没有特别使用任何树结构。)

请访问http://quickgraph.codeplex.com/

Quickgraph为.NET 2.0及更高版本提供通用的有向/无向图形数据结构和算法。Quickgraph提供了诸如深度优先搜索、呼吸优先搜索、A*搜索、最短路径、K-最短路径、最大流、最小生成树、最小公共祖先等算法。Quickgraph支持msagl、glee和graphviz来呈现图形、对graphml进行序列化等。

如果您想自己写，可以从这六部分文档开始，详细介绍C 2.0数据结构的有效使用以及如何分析C中数据结构的实现。每一篇文章都有示例和一个安装程序，其中包含您可以随附的示例。

Scott Mitchell的"使用C 2.0对数据结构的广泛检查"

我对解决方案有一点扩展。

使用递归泛型声明和派生子类，您可以更好地集中于实际目标。

注意，它不同于非泛型实现，您不需要在"nodeWorker"中强制转换"node"。

下面是我的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

public class GenericTree<T> where T : GenericTree<T> // recursive constraint
{
// no specific data declaration

protected List<T> children;

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

public virtual void AddChild(T newChild)
{
this.children.Add(newChild);
}

public void Traverse(Action<int, T> visitor)
{
this.traverse(0, visitor);
}

protected virtual void traverse(int depth, Action<int, T> visitor)
{
visitor(depth, (T)this);
foreach (T child in this.children)
child.traverse(depth + 1, visitor);
}
}

public class GenericTreeNext : GenericTree<GenericTreeNext> // concrete derivation
{
public string Name {get; set;} // user-data example

public GenericTreeNext(string name)
{
this.Name = name;
}
}

static void Main(string[] args)
{
GenericTreeNext tree = new GenericTreeNext("Main-Harry");
tree.AddChild(new GenericTreeNext("Main-Sub-Willy"));
GenericTreeNext inter = new GenericTreeNext("Main-Inter-Willy");
inter.AddChild(new GenericTreeNext("Inter-Sub-Tom"));
inter.AddChild(new GenericTreeNext("Inter-Sub-Magda"));
tree.AddChild(inter);
tree.AddChild(new GenericTreeNext("Main-Sub-Chantal"));
tree.Traverse(NodeWorker);
}

static void NodeWorker(int depth, GenericTreeNext node)
{ // a little one-line string-concatenation (n-times)
Console.WriteLine("{0}{1}: {2}", String.Join(" ", new string[depth + 1]), depth, node.Name);
}

试试这个简单的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class TreeNode<TValue>
{
#region Properties
public TValue Value { get; set; }
public List<TreeNode<TValue>> Children { get; private set; }
public bool HasChild { get { return Children.Any(); } }
#endregion
#region Constructor
public TreeNode()
{
this.Children = new List<TreeNode<TValue>>();
}
public TreeNode(TValue value)
: this()
{
this.Value = value;
}
#endregion
#region Methods
public void AddChild(TreeNode<TValue> treeNode)
{
Children.Add(treeNode);
}
public void AddChild(TValue value)
{
var treeNode = new TreeNode<TValue>(value);
AddChild(treeNode);
}
#endregion
}

这是我自己的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

class Program
{
static void Main(string[] args)
{
var tree = new Tree<string>()
.Begin("Fastfood")
.Begin("Pizza")
.Add("Margherita")
.Add("Marinara")
.End()
.Begin("Burger")
.Add("Cheese burger")
.Add("Chili burger")
.Add("Rice burger")
.End()
.End();

tree.Nodes.ForEach(p => PrintNode(p, 0));
Console.ReadKey();
}

static void PrintNode<T>(TreeNode<T> node, int level)
{
Console.WriteLine("{0}{1}", new string(' ', level * 3), node.Value);
level++;
node.Children.ForEach(p => PrintNode(p, level));
}
}

public class Tree<T>
{
private Stack<TreeNode<T>> m_Stack = new Stack<TreeNode<T>>();

public List<TreeNode<T>> Nodes { get; } = new List<TreeNode<T>>();

public Tree<T> Begin(T val)
{
if (m_Stack.Count == 0)
{
var node = new TreeNode<T>(val, null);
Nodes.Add(node);
m_Stack.Push(node);
}
else
{
var node = m_Stack.Peek().Add(val);
m_Stack.Push(node);
}

return this;
}

public Tree<T> Add(T val)
{
m_Stack.Peek().Add(val);
return this;
}

public Tree<T> End()
{
m_Stack.Pop();
return this;
}
}

public class TreeNode<T>
{
public T Value { get; }
public TreeNode<T> Parent { get; }
public List<TreeNode<T>> Children { get; }

public TreeNode(T val, TreeNode<T> parent)
{
Value = val;
Parent = parent;
Children = new List<TreeNode<T>>();
}

public TreeNode<T> Add(T val)
{
var node = new TreeNode<T>(val, this);
Children.Add(node);
return node;
}
}

输出：

1
2
3
4
5
6
7
8

Fastfood
Pizza
Margherita
Marinara
Burger
Cheese burger
Chili burger
Rice burger

因为没有提到这一点，我希望您注意一下现在发布的.NET代码库：特别是实现红黑树的SortedSet的代码：

https://github.com/microsoft/referencesource/blob/master/system/compmod/system/collections/generic/sortedset.cs

然而，这是一个平衡的树结构。所以我的答案更多的是引用我认为是.NET核心库中唯一的本地树结构。

我已经完成了@berezh共享的代码。

public class TreeNode<T> : IEnumerable<TreeNode<T>>
{

public T Data { get; set; }
public TreeNode<T> Parent { get; set; }
public ICollection<TreeNode<T>> Children { get; set; }

public TreeNode(T data)
{
this.Data = data;
this.Children = new LinkedList<TreeNode<T>>();
}

public TreeNode<T> AddChild(T child)
{
TreeNode<T> childNode = new TreeNode<T>(child) { Parent = this };
this.Children.Add(childNode);
return childNode;
}

public IEnumerator<TreeNode<T>> GetEnumerator()
{
throw new NotImplementedException();
}

IEnumerator IEnumerable.GetEnumerator()
{
return (IEnumerator)GetEnumerator();
}
}
public class TreeNodeEnum<T> : IEnumerator<TreeNode<T>>
{

int position = -1;
public List<TreeNode<T>> Nodes { get; set; }

public TreeNode<T> Current
{
get
{
try
{
return Nodes[position];
}
catch (IndexOutOfRangeException)
{
throw new InvalidOperationException();
}
}
}

object IEnumerator.Current
{
get
{
return Current;
}
}

public TreeNodeEnum(List<TreeNode<T>> nodes)
{
Nodes = nodes;
}

public void Dispose()
{
}

public bool MoveNext()
{
position++;
return (position < Nodes.Count);
}

public void Reset()
{
position = -1;
}
}

这是一棵树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class Tree<T> : List<Tree<T>>
{
public T Data { get; private set; }

public Tree(T data)
{
this.Data = data;
}

public Tree<T> Add(T data)
{
var node = new Tree<T>(data);
this.Add(node);
return node;
}
}

甚至可以使用初始值设定项：

1
2
3
4
5
6
7

var tree = new Tree<string>("root")
{
new Tree<string>("sample")
{
"console1"
}
};

我创建了一个节点类，可以为其他人提供帮助。类具有如下属性：

儿童
祖先
后裔
兄弟姐妹
节点的级别
起源
根
等。

还可以将具有ID和parentID的项目的简单列表转换为树。节点同时包含对子节点和父节点的引用，因此使节点的迭代速度相当快。

大多数树是由正在处理的数据形成的。

Say you have a person class that includes details of someone’s
parents, would you rather have the tree structure as part of your
"domain class", or use a separate tree class that contained links to
your person objects? Think about a simple operation like getting all
the grandchildren of a person, should this code be in the person
class, or should the user of the person class have to know about a
separate tree class?

另一个例子是编译器中的解析树…

这两个例子都表明树的概念是数据域的一部分，使用一个单独的通用树至少使创建的对象数量增加一倍，并且使API更难再次编程。

我们需要的是一种重用标准树操作的方法，而不必为所有树重新实现它们，同时也不必使用标准树类。Boost已经尝试解决C++的这类问题，但是我还没有看到.Net GET适应的任何效果。

我在上面使用ntree类添加了完整的解决方案和示例，还添加了"addchild"方法…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

public class NTree<T>
{
public T data;
public LinkedList<NTree<T>> children;

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

public void AddChild(T data)
{
var node = new NTree<T>(data) { Parent = this };
children.AddFirst(node);
}

public NTree<T> Parent { get; private set; }

public NTree<T> GetChild(int i)
{
foreach (NTree<T> n in children)
if (--i == 0)
return n;
return null;
}

public void Traverse(NTree<T> node, TreeVisitor<T> visitor, string t, ref NTree<T> r)
{
visitor(node.data, node, t, ref r);
foreach (NTree<T> kid in node.children)
Traverse(kid, visitor, t, ref r);
}
}
public static void DelegateMethod(KeyValuePair<string, string> data, NTree<KeyValuePair<string, string>> node, string t, ref NTree<KeyValuePair<string, string>> r)
{
string a = string.Empty;
if (node.data.Key == t)
{
r = node;
return;
}
}

使用

1 2	NTree<KeyValuePair<string, string>> ret = null; tree.Traverse(tree, DelegateMethod, node["categoryId"].InnerText, ref ret);

如果要在GUI上显示此树，可以使用TreeView和TreeNode。(我认为从技术上讲，您可以创建一个TreeNode，而不必将它放在GUI上，但它确实比一个简单的国产TreeNode实现有更多的开销。)

这是我对BST的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

class BST
{
public class Node
{
public Node Left { get; set; }
public object Data { get; set; }
public Node Right { get; set; }

public Node()
{
Data = null;
}

public Node(int Data)
{
this.Data = (object)Data;
}

public void Insert(int Data)
{
if (this.Data == null)
{
this.Data = (object)Data;
return;
}
if (Data > (int)this.Data)
{
if (this.Right == null)
{
this.Right = new Node(Data);
}
else
{
this.Right.Insert(Data);
}
}
if (Data <= (int)this.Data)
{
if (this.Left == null)
{
this.Left = new Node(Data);
}
else
{
this.Left.Insert(Data);
}
}
}

public void TraverseInOrder()
{
if(this.Left != null)
this.Left.TraverseInOrder();
Console.Write("{0}", this.Data);
if (this.Right != null)
this.Right.TraverseInOrder();
}
}

public Node Root { get; set; }
public BST()
{
Root = new Node();
}
}

如果您需要使用较少内存的根树数据结构实现，您可以按如下方式编写节点类(C++实现)：

1
2
3
4
5
6
7

class Node {
Node* parent;
int item; // depending on your needs

Node* firstChild; //pointer to left most child of node
Node* nextSibling; //pointer to the sibling to the right
}