树数据结构 - 开卷题库

小开

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

小开

最佳答案

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

您需要实现的基本结构是一个节点集合，这里有一些选项可以帮助您入门。让我们假设类Node是整个解决方案的基类。

如果您只需要沿着树向下导航，那么Node类需要一个子类的List。

如果需要向上导航树，则Node类需要一个到其父节点的链接。

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

小开

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

简单的递归实现… & lt;40行代码… 你只需要在类外保留一个对树根的引用，或者在另一个类中包装它，也许重命名为TreeNode??< / p >

小开

参见https://github.com/YaccConstructor/QuickGraph(以前的http://quickgraph.codeplex.com/)

QuickGraph为。net 2.0及更高版本提供了通用的有向/无向图数据结构和算法。QuickGraph自带算法，如深度优先搜索，广度优先搜索, A*搜索，最短路径，k最短路径，最大流量，最小生成树，最小公共祖先等…QuickGraph支持MSAGL，《欢乐合唱团》和Graphviz来呈现图形，序列化到GraphML等。

小开

这是我的，它与亚伦计的非常相似，只是在我看来更传统一点。就我的目的而言，我使用List<T>没有遇到任何性能问题。如果需要，切换到LinkedList是很容易的。

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

小开

如果你需要一个使用较少内存的根树数据结构实现，你可以这样写你的Node类(c++实现):

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
}

小开

我对解做了一些扩展。

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

注意，它不同于非泛型实现，你不需要将'node'转换为'NodeWorker'。

以下是我的例子:

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

小开

试试这个简单的例子。

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
}

小开

我创建了一个Node< T>类，它可以对其他人有帮助。该类具有如下属性:

孩子们
的祖先
的后代
兄弟姐妹
节点级别
父
根
等。

还有一种可能是将一个带有Id和ParentId的项目平面列表转换为树。节点包含对子节点和父节点的引用，因此迭代节点非常快。

小开

还有另一种树结构:

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


... // for iterator details see below link
}

示例用法:

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

< p > 奖金 < br > 参见full -羽翼丰满的树:

迭代器
搜索
Java / c#

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

小开

下面是BST的实现:

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

小开

有现在发布的。net代码库:具体来说是实现了红黑树: sortedset.cs .cs的SortedSet代码

然而，这是一个平衡的树形结构。因此，我的答案更多的是参考。net核心库中唯一的原生树结构。

小开

如果你打算在GUI上显示这个树，你可以使用树状视图和TreeNode。(我认为从技术上讲，你可以创建一个TreeNode而不把它放在GUI上，但它确实比一个简单的自定义TreeNode实现有更多的开销。)

小开

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

假设你有一个person类，它包含某人的详细信息 parents，你宁愿有树结构作为你的一部分 “域类”，或者使用包含链接的单独树类你的人反对吗?考虑一个简单的操作，比如获取全部 person的grandchildren，如果此代码在person中类，或者person类的用户必须知道一个单独的树类?< / p >

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

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

我们想要一种重用标准树操作的方法，而不必为所有树重新实现它们，同时又不必使用标准树类。提高已经尝试为c++解决这类问题，但我还没有看到任何效果。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;
}
}

小开

我已经使用上面的NTree类添加了一个完整的解决方案和示例。我还添加了“addchild”;方法……

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

使用它

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

小开

这是我自己的想法:

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

输出:

Fastfood
Pizza
Margherita
Marinara
Burger
Cheese burger
Chili burger
Rice burger

小开

也有可能在LINQ中使用XML:

在c#中创建XML树(LINQ to XML)

当谈到使用树时，XML是最成熟和灵活的解决方案，LINQ为您提供了所需的所有工具。您的树的配置也变得更加清晰和用户友好，因为您可以简单地使用XML文件进行初始化

如果你需要处理对象，你可以使用XML序列化:

XML序列化

小开

具有通用数据的树

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;


public class Tree<T>
{
public T Data { get; set; }
public LinkedList<Tree<T>> Children { get; set; } = new LinkedList<Tree<T>>();
public Task Traverse(Func<T, Task> actionOnNode, int maxDegreeOfParallelism = 1) => Traverse(actionOnNode, new SemaphoreSlim(maxDegreeOfParallelism, maxDegreeOfParallelism));
private async Task Traverse(Func<T, Task> actionOnNode, SemaphoreSlim semaphore)
{
await actionOnNode(Data);
SafeRelease(semaphore);
IEnumerable<Task> tasks = Children.Select(async input =>
{
await semaphore.WaitAsync().ConfigureAwait(false);
try
{
await input.Traverse(actionOnNode, semaphore).ConfigureAwait(false);
}
finally
{
SafeRelease(semaphore);
}
});
await Task.WhenAll(tasks);
}
private void SafeRelease(SemaphoreSlim semaphore)
{
try
{
semaphore.Release();
}
catch (Exception ex)
{
if (ex.Message.ToLower() != "Adding the specified count to the semaphore would cause it to exceed its maximum count.".ToLower())
{
throw;
}
}
}


public async Task<IEnumerable<T>> ToList()
{
ConcurrentBag<T> lst = new ConcurrentBag<T>();
await Traverse(async (data) => lst.Add(data));
return lst;
}
public async Task<int> Count() => (await ToList()).Count();
}

单元测试

using System.Threading.Tasks;
using Xunit;


public class Tree_Tests
{
[Fact]
public async Task Tree_ToList_Count()
{
Tree<int> head = new Tree<int>();


Assert.NotEmpty(await head.ToList());
Assert.True(await head.Count() == 1);


// child
var child = new Tree<int>();
head.Children.AddFirst(child);
Assert.True(await head.Count() == 2);
Assert.NotEmpty(await head.ToList());


// grandson
child.Children.AddFirst(new Tree<int>());
child.Children.AddFirst(new Tree<int>());
Assert.True(await head.Count() == 4);
Assert.NotEmpty(await head.ToList());
}


[Fact]
public async Task Tree_Traverse()
{
Tree<int> head = new Tree<int>() { Data = 1 };


// child
var child = new Tree<int>() { Data = 2 };
head.Children.AddFirst(child);


// grandson
child.Children.AddFirst(new Tree<int>() { Data = 3 });
child.Children.AddLast(new Tree<int>() { Data = 4 });


int counter = 0;
await head.Traverse(async (data) => counter += data);
Assert.True(counter == 10);


counter = 0;
await child.Traverse(async (data) => counter += data);
Assert.True(counter == 9);


counter = 0;
await child.Children.First!.Value.Traverse(async (data) => counter += data);
Assert.True(counter == 3);


counter = 0;
await child.Children.Last!.Value.Traverse(async (data) => counter += data);
Assert.True(counter == 4);
}
}

小开

我不喜欢树的方法。它使事情变得过于复杂，包括搜索或下钻，甚至ui控件填充。

我建议对IDictionary<TChild, TParent>使用一个非常简单的方法。这也允许节点或级别之间没有连接。