C #에서 트리 또는 그래프 데이터 구조를 찾고 있었지만 제공되지 않은 것 같습니다. C # 2.0을 사용한 광범위한 데이터 구조 조사에서는 그 이유에 대해 설명합니다. 이 기능을 제공하기 위해 일반적으로 사용되는 편리한 라이브러리가 있습니까? 아마도 기사에 제시된 문제를 해결하기위한 전략 패턴을 통해서 일 것입니다.
내 ArrayList를 구현하는 것처럼 내 자신의 트리를 구현하는 것이 바보 같은 느낌이 듭니다.
균형이 맞지 않는 일반 트리를 원합니다. 디렉토리 트리를 생각하십시오. C5는 근사해 보이지만 트리 구조는 노드 계층 구조를 나타내는 것보다 검색에 더 적합한 균형 잡힌 빨강-검정 트리로 구현 된 것 같습니다.
답변
최선의 조언은 표준 트리 데이터 구조가 없다는 것입니다. 구현할 수있는 방법이 너무 많아서 모든 기반을 하나의 솔루션으로 처리하는 것은 불가능합니다. 솔루션이 구체적 일수록 주어진 문제에 적용 할 가능성이 줄어 듭니다. 심지어 LinkedList에 짜증이납니다. 순환 링크 목록을 원한다면 어떻게해야합니까?
구현해야 할 기본 구조는 노드 모음이며 시작하기위한 몇 가지 옵션이 있습니다. 클래스 Node가 전체 솔루션의 기본 클래스라고 가정하십시오.
트리를 아래로만 탐색해야하는 경우 Node 클래스에는 하위 목록이 필요합니다.
트리를 탐색해야하는 경우 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);
}
}간단한 재귀 구현 … <40 줄의 코드 … 클래스 외부의 트리 루트에 대한 참조를 유지하거나 다른 클래스로 래핑해야합니다.
답변
여기 내 의견 으로는 Aaron Gage 와 매우 유사한 광산이 있습니다. 내 목적으로와 관련하여 성능 문제가 발생하지 않았습니다 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()));
}
}
}답변
또 다른 트리 구조 :
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");
}
}보너스
다음과 같은 본격적인 나무를보십시오.
- 반복자
- 수색
- 자바 / C #
답변
일반적으로 우수한 C5 Generic Collection Library 에는 세트, 백 및 사전을 포함하여 여러 가지 다른 트리 기반 데이터 구조가 있습니다. 구현 세부 사항을 연구하려는 경우 소스 코드를 사용할 수 있습니다. (트리 구조를 구체적으로 사용하지는 않았지만 프로덕션 코드에서 C5 컬렉션을 사용했지만 좋은 결과를 얻었습니다.)
답변
http://quickgraph.codeplex.com/을 참조하십시오
QuickGraph는 .Net 2.0 이상을위한 일반 지향 / 무 방향 그래프 데이터 구조 및 알고리즘을 제공합니다. QuickGraph는 깊이 우선 시치, 호흡 우선 검색, A * 검색, 최단 경로, k 최단 경로, 최대 흐름, 최소 스패닝 트리, 최소 공통 조상 등의 알고리즘을 제공합니다. QuickGraph는 MSAGL, GLEE 및 Graphviz를 지원합니다. 그래프 렌더링, GraphML 로의 직렬화 등 …
답변
직접 작성하려면 C # 2.0 데이터 구조의 효과적인 사용법과 C #에서 데이터 구조의 구현 분석 방법에 대해 자세히 설명하는이 6 부 문서로 시작할 수 있습니다. 각 기사에는 예제와 함께 따를 수있는 샘플이 포함 된 설치 프로그램이 있습니다.
Scott Mitchell의 “C # 2.0을 사용한 광범위한 데이터 구조 검사”
