파일에 일반 트리를 저장하려면 어떻게해야합니까?

Question

나는 모든 종류의 (등 INT, 플로트, 문자열)

template<class T> class Tree { 
public: 
// Class interface 
private: 
T node; 
std::list<Tree<T>*>* children; 
}; 

를 저장할 수있는 C++로 작성된 일반적인 트리 구현을하고 난 입력 소스 트리로 받아 프로그램 (C++로 작성된)이 (파일에 저장된) 규칙 집합을 기반으로 다른 트리를 출력 할 수 있습니다.

Any instance of class A become an instance of class X 
Any instance of class B become an instance of class Y 
Any instance of class C become an instance of class Z 

예를 들어, I는 (B (C))이 입력 트리 값이 가정 (노드 (A)는 아이로서 B를 갖고 B는 자식으로 C를 갖는다). 규칙의 파일을 기반으로 내 프로그램은이 트리 X (Y (Z))를 제공합니다. 내 질문은 : 어떻게 파일에 규칙 집합을 저장할 수 있습니까? 이 파일에 트리 유형을 저장하려면 어떻게해야합니까?

<translationUnit> 
    <from> 
    <A> 
     <B> 
     <C></C> 
     </B> 
    </A> 
    </from> 
    <to> 
    <X> 
     <Y> 
     <Z></Z> 
     </Y> 
    </X> 
    <to> 
</translationUnit> 

XML을 사용하여 규칙을 저장하려고하지만 클래스 유형을 어떻게 저장할 수 있습니까?

Answer 1

트리의 각 값에 대해 유형을 연결해야합니다. 따라서 트리의 각 요소는 값과 값의 유형 및 자식 목록의 쌍입니다. 파일에서 각 노드에 대해이 정보를 저장해야합니다.

당신은 json이 트리의 직렬화 된 버전을 저장한다고 생각할 수 있습니다. 읽기 쉽고 많은 좋은 C++ 라이브러리가 존재합니다. 예를 들어, 입력 나무가 될 것입니다 : 당신이 원하는 경우

[ 
    { from: "A", to: "X" }, 
    { from: "B", to: "Y" }, 
    { from: "C", to: "Z" } 
] 

: 각 유형 변환을 저장할 수

{ 
    type: "X", 
    value: "value of the first node, 
    children: [ 
     { 
      type: "Y" 
      value: "a value ...", 
      children: [ 
        { 
         type: "Z", 
         value: "a value ...", 
        } 
      ] 
     } 
    ] 
} 

및 구성 파일 :

이

{ 
    type: "A", 
    value: "value of the first node, 
    children: [ 
     { 
      type: "B" 
      value: "a value ...", 
      children: [ 
        { 
         type: "C", 
         value: "a value ...", 
        } 
      ] 
     } 
    ] 
} 

당신의 결과가 될 것입니다 A와 B가 기본 유형을 공유해야하고, 포인터를 사용하여 노드 구성원을 저장해야합니다. 당신이 관리하지 않는 경우 수동으로 unique_ptr 사용 : 당신이 나무에 대한 포인터의 목록에 대한 포인터를 가지고, 그 후

unique_ptr<T> node; 

을 당신이를 피하려면, 그것을 관리하는 포인터의 많은이야 포인터를 목록에 추가하면 불완전한 형식의 컨테이너를 허용하는 boost::container::list을 사용할 수 있습니다. 그런 다음 목록에 저장된 트리에 대한 포인터를 가질 필요가 없으며 Tree 값이 작업을 수행합니다.

boost::container::list<Tree<T> > children; 

Answer 2

노드 간의 관계에 대한 포인터를 사용하는 것 같습니다. 예 :

class node{ 
int value; 
node* first_child; 
node* next_sibling; 
}; 

포인터 대신 색인을 사용하여 직렬화 노드를 만들 수 있습니다. 다음과 같습니다.

class node2{ 
    int value; 
    int id_first_child; 
    int id_next_sibling; 
}; 

이제 트리를 플랫 할 수 있습니다. 그것을 배열로 바꾸는 것을 의미합니다.

모든 노드를 포인터에 벡터의 인덱스로 변환하는 데 사용되는 vector<node*> 및 map<node*,int>에 대한 포인터를 추가합니다.

은 이제 포인터 대신 색인을 사용하여 노드에 파일을 씁니다.

파일에서 읽을 때 반대 방향으로해야하고 색인을 포인터로 변환하십시오.