C++에서 트리를 만드는 방법은 무엇입니까?

Question

포인터 대신 반복자를 사용하는 C++에서 트리 데이터 구조를 만들려면 어떻게해야합니까? 나는 이것을 할 수있는 STL에서 아무것도 찾을 수 없었다. 내가 뭘하고 싶은 것은이 같은 트리를 만들고 조작 할 수 있습니다 :

#include <iostream> 
#include <tree> 
using namespace std; 

int main() 
{ 
    tree<int> myTree; 

    tree<int>::iterator i = myTree.root(); 
    *i = 42; 

    tree<int>::iterator j = i.add_child(); 
    *j = 777; 
    j = j.parent(); 

    if (i == myTree.root() && i == j) cout << "i and j are both pointing to the root\n"; 

    return 0; 
} 

---

감사합니다, tree.hh는 내가 찾던 그냥 뭐 것 같다. 이 임의의 인덱스 유형을 들고 의 데이터 구조를 이익을 얻기위한 경우

, 다음지도를 이용하여 을 고려 검색을위한 최적화 삽입 좋은. 대수 검색, 대수 삽입, 삭제 대수 선형 공간 :

지도에는 는 트리 것과 동일한 성능 보장을 갖고 연관 컨테이너이다. 내부적으로 그들은 종종 이 아니지만 적색 - 검은 색 나무로 으로 구현됩니다. STL 사용자가 인 경우 STL 알고리즘 및 데이터 구조에 대한 성능 보증은 입니다. 그들이 나무로 구현되었는지 여부는 이거나 작은 녹색 남성은 과 관련이 없습니다.

지도가 필요한지 잘 모르겠지만 정보를 제공해 주셔서 감사합니다. 나무를 구현하는 대신 가능할 때마다지도를 사용하는 것을 기억합니다.

Answer 1

여기는 과는 조금 다르긴하지만 조금 더 가까이에있는 tree.hh입니다.

다음은 해당 웹 사이트에서 추출한 코드입니다.

int main(int, char **) 
    { 
    tree<string> tr; 
    tree<string>::iterator top, one, two, loc, banana; 

    top=tr.begin(); 
    one=tr.insert(top, "one"); 
    two=tr.append_child(one, "two"); 
    tr.append_child(two, "apple"); 
    banana=tr.append_child(two, "banana"); 
    tr.append_child(banana,"cherry"); 
    tr.append_child(two, "peach"); 
    tr.append_child(one,"three"); 

    loc=find(tr.begin(), tr.end(), "two"); 
    if(loc!=tr.end()) { 
     tree<string>::sibling_iterator sib=tr.begin(loc); 
     while(sib!=tr.end(loc)) { 
     cout << (*sib) << endl; 
     ++sib; 
     } 
     cout << endl; 
     tree<string>::iterator sib2=tr.begin(loc); 
     tree<string>::iterator end2=tr.end(loc); 
     while(sib2!=end2) { 
     for(int i=0; i<tr.depth(sib2)-2; ++i) 
      cout << " "; 
     cout << (*sib2) << endl; 
     ++sib2; 
     } 
     } 
    } 

다른 점은 무엇입니까? 노드에 트리를 추가 할 때 구현이 더 간단합니다. 귀하의 버전이 indiscutably 간단하지만,이 lib의 dev에 아마 예를 들어 나무의 크기와 같은 트리를 탐색하지 않고도 액세스 할 수있는 정보가 필요했습니다.

성능상의 이유로 모든 노드에 루트를 저장하지 않으려한다고 가정합니다. 당신이 원하는 방식으로 구현하고 싶다면 논리의 대부분을 유지하고 반복기의 상위 트리에 링크를 추가하고 비트를 다시 추가하는 것이 좋습니다.

Answer 2

왜 그렇게하고 싶습니까? 이것이 학습을위한 것이라면, 당신은 당신 자신의 트리 데이터 구조를 작성할 수 있습니다. 이것이 임의의 인덱스 타입을 가지고있는 데이터 구조의 이점을 얻기위한 것이고, 검색을 위해 최적화되고 삽입시 잘 맞으면 맵을 사용하는 것을 고려하십시오.

맵은 로그 검색, 로그 삽입, 로그 삭제, 선형 공간과 같은 성능 보장을 트리의 검색과 동일하게 유지하는 연관 컨테이너입니다. 내부적으로 이들은 종종 붉은 색 검정 나무로 구현되지만 보증은 아닙니다. 여전히 STL 사용자로서 신경 써야 할 것은 STL 알고리즘과 데이터 구조의 성능 보장입니다. 나무로 구현 되든 작은 초록색으로 구현 되든 상관 없습니다.

부수적으로 root() 함수와 같은 것은 없습니다. 모든 STL 컨테이너에는 컨테이너의 개념적 시작을 구현하는 begin() 함수가 있습니다. 이 함수가 반환하는 반복자의 종류는 컨테이너의 특성에 따라 다릅니다.