Drzewa N-ary w C

Question

Drzewa N-ary w C

Która byłaby zgrabną implementacją drzewa N-ary w języku C?

W szczególności chcę zaimplementować drzewo n-ary, a nie samo-balansujące, z niezwiązaną liczbą dzieci w każdym węźle, w którym każdy węzeł posiada już zdefiniowaną strukturę, jak na przykład:

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

14

c struct abstract-data-type n-ary-tree

Author: Remo.D, 2008-10-10

Source

2 answers

Dowolne drzewo n-ary może być reprezentowane jako drzewo binarne, gdzie w każdym węźle lewy wskaźnik wskazuje na pierwsze dziecko, a prawy na następnego brata.

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

Więc twoja sprawa będzie:

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

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

Ta technika ma tę zaletę, że wiele algorytmów jest prostszych do napisania, ponieważ można je wyrazić na drzewie binarnym, a nie na bardziej skomplikowanej strukturze danych.

51

Author: Remo.D,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2008-10-10 16:29:00

score 13 · Accepted Answer

Jako pierwsze przejście, możesz po prostu utworzyć strukturę (nazwijmy ją TreeNode), która zawiera Zadanie, a także zestaw wskaźników do TreeNodeS. ten zestaw może być tablicą (jeśli N jest stała) lub połączoną listą (jeśli N jest zmienna). Lista powiązana wymaga zadeklarowania dodatkowej struktury (nazwijmy ją ListNode ) ze wskaźnikiem TreeNode do rzeczywistego potomka (części drzewa) oraz wskaźnikiem do następnego ListNode w liście (null jeśli na końcu listy).

Może wyglądać mniej więcej tak:

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