115
Pryufer kodi orqali daraxtni tiklash.
Pryufer
kodi bilan
ifodalangan daraxtlarni hosil qilish algoritmi qirralarning tegishli
roʻyxatini olishga imkon beradi.
Antikodni Pryufer kodiga kiritilmagan
uchlar sonining ortib
boruvchi ketma-ketligi deylik. Koʻrib chiqilgan misol uchun antikod
2357 ga teng.
Daraxt ketma-ket qirralarni qoʻshib quriladi. Keyingi qoʻshilgan
chekka,
birinchisidan boshlab, vertikal juftlik bilan hosil boʻladi,
ularning raqamlari kod satrida va antikod satrida birinchi boʻladi.
Shundan soʻng, ishlatilgan satr elementlari chiziladi. Agar kod satridan
chiqib ketgan raqam undagi qolgan elementlar
qatoriga kiritilmagan
boʻlsa, uning tartibini buzmasdan antikod qatoriga qoʻshilishi kerak.
Ta‘riflangan harakatlar kod va antikod satrlarining "qoldiqlari" bilan
ularning birinchisining barcha elementlari oʻchirilguncha takrorlanadi.
Bunday holda, antikod chizigʻida hosil qilingan roʻyxatga qoʻshiladigan
soʻnggi chekkani belgilaydigan ikkita element boʻladi,
natijada biz
Pryufer kodi bilan belgilangan daraxtga mos keladigan n - 1 qirralarning
roʻyxatini olamiz.
3-misol.
Masalan, 1-misolda berilgan 14166 kodi yordamida
daraxtni tiklaylik. Yuqorida 1-misolda koʻrsatilgandek
mos keladigan
antikod 2357 ni tashkil qiladi. Shuning uchun daraxtning birinchi qirrasi
{1; 2}. 1 va 2-ni kesib oʻtib, biz kod satrida 4166 va antikod satrida 357
olamiz. Keyingi takrorlashda {4; 3} juftligini kesib tashlaymiz va
qatorga antikod 4 ni kiritamiz va hokazo. Takrorlashlar ketma-ketligi 8-
jadvalda keltirilgan.
h) Pryufer kodi: 1 5 2 6 6 2 1 3
