c에서 n-ary trees

Question

C 언어로 N-Ary 트리를 깔끔하게 구현하는 것은 무엇입니까?

특히, 나는 각 노드에 불완전한 수의 어린이가있는 자체 뱅킹이 아닌 n-ary 트리를 구현하고 싶습니다. 각 노드는 예를 들어 다음과 같이 이미 정의 된 구조물을 보유합니다.

struct task {
  char command[MAX_LENGTH];
  int required_time;
};

Answer 1

첫 번째 패스로서, 당신은 단순히 구조 (그것을 부르자 트린 노드) a 직무, 그리고 일련의 포인터 트린 노드에스. 이 세트는 배열 일 수 있습니다 (if N 고정) 또는 링크 된 목록 (if N 가변적입니다). 링크 된 목록은 추가를 선언해야합니다. 구조 (그것을 불러 봅시다 ListNode)와 함께 트린 노드 실제 어린이 (나무의 일부)에 대한 포인터와 다음에 대한 포인터 ListNode 목록에서 (없는 목록의 끝에있는 경우).

다음과 같이 보일 수 있습니다.

struct task {
  char command[MAX_LENGTH];
  int required_time;
};

struct TreeNode;

struct ListNode {
  struct TreeNode * child;
  struct ListNode * next;
};

struct TreeNode {
  struct task myTask;
  struct ListNode myChildList;
};

Answer 2

모든 N- 아리 트리는 이진 트리로 표시 될 수 있으며 각 노드에서 왼쪽 포인터는 첫 번째 자식을 가리키고 오른쪽 포인터는 다음 형제를 가리 킵니다.

             R                        R
           / | \                      |
          B  C  D                     B -- C -- D
         / \    |                     |         |
        E   F   G                     E -- F    G

따라서 귀하의 경우는 다음과 같습니다.

struct task {
  char command[MAX_LENGTH];
  int required_time;
};

struct node {
  struct task taskinfo;
  struct node *firstchild;
  struct node *nextsibling;
};

이 기술은 많은 알고리즘이 더 복잡한 데이터 구조가 아닌 이진 트리에서 표현할 수 있기 때문에 쓰기가 더 간단하다는 이점이 있습니다.