♓️ 👱🏿 🔎 Pandangan umum tentang pohon, implementasi dan tidak hanya 🤖 ☝️ 🤔

Banyak yang mungkin mencoba menemukan konstruksi pohon umum, tetapi mesin pencari hanya menemukan yang biner ... Pohon pencarian biner, traversal dari pohon biner dan banyak algoritma lainnya.
Ya, memang, pohon umum tidak digunakan di mana saja, memotongnya lambat, kasus penggunaannya kecil.

Jadi, saya mengajukan pertanyaan ini dan sekarang saya akan menjelaskan bagaimana pohon itu dibangun. Jadi, idealnya, struktur pohon bentuk umum harus menyimpan tiga variabel:

pointer ke putra tertua
arahkan ke saudara
data yang akan Anda simpan

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

Nyatakan sebuah pointer ke atas:

 Node *tree = NULL;

Kita harus menyetujui terlebih dahulu cara memasukkan simpul, ini bukan pohon biner, dan setiap simpul dapat memiliki anak laki-laki.

+ 2 (atau + ssbb 2) - penyisipan ke pohon (untuk pohon yang tampak umum, jalan ditentukan oleh garis, di mana r adalah root, s adalah transisi ke putra tertua, b adalah transisi ke saudara);

Saya akan memberi contoh:

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

Akibatnya, pohon ini akan dilepaskan:

 1 2 5 3 6 7 3

Pertama, buat fungsi yang menambahkan titik, yaitu, mengalokasikan memori untuk titik dan melewati pointer ke titik ini (awalnya tidak terkait dengan apa pun).

 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 harus membuat fungsi yang memproses string path (+ bs ...). Setiap kali kita memulai traversal dari root, jika tidak dibuat, maka kita mencetak NULL (kita tidak bisa melakukan apa-apa). Jika tidak ada puncak, maka kita harus membuatnya. Buka fungsi create tree dan dapatkan pointer ke root.

Catatan: Node ** pohon melewati struktur, bukan salin. Ini memberi kita kemampuan untuk mengubah apa yang tidak bisa dilakukan, tidak seperti deklarasi Node * tree.

Secara umum, kita harus menemukan pointer ke atas, yang perlu kita tambahkan putra:

 Node* add_node(Node **tree, const char *a) { Node* t = *tree; int value; scanf("%d", &value); int i = 0; while (a[++i] != '\0') { 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; } }

Dengan cara ini kita membangun pohon.

PS adalah artikel pertama saya, jadi tolong jangan menilai dengan ketat

Pandangan umum tentang pohon, implementasi dan tidak hanya

More articles: