2009-11-20 3 views
1

을 사용하여 진정한 일반적인 트리를 코딩하는 방법 :다음과 같이 내가 노드 클래스가 있다고 가정하자 제네릭

class Node<T> 
    { 
     T data; 
     List<Node<T>> children; 
     internal Node(T data) 
     { 
      this.data = data; 
     } 

     List<Node<T>> Children 
     { 
      get 
      { 
       if (children == null) 
        children = new List<Node<T>>(1); 

       return children; 
      } 
     } 

     internal IEnumerable<Node<T>> GetChildren() 
     { 
      return children; 
     } 

     internal bool HasChildren 
     { 
      get 
      { 
       return children != null; 
      } 
     } 

     internal T Data 
     { 
      get 
      { 
       return data; 
      } 
     } 



     internal void AddChild(Node<T> child) 
     { 
      this.Children.Add(child); 
     } 

     internal void AddChild(T child) 
     { 
      this.Children.Add(new Node<T>(child)); 
     } 

    } 

문제는 트리의 각각의 모든 노드가 단일 유형에 국한된다는 점이다. 그러나 루트 노드가 세 번째 유형의 자식 (예 : 문서 -> 단락 -> 줄 -> 단어)이있는 다른 유형의 하위가있는 한 유형의 상황이 있습니다.

그런 경우 어떻게 일반 트리를 정의합니까? 이 유형의 엄격한 계층 구조를 원하는 경우

+0

데이터 개체간에 공통점이 있습니까? 동일한 인터페이스 또는 기본 유형을 공유합니까? – Elisha

+0

아니요. 그러나 일반적으로 위의 문서 -> 예와 같이 논리적으로 연결됩니다. – logicnp

+0

인터페이스를 공유하지 않으면 노드 보다 나은 것을 얻지 못할 것이라고 생각합니다. 그렇지 않으면 GraemeF로 가십시오. 나는 에릭의 대답을 살펴보고 트리를 왜 사용하고 있는지 다시 생각해 보겠다. 아마 더 좋은 구조가있을 것입니다. –

답변

7

당신은 다음과 같이 선언 할 수있다 :

class Node<T, TChild> {...} 

Node<Document, Node<Paragraph, Node<Line, Word>>> 

나는 그것이 꽤 될 것이다 주장하지 않았다. :)

+0

이것은 내가 얻을 수있는 가장 가까운 것 같습니다. 그러나 컴파일 시간에 계층 구조를 수정해야합니다. 그리고 더 깊은 계급을 위해 아직도 추악 할 것입니다. – logicnp

0

는 하위 개체의 모든 특정 예를 들어 IDocumentPart 다음 선언 노드는 이러한 경우에 대한 일반적인 트리를 정의하려면 어떻게

+0

하지만 정말 일반적인 트리가 아닐 것입니다. 예를 들어, 목록 은 'T'가 특정 인터페이스를 구현할 것을 요구하지 않습니다. 'T'를 선택하고 'T'의 목록을 만들 수 있습니다. – logicnp

+0

귀하의 의견에 따라 노드 을 원할 수도 있습니다. –

8

을 구현 적이 있습니까?

처음에는 시도하지 않겠습니다. 내가 모델 원한 경우였다

  • 나는 문서 단락이

