Bu uning har bir tuguni nol yoki bir- necha bolaga ega bo‘lgan iyerarxik tuzilmadir

Umumiy daraxtlarni ikkilik daraxtlar sifatida kodlash

Umumiy buyurtma qilingan daraxtlar va ikkilik daraxtlar o'rtasida birma-bir xaritalash mavjud, ular ayniqsa foydalaniladi Lisp umumiy tartibli daraxtlarni ikkilik daraxtlar sifatida ko'rsatish. Umumiy buyurtma qilingan daraxtni ikkilik daraxtga aylantirish uchun biz faqat umumiy daraxtni chapdan o'ngga birodarlik usulida namoyish etishimiz kerak. Ushbu namoyish natijasi, agar boshqa nuqtai nazardan qaralsa, avtomatik ravishda ikkilik daraxt bo'ladi. Har bir tugun N buyurtma qilingan daraxtda tugunga to'g'ri keladi N ' ikkilik daraxtda; The chap ning farzandi N ' ning birinchi bolasiga mos keladigan tugun N, va to'g'ri ning farzandi N ' ga to'g'ri keladigan tugun N keyingi birodar ---, ya'ni ota-onasining farzandlari orasida navbatdagi tugun N. Umumiy tartib daraxtining bu ikkilik daraxt tasvirini ba'zida a deb ham atashadi chap bolada o'ng aka-uka ikkilik daraxt (shuningdek, LCRS daraxti, juft zanjirli daraxt, filial-merosxo'r zanjiri deb ham ataladi).
Bu haqda o'ylashning bir usuli shundaki, har bir tugunning bolalari a bog'langan ro'yxat, ular bilan birga zanjirlangan to'g'ri maydonlari va tugun faqat ushbu ro'yxatning boshiga yoki boshiga ko'rsatgichga ega chap maydon.
Masalan, chap tomondagi daraxtda A ning 6 ta farzandi bor {B, C, D, E, F, G}. Uni o'ngdagi ikkilik daraxtga aylantirish mumkin.

Ikkilik daraxtni yon tomonga burilgan, chap qora qirralarni ko'rsatadigan asl daraxt deb hisoblash mumkin birinchi bola va ko'k rangning o'ng qirralari keyingi birodar. Chapdagi daraxt barglari Lispda shunday yozilgan bo'lar edi:
(((N O) I J) C D ((P) (Q)) F (M))
bu chap bolali tugunlarda hech qanday harflarsiz, xotirada o'ngdagi ikkilik daraxt sifatida amalga oshiriladi.

Umumiy operatsiyalar

Daraxtlarni aylantirish juda keng tarqalgan ichki operatsiyalar o'z-o'zini muvozanatlashtiradigan ikkilik daraxtlar.
Ikkilik daraxtlarda bajarilishi mumkin bo'lgan turli xil operatsiyalar mavjud. Ba'zilar mutator operatsiyalar, boshqalari shunchaki daraxt haqida foydali ma'lumotlarni qaytaradilar.