C#의 트리 데이터 구조
https://stackoverflow.com/questions/66893
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
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줄 미만의 코드...수업 외부의 나무의 근본에 대한 참조를 유지하거나 다른 클래스로 랩핑하면 Treenode로 이름을 바꿀 수 있습니까?
여기 내 것이 있습니다. 이것은 다음과 매우 유사합니다. 아론 게이지의, 제 생각에는 조금 더 관습적입니다.내 목적에 따라 성능 문제가 발생하지 않았습니다. 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 일반 컬렉션 라이브러리 세트, 백, 사전을 포함한 여러 가지 트리 기반 데이터 구조를 가지고 있습니다.구현 세부 사항을 연구하려면 소스 코드를 사용할 수 있습니다.(트리 구조를 구체적으로 사용하지는 않았지만 프로덕션 코드에서 C5 컬렉션을 사용하여 좋은 결과를 얻었습니다.)
보다 http://quickgraph.codeplex.com/
QuickGraph는 .Net 2.0 이상에 대한 일반적인 방향성/비방향성 그래프 데이터 구조 및 알고리즘을 제공합니다.QuickGraph에는 깊이 우선 검색, 호흡 우선 검색, A* 검색, 최단 경로, k-최단 경로, 최대 흐름, 최소 스패닝 트리, 최소 공통 조상 등과 같은 알고리즘이 제공됩니다.QuickGraph는 그래프 렌더링, GraphML 직렬화 등을 위해 MSAGL, GLEE 및 Graphviz를 지원합니다.
직접 작성하고 싶다면 C# 2.0 데이터 구조의 효과적인 사용법과 C#에서 데이터 구조 구현을 분석하는 방법을 자세히 설명하는 6부분으로 구성된 이 문서부터 시작해 보세요.각 문서에는 예제와 함께 따라할 수 있는 샘플이 포함된 설치 프로그램이 있습니다.
솔루션에 대한 약간의 확장이 있습니다.
재귀적 일반 선언과 파생 하위 클래스를 사용하면 실제 대상에 더 집중할 수 있습니다.
이는 일반 구현이 아닌 것과 다르기 때문에 '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
}
나는 노드 클래스 그것은 다른 사람들에게 도움이 될 수 있습니다.클래스에는 다음과 같은 속성이 있습니다.
- 어린이들
- 선조
- 자손
- 형제
- 노드의 레벨
- 부모의
- 뿌리
- 등.
Id 및 ParentId가 포함된 단순 항목 목록을 트리로 변환할 수도 있습니다.노드는 자식과 부모 모두에 대한 참조를 보유하므로 노드 반복이 매우 빨라집니다.
언급되지 않았기 때문에 현재 출시된 .net 코드 기반에 주목해 주시기 바랍니다.특히 SortedSet Red-Black-Tree를 구현하는 것:
그러나 이는 균형 잡힌 트리 구조입니다.따라서 내 대답은 .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;
}
}
여기 나무가 있습니다
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;
}
}
초기화 프로그램을 사용할 수도 있습니다:
var tree = new Tree<string>("root")
{
new Tree<string>("sample")
{
"console1"
}
};
내 자신은 다음과 같습니다.
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
대부분의 트리는 처리 중인 데이터에 의해 형성됩니다.
당신이 가지고 있다고 말해보세요
person누군가의 세부 정보를 포함하는 클래스parents, 오히려 트리 구조를“도메인 클래스”의 일부로 사용 하시겠습니까, 아니면 개인 개체에 대한 링크가 포함 된 별도의 트리 클래스를 사용 하시겠습니까?모든 것을 얻는 것과 같은 간단한 작업에 대해 생각하십시오grandchildren~의person, 이 코드가person클래스 또는 사용자가person클래스는 별도의 트리 클래스에 대해 알아야합니까?
또 다른 예는 컴파일러의 구문 분석 트리입니다.
이 두 가지 예가 보여주는 것은 트리의 개념이 다음의 일부라는 것입니다. 도메인 데이터를 줄이고 별도의 범용 트리를 사용하면 생성되는 개체 수가 두 배 이상 늘어나고 API를 다시 프로그래밍하기가 더 어려워집니다.
우리가 원하는 것은 모든 트리에 대해 다시 구현하지 않고도 표준 트리 작업을 재사용하는 동시에 표준 트리 클래스를 사용할 필요가 없는 방법입니다.Boost는 C++에 대해 이러한 유형의 문제를 해결하려고 시도했지만 아직 .NET에 대한 효과가 적용되는 것을 보지 못했습니다.
위의 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);
여기 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();
}
}
더 적은 메모리를 사용하는 루트 트리 데이터 구조 구현이 필요한 경우 다음과 같이 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
}
