it-swarm-ko.tech

C #의 트리 데이터 구조

C #에서 트리 또는 그래프 데이터 구조를 찾고 있었지만 제공되지 않았다고 생각합니다. C # 2.0을 사용하여 광범위한 데이터 구조 검토 이유에 대해 약간 설명합니다. 이 기능을 제공하기 위해 일반적으로 사용되는 편리한 라이브러리가 있습니까? 아마도 기사에서 제시된 문제를 해결하기위한 전략 패턴을 통해.

내 자신의 ArrayList를 구현하는 것처럼 내 자신의 트리를 약간 어리석게 구현한다고 느낍니다.

난 그냥 불균형 될 수있는 일반적인 나무 싶어요. 디렉토리 트리를 생각해보십시오. C5는 멋진 모양이지만 트리 구조는 노드 계층 구조를 나타내는 것보다 검색에 더 적합한 균형 잡힌 빨강 - 검정 나무로 구현되는 것 같습니다.

228
stimms

최선의 조언은 표준 트리 데이터 구조가 없다는 것입니다. 왜냐하면 하나의 솔루션으로 모든 기반을 포괄하는 것은 불가능하기 때문에 구현할 수있는 방법이 너무 많기 때문입니다. 해결책이 구체적 일수록 특정 문제에 적용될 가능성이 적습니다. 나는 LinkedList로 짜증이났다. 만약 내가 순환 연결된 목록을 원한다면?

구현해야 할 기본 구조는 노드 모음이며 여기서는 시작할 수있는 몇 가지 옵션이 있습니다. Node 클래스가 전체 솔루션의 기본 클래스라고 가정합시다.

트리를 탐색해야하는 경우 Node 클래스에는 하위 목록이 필요합니다.

트리를 탐색해야하는 경우 Node 클래스에는 상위 노드에 대한 링크가 필요합니다.

이 두 점의 모든 세부 점 및 구현해야하는 기타 비즈니스 논리 (자식 제한, 자식 정렬 등)를 처리하는 AddChild 메서드를 작성합니다.

141
David Boike

나는 그것을 인정하기 싫지만 링크드리스트를 사용하여 내 자신의 트리 클래스를 작성했다. 관련없는 메모에서 나는 방금 '액슬 (axle)'이라고 부르는 것에 붙여지면 상품 운송을 용이하게하는이 둥근 것을 발견했습니다.

194
stimms
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로 이름을 바꿀 필요가 있습니다.

112
Aaron Gage

내 의견은 Aaron Gage 's 와 매우 유사합니다. 내 목적을 위해, 나는 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()));
        }
    }
}
49
Ronnie Overby

또 다른 나무 구조 :

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

보너스
본격적인 나무보기 :

  • 반복자
  • 수색
  • Java/C #

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

40
Grzegorz Dev

일반적으로 우수한 C5 Generic Collection Library 에는 세트, 가방 및 사전을 포함하여 여러 가지 트리 기반 데이터 구조가 있습니다. 소스 코드는 구현 세부 사항을 연구하려는 경우 사용할 수 있습니다. (특별히 나무 구조를 사용하지는 않았지만 C5 모음을 프로덕션 코드로 사용하여 좋은 결과를 얻었습니다.)

22
McKenzieG1

참조 http://quickgraph.codeplex.com/

QuickGraph는 .Net 2.0 이상을위한 일반 지향성/무향 그래프 데이터 구조 및 알고리즘을 제공합니다. QuickGraph는 깊이 첫 번째 검색, 호흡 첫 검색, A * 검색, 최단 경로, k 최단 경로, 최대 흐름, 최소 스패닝 트리, 최소 공통 조상 등과 같은 알고리즘을 제공합니다. QuickGraph는 MSAGL, GLEE 및 Graphviz를 지원합니다. 그래프 렌더링, GraphML 직렬화 등.

10
nietras

직접 작성할 계획이라면 C # 2.0 데이터 구조의 효과적인 사용법과 C #의 데이터 구조 구현 분석 방법에 대해 자세히 설명하는 6 부로 구성된이 문서에서부터 시작할 수 있습니다. 각 기사에는 예제와 함께 따라 할 수있는 샘플이 들어 있습니다.

"C # 2.0을 사용한 광범위한 데이터 구조 검토" Scott Mitchell

7
user7116

솔루션에 약간의 확장이 있습니다.

재귀 일반 선언 및 유도 하위 클래스를 사용하면 실제 대상에 더 잘 집중할 수 있습니다.

공지 사항, 일반 구현과 다른 점은 '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);  
}  
6
Erik Nagel

이 간단한 샘플을 사용해보십시오.

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
}
4
Berezh

다른 사람들에게 도움이 될 수있는 노드 클래스 를 만듭니다. 클래스에는 다음과 같은 속성이 있습니다.

  • 어린이
  • 조상
  • 자손
  • 동기
  • 노드 레벨
  • 부모의
  • Root
  • 기타.

또한 Id 및 ParentId가있는 항목의 플랫 목록을 트리로 변환 할 수 있습니다. 노드는 자식 노드와 부모 노드 모두에 대한 참조를 보유하므로 반복 노드가 매우 빠릅니다.

2
Alex Siepman

왜냐하면 그것은 언급하지 않았기 때문에 나는 지금 당신이주의를 끌기 바란다. 닷넷 코드 -베이스 : 구체적으로 Red-Black-Tree를 구현하는 SortedSet을위한 코드 :

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

그러나 이것은 균형 잡힌 나무 구조입니다. 따라서 제 대답은 .net 핵심 라이브러리의 유일한 기본 트리 구조라고 생각하는 것에 대한 참조입니다.

2
Meirion Hughes

여기에 나무가있다.

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"
        }
    };
2
Visar

여기 내 자신의 :

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
2
moien

@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;
        }
    }
2
Ashkan Sirous

대부분의 나무는 처리중인 데이터로 구성됩니다.

누군가의 person에 대한 세부 정보를 포함하는 parents 클래스가 있다고 가정 해 봅시다. "도메인 클래스"의 일부로 트리 구조를 사용하거나, 개인 객체에 대한 링크가 포함 된 별도의 트리 클래스를 사용 하시겠습니까? 이 코드가 grandchildren 클래스에 있어야하거나 person 클래스의 사용자가 별도의 트리 클래스에 대해 알고 있어야하는 것과 같이 personperson을 모두 얻는 것과 같은 간단한 작업을 생각해보십시오.

또 다른 예는 컴파일러의 구문 분석 트리입니다.

이 두 예제가 보여주는 것은 트리의 개념이 데이터의 도메인의 일부이고 별도의 범용 트리를 사용하여 생성되는 객체의 수를 두 배 이상 늘리고 API를 다시 프로그래밍하기가 어렵습니다.

우리가 원했던 것은 표준 트리 작업을 재사용 할 수있는 방법입니다. 표준 트리 작업을 재사용 할 필요없이 모든 트리에 대해 다시 구현할 수 있습니다. 동시에 표준 트리 클래스를 사용할 필요가 없습니다. Boost는 이러한 유형의 C++ 문제를 해결하려고 노력했지만 .NET에 대한 영향을 아직 보지 못했습니다.

1
Ian Ringrose

위의 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);
1
Dmitry

이 트리를 GUI에 표시하려면 TreeViewTreeNode 를 사용할 수 있습니다. (기술적으로 GUI에 배치하지 않고 TreeNode를 생성 할 수 있다고 가정하지만 간단한 자체 개발 TreeNode 구현보다 많은 오버 헤드가 발생합니다.)

0
Denise Skidmore