왜 당신을 단어의 목록을 가지고

  • 단락의 목록이
  • 문서의 목록을 가지고 일반 노드가 필요합니까? 문단이 List<Word> 인 문단을 만들고 List<Paragraph>이있는 Document 클래스를 만든 다음 List<Document>을 작성하면 완료됩니다. 인위적으로 일반 트리 구조를 적용해야하는 이유는 무엇입니까? 그게 당신에게 어떤 이점이 있습니까?

  • 0

    나는 추측 할 수있는 코드를 게시하는 측면에서 StackOverFlow의 "규범"에 대해 강한 감각을 가지고 있지 않다고 생각하여 첨부 된 코드 예제를 제공하기를 꺼 렸습니다. 이 특별한 장난은 "Moreau 박사의 섬"이라는 실험실에서 탈출 한 "돌연변이 종"의 일부 형태입니다. :) 그리고 나는 에릭 리 퍼트 (Eric Lippert)의 답변이 옳다고 생각합니다.

    .NET 상속 ("프레임 워크 3.5"기능 사용)을 "프로빙"하는 실험에서 "소금 곡식"을 다음과 같이 사용하십시오. 이 글을 쓰면서 저의 목표 (몇 달 전)는 "자체"라는 내부 목록 <>을 구현 한 노드 구조에 대한 추상 클래스 기반을 실험 한 다음 추상 클래스에서 상속 한 강력한 유형의 클래스를 구현하는 것이 었습니다. , 그 기초 위에서, 일반화 된 Tree 데이터 구조를 구축합니다.

    실제로 테스트 한 결과 놀랍습니다.:)

    using System; 
    using System.Collections.Generic; 
    using System.Linq; 
    using System.Text; 
    
    // experimental code : tested to a limited extent 
    // use only for educational purposes 
    
    namespace complexTree 
    { 
        // foundation abstract class template 
        public abstract class idioNode 
        { 
         // a collection of "itself" ! 
         public List<idioNode> Nodes { private set; get; } 
    
         public idioNode Parent { get; set; } 
    
         public idioNode() 
         { 
          Nodes = new List<idioNode>(); 
         } 
    
         public void Add(idioNode theNode) 
         { 
          Nodes.Add(theNode); 
          theNode.Parent = this; 
         } 
        } 
    
        // strongly typed Node of type String 
        public class idioString : idioNode 
        { 
         public string Value { get; set; } 
    
         public idioString(string strValue) 
         { 
          Value = strValue; 
         } 
        } 
    
        // strongly typed Node of type Int 
        public class idioInt : idioNode 
        { 
         public int Value { get; set; } 
    
         public idioInt(int intValue) 
         { 
          Value = intValue; 
         } 
        } 
    
        // strongly type Node of a complex type 
        // note : this is just a "made-up" test case 
        // designed to "stress" this experiment 
        // it certainly doesn't model any "real world" 
        // use case 
        public class idioComplex : idioNode 
        { 
         public Dictionary<idioString, idioInt> Value { get; set; } 
    
         public idioComplex(idioInt theInt, idioString theString) 
         { 
          Value = new Dictionary<idioString, idioInt>(); 
          Value.Add(theString, theInt); 
         } 
    
         public void Add(idioInt theInt, idioString theString) 
         { 
          Value.Add(theString, theInt); 
          theInt.Parent = this; 
          theString.Parent = this; 
         } 
        } 
    
        // special case the Tree's root nodes 
        // no particular reason for doing this 
        public class idioTreeRootNodes : List<idioNode> 
        { 
         public new void Add(idioNode theNode) 
         { 
          base.Add(theNode); 
          theNode.Parent = null; 
         } 
        } 
    
        // the Tree object 
        public class idioTree 
        { 
         public idioTreeRootNodes Nodes { get; set; } 
    
         public idioTree() 
         { 
          Nodes = new idioTreeRootNodes(); 
         } 
        } 
    } 
    

    그래서 시험 (A의 WinForm에 대한 몇 가지 이벤트 핸들러에서이 코드를 호출) :

    // make a new idioTree 
        idioTree testIdioTree = new idioTree(); 
    
        // make a new idioNode of type String 
        idioString testIdioString = new idioString("a string"); 
    
        // add the Node to the Tree 
        testIdioTree.Nodes.Add(testIdioString); 
    
        // make a new idioNode of type Int 
        idioInt testIdioInt = new idioInt(99); 
    
        // add to Tree 
        testIdioTree.Nodes.Add(testIdioInt); 
    
        // make another idioNode of type String 
        idioString testIdioString2 = new idioString("another string"); 
    
        // add the new Node to the child Node collection of the Int type Node 
        testIdioInt.Nodes.Add(testIdioString2); 
    
        // validate inheritance can be verified at run-time 
        if (testIdioInt.Nodes[0] is idioString) MessageBox.Show("it's a string, idiot"); 
    
        if (!(testIdioInt.Nodes[0] is idioInt)) MessageBox.Show("it's not an int, idiot"); 
    
        // make a new "complex" idioNode 
        // creating a Key<>Value pair of the required types of idioNodes 
        idioComplex complexIdio = new idioComplex(new idioInt(88), new idioString("weirder")); 
    
        // add a child Node to the complex idioNode 
        complexIdio.Add(new idioInt(77), new idioString("too weird")); 
    
        // make another idioNode of type Int 
        idioInt idioInt2 = new idioInt(33); 
    
        // add the complex idioNode to the child Node collection of the new Int type idioNode 
        idioInt2.Nodes.Add(complexIdio); 
    
        // add the new Int type Node to the Tree 
        testIdioTree.Nodes.Add(idioInt2); 
    
        // validate you can verify the type of idioComplex at run-time 
        MessageBox.Show(" tree/2/0 is complex = " + (testIdioTree.Nodes[2].Nodes[0] is idioComplex).ToString()); 
    

    을이 코드의 "냄새"가 여기에 과일만큼 나쁘지 경우 태국에서 우리는 "두리안"이라고 부릅니다. 글쎄, 그렇게 되겠지 :)이 실험에서 분명히 가능한 "이상한"것은 한 번에 두 개 이상의 노드에서 동일한 노드에 참조를 가질 수 있다는 것입니다. 동시에.

    관련 문제