🥇 Allgemeng Vue vum Bam, Ëmsetzung a méi

Vill Leit hu wahrscheinlech probéiert eng allgemeng Bamkonstruktioun ze fannen, awer d'Sichmaschinn huet nëmmen binär fonnt ... Binär Sichbaum, Binärbaumtraversal a vill aner Algorithmen.
Jo, tatsächlech, den allgemenge Bam gëtt net iwwerall benotzt, d'Traversal ass lues, d'Benotzungsfäll si kleng.

Also, ech hunn dës Fro gefrot an elo wäert ech erkläre wéi de Bam gebaut ass. Also, am Idealfall, soll eng allgemeng Bamstruktur dräi Variabelen späicheren:

Hiweis op eelste Jong
Zeigefanger zu Brudder
d'Donnéeën déi Dir späichere gitt

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

Loosst eis e Pointer op de Wirbel erklären:

Node *tree = NULL;

Mir mussen am Viraus averstane wéi Wirbelen anzeginn; Dëst ass kee binäre Bam, an all Wirbel kann esou vill Kanner hunn wéi gewënscht.

+ 2 (oder +ssbb 2) - Asetzen an e Bam (fir en allgemenge Bam gëtt de Wee vun der Linn uginn, wou r d'Schafung vun enger Wuerzel ass, s en Iwwergang zum eelste Jong ass, b ass en Iwwergang zu e Brudder);

Ech ginn e Beispill:

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

D'Resultat wäert e Bam wéi dëst sinn:

Eischtens, loosst eis eng Funktioun erstellen déi e Wirbel bäidréit, nämlech d'Erënnerung fir de Wirbel verdeelt an e Pointer un dësen Wirbel passéiert (ufanks net mat näischt verbonnen).

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

Dir musst och eng Funktioun erstellen déi de Wee String handhabt (+bs...). All Kéier wann mir d'Traversal vun der Root starten, wann et net erstallt gëtt, da gi mir NULL aus (mir kënnen näischt maachen). Wann et keen Héichpunkt ass, da musse mir et erstellen. Mir ginn op d'Erstelle Bam Funktioun a kréien e Pointer op d'Wurzel.

Notéiert datt Node ** Bam d'Struktur passéiert, net kopéiert. Dëst gëtt eis d'Fäegkeet Saachen ze änneren, déi mir net mat der Node * Bam Deklaratioun maache kënnen.

Am Allgemengen, musse mir e Pointer op d'Vertex fannen, op deen mir de Jong addéiere mussen:

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

Esou bauen mir e Bam.

P.S. mäin éischten Artikel, also beurteelt w.e.g. net ze streng

Source: will.com

Allgemeng Vue vum Bam, Ëmsetzung a méi

Setzt e Commentaire annuléieren reply