Pandangan umum pokok, pelaksanaan dan banyak lagi

Ramai orang mungkin cuba mencari pembinaan pokok am, tetapi enjin carian hanya menemui binari... Pokok carian binari, traversal pokok binari dan banyak algoritma lain.
Ya, memang pokok umum tidak digunakan di mana-mana, laluannya perlahan, kes penggunaan kecil.

Jadi, saya bertanya kepada diri sendiri soalan ini dan sekarang saya akan menerangkan bagaimana pokok itu dibina. Jadi, idealnya, struktur pokok am harus menyimpan tiga pembolehubah:

• penunjuk kepada anak sulung
• penunjuk kepada abang
• data yang anda akan simpan

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

Mari kita isytiharkan penunjuk ke puncak:

Node *tree = NULL;

Kita mesti bersetuju terlebih dahulu bagaimana untuk memasukkan bucu; ini bukan pokok binari, dan setiap bucu boleh mempunyai seberapa banyak anak yang dikehendaki.

• + 2 (atau +ssbb 2) - sisipan ke dalam pokok (untuk pokok umum, laluan diberikan oleh garisan, di mana r ialah penciptaan akar, s ialah peralihan kepada anak sulung, b ialah peralihan kepada abang);

Biar saya berikan satu contoh:

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

Hasilnya akan menjadi pokok seperti ini:

1
  2
    5
  3
    6
    7
  3

Mula-mula, mari kita cipta fungsi yang menambah bucu, iaitu, memperuntukkan memori untuk bucu dan menghantar penuding ke bucu ini (pada mulanya tidak disambungkan kepada apa-apa).

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

Anda juga perlu mencipta fungsi yang mengendalikan rentetan laluan (+bs...). Setiap kali kita memulakan traversal dari akar, jika ia tidak dicipta, maka kita mengeluarkan NULL (kita tidak boleh berbuat apa-apa). Jika tiada bucu, maka kita mesti menciptanya. Kami pergi ke fungsi pepohon cipta dan dapatkan penunjuk ke akar.

Ambil perhatian bahawa Node**tree melepasi struktur, bukan menyalinnya. Ini memberi kita keupayaan untuk menukar perkara yang tidak boleh kita lakukan dengan pengisytiharan pokok Node *.

Secara umum, kita mesti mencari penunjuk ke puncak yang perlu kita tambahkan anak:

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

Beginilah cara kita membina pokok.

PS ini adalah artikel pertama saya, jadi tolong jangan menilai terlalu keras

Sumber: www.habr.com