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

StackOverflow https://stackoverflow.com/questions/19193

  •  09-06-2019
  •  | 
  •  

문제

포인터 대신 반복자를 사용하는 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 알고리즘 및 데이터 구조의 성능 보장 만 있으면됩니다.그들이 나무 또는 작은 녹색 남자로 구현되었는지 여부는 당신에게 중요하지 않습니다.

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

도움이 되었습니까?

해결책

여기는 나무.아아 조금 다르지만 원하는 것과 약간 가깝습니다.

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

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

이제 무엇이 다른가요?트리에 노드를 추가 할 때 구현이 더 간단합니다.귀하의 버전이 명백히 단순하기는 하지만 이 라이브러리의 개발자는 트리를 탐색하지 않고도 트리 크기와 같은 일부 정보에 액세스할 수 있기를 원했을 것입니다.

나는 또한 성능상의 이유로 모든 노드에 루트를 저장하고 싶지 않다고 가정합니다.따라서 원하는 방식으로 구현하려면 대부분의 논리를 유지하고 반복자에서 상위 트리에 대한 링크를 추가하고 약간의 추가를 다시 작성하는 것이 좋습니다.

다른 팁

왜 그렇게 하고 싶나요?이것이 학습 목적이라면 자신만의 트리 데이터 구조를 작성할 수 있습니다.이것이 임의의 인덱스 유형을 보유하고 검색에 최적화되어 있고 삽입에 능숙한 데이터 구조의 이점을 얻기 위한 것이라면 맵 사용을 고려하십시오.

맵은 트리와 동일한 성능을 보장하는 연관 컨테이너입니다.로그 검색, 로그 삽입, 로그 삭제, 선형 공간.내부적으로는 레드-블랙 트리로 구현되는 경우가 많지만 이것이 보장되는 것은 아닙니다.그럼에도 불구하고 STL 사용자로서 관심을 가져야 할 것은 STL 알고리즘과 데이터 구조의 성능 보장입니다.그들이 나무로 구현되는지 아니면 작은 녹색 인간으로 구현되는지는 당신에게 중요하지 않습니다.

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

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top