Γενική άποψη του δέντρου, υλοποίηση και άλλα

Πολλοί άνθρωποι μάλλον προσπάθησαν να βρουν μια γενική κατασκευή δέντρου, αλλά η μηχανή αναζήτησης βρήκε μόνο δυαδικές... Δυαδικό δέντρο αναζήτησης, δυαδική διέλευση δέντρων και πολλοί άλλοι αλγόριθμοι.
Ναι, πράγματι, το γενικό δέντρο δεν χρησιμοποιείται πουθενά, η διάβαση είναι αργή, οι περιπτώσεις χρήσης είναι μικρές.

Έτσι, έκανα αυτή την ερώτηση στον εαυτό μου και τώρα θα εξηγήσω πώς είναι χτισμένο το δέντρο. Έτσι, ιδανικά, μια γενική δομή δέντρου θα πρέπει να αποθηκεύει τρεις μεταβλητές:

• δείκτης προς τον μεγαλύτερο γιο
• δείκτης στον αδερφό
• τα δεδομένα που πρόκειται να αποθηκεύσετε

struct Tnode {
    int key;
    struct Tnode *son;
    struct Tnode *brother;
};
typedef struct Tnode Node;

Ας δηλώσουμε έναν δείκτη στην κορυφή:

Node *tree = NULL;

Πρέπει να συμφωνήσουμε εκ των προτέρων πώς να εισάγουμε κορυφές· αυτό δεν είναι δυαδικό δέντρο και κάθε κορυφή μπορεί να έχει όσα παιδιά επιθυμείτε.

• + 2 (ή +ssbb 2) - εισαγωγή σε ένα δέντρο (για ένα γενικό δέντρο, η διαδρομή δίνεται από τη γραμμή, όπου r είναι η δημιουργία μιας ρίζας, s είναι μια μετάβαση στον μεγαλύτερο γιο, b είναι μια μετάβαση σε ένας αδερφός);

Επιτρέψτε μου να σας δώσω ένα παράδειγμα:

+r 1
+ 2
+ 3
+ 3
+s 5
+sb 6
+sb 7

Το αποτέλεσμα θα είναι ένα δέντρο σαν αυτό:

1
  2
    5
  3
    6
    7
  3

Αρχικά, ας δημιουργήσουμε μια συνάρτηση που προσθέτει μια κορυφή, δηλαδή, εκχωρεί μνήμη για την κορυφή και περνά έναν δείκτη σε αυτήν την κορυφή (αρχικά δεν συνδέεται με τίποτα).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  //обнуляем указатели к братьям и сыновьям, независимая вершина, которая хранит value
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

Πρέπει επίσης να δημιουργήσετε μια συνάρτηση που χειρίζεται τη συμβολοσειρά διαδρομής (+bs...). Κάθε φορά που ξεκινάμε τη διέλευση από τη ρίζα, αν δεν δημιουργείται, τότε βγάζουμε NULL (δεν μπορούμε να κάνουμε τίποτα). Αν δεν υπάρχει κορυφή, τότε πρέπει να τη δημιουργήσουμε. Πηγαίνουμε στη συνάρτηση δημιουργίας δέντρου και παίρνουμε έναν δείκτη στη ρίζα.

Σημειώστε ότι το Node**tree περνά τη δομή και όχι την αντιγράφει. Αυτό μας δίνει τη δυνατότητα να αλλάξουμε πράγματα που δεν μπορούμε να κάνουμε με τη δήλωση Node *tree.

Γενικά, πρέπει να βρούμε έναν δείκτη στην κορυφή στην οποία πρέπει να προσθέσουμε το son:

Node* add_node(Node **tree, const char *a) {
  Node* t = *tree;
  int value;
  scanf("%d", &value);
  int i = 0;
      while (a[++i] != ' ') {
        if (a[i] == 'r') {
            *tree = create_tree(value); // создаем корень
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // функция, которая возвращает указатель на сына
            continue;
          return NULL; //иначе NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) //возвращает указатель на брата t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // мы перешли к вершине, к которой хотели 
   //и теперь идем к последнему ее сыну,
   //чтобы добавить в конец списка
    t->brother = create_tree(value);
    return t->brother;
    }
    else {//если сына нет, то создадим его
      t->son = create_tree(value);
      return t->son;
    }
}

Έτσι χτίζουμε ένα δέντρο.

Υ.Γ αυτό είναι το πρώτο μου άρθρο, γι' αυτό μην κρίνετε πολύ σκληρά

Πηγή: www.habr.com