Tema: Izbe-izlikler, oplamlar, terekler, grafikalar hám basqalardı kórsetiw Jobası

Pryufer Kodı. Pryufer kodı [1, n] kesindindegi n-2 pútkil sanlar izbe-izligi járdeminde n úshleri menen belgilengen tereklerdi Birma -bir kodlaw usılı. Yaǵnıy, Pryufer kodı - bul tolıq graf hám nomerler izbe-izliginiń barlıq terekleri arasındaǵı biyeksiyasi bolıp tabıladı. Tereklerdi kodlawdıń bul usılı nemis matematikalıqı Xaynts Pryufer tárepinen 1918-jılda usınıs etilgen. ta úshleri menen berilgen terek ushın Pryufer kodın qurıw algoritmın kórip shıǵayıq. Kirisiwde qırlardıń dizimi berilgen. Eń kishi nomerge iye bolǵan terektiń bargi saylanadı, keyin ol terekten alıp taslanadı jáne bul japıraq menen baylanısqan úshlerdiń sanı Pryufer kodına qosıladı. Bul procedura ret tákirarlanadı. Aqır-aqıbet, terekte tek 2 úsh qaladı hám algoritm bulmanda tawsıladı. Qalǵan eki ushınıń nomerleri kodqa jazılmaydı. Sonday etip, málim bir terek ushın Pryufer kodı ta nomerler izbe-izligi bolıp, bul jerde hár bir nomer eń kishi japıraq menen baylanısqan ushınıń sanı - bul segment degi nomer [1, n ]. Pryufer kodın anıqlaw.

Kodtı alıw algoritmı tómendegishe. Terek túyinleri 1 den n ge shekem bolǵan nomerler menen belgilengen (nomerlengen) bolsın. Biz eń kishi sanlı 1-dárejeli ushın tabamız hám kodqa oǵan qońsılas bolǵan ushınıń sanın kiritemiz, sonnan keyin tabılǵan ushın (qırı menen birge) óshirip taslaymiz. Alınǵan graf astı menen biz tap sol ámeldi atqaramız, onı tek bir qır qolguncha tákirarlaymız. Kodtı jaratıw procesi 34-suwretde keltirilgen. Keyingi basqıshda óshirilgen ushınıń sanı ramkaǵa kiritilgen. Berilgen grafda (34-súwret, a) birinshi dárejeli úshler arasında minimal san 2-uchda jaylasqan. Ol 1-uchga qońsılas. Sol sebepli Pryufer kodınıń birinshi nomeri 1. 2-ushın alıp taslaw nátiyjesinde biz b-suwretde kórsetilgen grafni alamız. Bul grafda dárejesi birge teń bolǵan úshler arasındaǵı minimal san 3 ke teń, sol sebepli koddıń ekinshi nomeri 4. Formada kórsetilgen graflarga sáykes keletuǵın taǵı ush tákirarlawdı atqarǵannan keyin, c, d, e-su'wretler degi bir qırdan ibarat terekti alamız {7; 6}. Process tamamlandi. Qabıl etilgen qádemlerdiń nátiyjeleri kestede keltirilgen. Aqırǵı qatarında kerekli kod ámeldegi - 14166.
Pryufer kodı arqalı terekti qayta tiklew.
Pryufer kodı menen kórsetilgen tereklerdi payda etiw algoritmı qırlardıń tiyisli dizimin alıwǵa múmkinshilik beredi. Áyyemgi kodti Pryufer kodına kiritilmegen úshler sanınıń artıp baratuǵın izbe-izligi deylik. Kórip shıǵılǵan mısal ushın áyyemgiod 2357 ge teń. Terek izbe-iz qırlardı qosıp qurıladı. Keyingi qosılǵan shet, birinshisidan baslap, vertikal juplıq menen payda boladı, olardıń nomerleri kod qatarında hám áyyemgiod qatarında birinshi boladı. Sonnan keyin, isletilingen qatar elementleri sızıladı. Eger kod qatarınan shıǵıp ketken nomer odaǵı qalǵan elementler qatarına kiritilmegen bolsa, onıń rejimin buzmasdan áyyemgiod qatarına qosılıwı kerek. Tariyp berińan háreketler kod hám áyyemgiod qatarlarınıń " qaldıqları" menen olardıń birinshisiniń barlıq elementleri óshirilguncha tákirarlanadı. Bunday halda, áyyemgiod sızıǵında payda etińan dizimge qosılatuǵın sońǵı shetti belgileytuǵın eki element boladı, nátiyjede biz Pryufer kodı menen belgilengen terekke sáykes keletuǵın n - 1 qırlardıń dizimin alamız.
AvL tereginen barlıq túyinlerdi alıp taslaw funksiyası
void avltree_free (struct avltree *tree)
{
if (tree == NULL) return;
avltree_free(tree->left);
avltree_free(tree->rigth);
free(tree);
}
Túyinnen gilt boyınsha izlew funksiyası
struct avltree *avltree_lookup(struct avltree *tree, int key)
{
while(tree !=NULL)
{
if(key == tree->key)
{
return tree;
}
else if(keykey)
{
tree = tree->left;
}
Else
{
tree = tree->rigth;
} }
};
Túyin payda etiw funksiyası
struct avltree *avltree_create(int key,char *value)
{
struct avltree *node; node = malloc(sizeof(*node));
if (node != NULL)
{
node->key = key;
node->value = value;
node->left = NULL;
node->right = NULL;
node->height = 0;
}
return node;
}