Firmware-ul copacilor binari

Un firmware al unui copac este înțeles ca înlocuirea, conform unei anumite reguli, a pointerilor goi către fiii cu indicii către nodurile ulterioare corespunzătoare bypass-ului.

Deoarece lemnul după câmpul de suturare la stânga și la dreapta pot fi caracterizate fie legături structurale sau de „fir“, este nevoie de a le deosebi pentru această descriere trebuie să fie introduse în caracteristicile structura arborescentă din stânga și din dreapta (indicatoare false și TRUE).







Astfel, copaci mai repede cu ace distribui si de a nu necesită ca memorie suplimentară (stiva), dar necesită memorie suplimentară pentru stocarea steaguri de filamente, și, de asemenea operații complicate și pentru a permite îndepărtarea copacului elementului.

Arborele binar cusut pe Pascal poate fi descris după cum urmează:

unde lf și rf indică dacă relația este un indicator pentru un element sau un fir. Dacă lf sau rf este FALSE, atunci pachetul este un fir.

Înainte de crearea arborelui, vârful capului are următoarea formă: Aici săgeata punctată indică relația pe fir. Arborele este cusut în ramura stângă.

În exemplul de program 6.14, funcția (Inson) este dată pentru a determina fiul (succesorul) unui vârf dat.

(* ------ Funcția care găsește succesorul acestui vârf X ---- *)

(* -------- în funcție de mers pe jos amestecat ------------ *)







Funcția Inson (x: TreePtr): TreePtr;

În exemplul de program 6.15, funcția (Int) este dată pentru a determina tatăl (strămoșul) vârfului dat.

(* ---------- Funcția care emite nodul predecesor ------ *)

(* ------- în funcție de bypass ridicol ------------ *)

Funcția Inp (x: TreePtr): TreePtr;

dacă nu (x ^ .lf) atunci ieșiți;

în timp ce Inp ^ .rf face Inp: = Inp ^ .right; <связка не нить>

În exemplul de program 6.16, este implementată o funcție care implementează algoritmul pentru includerea unei înregistrări în arborele cusut (leftIn). Acest algoritm inserează vârful P ca subdrive stânga a vârfului X dat în cazul în care vârful X nu are un substrat de stânga. În caz contrar, un vârf nou este inserat între vârful X și vârful X ^ .left. În această operație, structura corectă a firmware-ului arborelui este menținută, corespunzând cu crawlerea mixtă.

(* - Introduceți p în stânga lui x sau între x și vârful său stâng - *)

Procedură LeftIn (x, p: TreePtr);

p. p ^ .lf: = x ^ lf; x ^ .left: = p;

x ^ .lf: = TRUE; p ^. dreapta: = x; p ^ .rf: = FALSE;

(* -------- Re-legătura cu predecesorul -------- *)

începe q: = TreePtr (Inp (p)); q ^ .right: = p; q ^ .rf: = FALSE;

De exemplu, luați în considerare firmware-ul arborelui prezentat în Figura 6-20. cu o traversare în jos.

Reprezentarea mecanică a arborelui în crawlerea descendentă cu firmware-ul este prezentată în figura 6.28.

Fig. 6.28. Reprezentarea conectată a aparatului arborelui sursă, reprezentată în figura 6-20, cu un crawl descendent cu firmware

Urmărirea by-pass-ului descendent cu firmware este dată în tabelul 6.3.

Luați în considerare exemplul aceluiași firmware pentru o plimbare mixtă. Reprezentarea mecanică a copacului cu un crawl mixt cu firmware-ul este prezentată în Figura 6.28.







Articole similare

Trimiteți-le prietenilor: