재귀가 있거나없는 비 이진 트리를 작성하는 방법은 무엇입니까?

나는 계층 이렇게되면 데이터가 있습니다재귀가 있거나없는 비 이진 트리를 작성하는 방법은 무엇입니까?

+----------------------+-------+ 
| name     | depth | 
+----------------------+-------+ 
| ELECTRONICS   |  0 | 
| TELEVISIONS   |  1 | 
| TUBE     |  2 | 
| LCD     |  2 | 
| PLASMA    |  2 | 
| PORTABLE ELECTRONICS |  1 | 
| MP3 PLAYERS   |  2 | 
| FLASH    |  3 | 
| CD PLAYERS   |  2 | 
| 2 WAY RADIOS   |  2 | 
+----------------------+-------+

튜브, LCD 및 플라즈마 텔레비전 자녀입니다. FLASH는 MP3 PLAYERS의 자녀입니다. MP3 플레이어, CD 플레이어 및 2 가지 라디오는 휴대용 전자 제품의 어린이입니다. 너는 훈련을 받는다.

이제 구조체 Node에는 해당 ID와 그 하위 노드가 포함되어 있습니다. 이처럼 :

struct Node 
{ 
    int id; 
    list<Node*> children; 
}

각 항목은 행 번호 인 ID로 식별 (전자 = 0, 텔레비전의 = 1 등), 그래서 그것의 아이들 누군지 알아 쉽게 찾을 수 있습니다 마디.

이것은 내가 작성하려고하는 나무입니다. 이 트리는 바이너리가 아닙니다. 재귀 적용은 쉬운 생각처럼 보이지 않습니다. 틀 렸으면 고쳐줘.

어떻게하면됩니까? 도움!

출처

2012-01-30 Michael Eilers Smith

재귀를 사용하면 둘 이상의 경로를 탐색하는 것이 더 쉬워집니다. 따라서 2 개 이상의 분기를 사용하면 재귀를 쉽게 선택할 수 있습니다. 대체 접근법 (반복)은 수동으로 진행 상황을 추적해야합니다 (예 : 스택이 재귀 버전에서 수행중인 작업 수행). 그러나이 상황에서 재귀는 필요하지 않습니다. –

대신 노드에 대한 포인터를 사용해야합니다. 그렇지 않으면 각 레벨의 트리에서 데이터를 복제하게됩니다.

또한 int id 대신 enum을 사용하면 코드가 좀 더 명확 해집니다. 비 - 이진 트리에 재귀를 사용하여 아무 문제가 없다

, 당신은 대신 재귀 함수 호출 (또는 유사) list<Node*>의 각을 left/right를 호출해야합니다. 이 같은

출처

2012-01-30 06:36:33

그건 의미가 있습니다. 감사! –

목록에서 O (n) (정의에 따라)와 달리 액세스 시간이 일정하기 때문에 목록 대신 해시를 사용하는 것이 좋습니다. –

트리를 재귀 적으로 빌드하기 위해 트리가 2 진수 여야한다는 제한은 없습니다. 재귀 적 방법과 비 재귀 적 방법 모두에서 생성 될 수 있습니다.

나는 나무를 위에서 아래로 만들었습니다. 즉, 아이들보다 먼저 부모 노드를 만듭니다. 필자는 소비를 선형으로 만들기 위해 어떻게 든 입력 데이터를 정렬 할 것입니다. 새 노드를 추가하려면 깊이를 매개 변수로 지정하고 (루트에서 내려가는 동안) 0에 도달 할 때까지 노드를 감소시켜야합니다. 물론 노드에 대한 상위 경로 정보가 필요합니다.

출처

2012-01-30 06:33:19 LeleDumbo

이것이 어떻게 작동하는지 모르겠습니다. 코드 스 니펫을 줄 수 있습니까? –

뭔가 :

이

int main() 
{ 
    Node flash(FLASH_ID); 
    Node mp3(MP3_ID); 

    mp3.children.push_back(flash); 
    // repeat 
}

출처

2012-01-30 06:47:16

두 개 이상의 연결 포인터를 사용할 수 있습니다. 즉

struct node 
{ 
int id; 
node *first_child; 
node *second child; 
node *third_child; 
}

당신이 최대 당신은 다른 아이들과 함께 노드를 가리키고 액세스 할 수 있습니다 3. 인 경우

. 자식이 3 명 미만인 경우 NULL로 설정할 수 있습니다.

출처

2013-12-05 11:00:11 user3069721

재귀가 있거나없는 비 이진 트리를 작성하는 방법은 무엇입니까?

답변

관련 문제