Algoritmlar va berilganlar strukturalari

Ko’p o’lchamli daraxtni binar ko’rinishga keltirish.

m-o`lchamli daraxtni binar ko`rinishga keltirish

Ko`p o`lchamli daraxtni binary ko`rinishga keltirishning noformal algoritmi: Daraxtning har bir tugunida katta o`g`liga mos chetki chap shoxidan tashqari barcha shoxlari kesib tashlanadi.


Binar daraxtda key(left_son)


.

оtа

Chаp o`g`il

O`ng o`g`il

• 
  Bitta otaning barcha o`g`illari gorizontal chiziq bilan ulanadi.
  

• Hosil qilingan tuzilmada har bir katta o`g`il mazkur tugun pastida turgan tugun hisoblanadi. (agar u mavjud bo`lsa). Amallar ketma- ketligi quyida keltirilgan:

yoki

• 
  Daraxt ko’ruvi (elementlarni ma’lum bir ko’rinishda tartiblash yoki chop etish);
  
• 
  Daraxtga yangi tugun qo’yish;
  

• Daraxt tugunini o’chirish;

• 
  Daraxt tugunini qidirish.
  

44. Daraxtlar ustidagi bajariladigan amallar.

Binar daraxtlar ustida bajariladigan amallar:

daraxtni aylanib o’tish (daraxtda o’tish) (bunda, asosan, tugunlarni chop etish tushuniladi);

daraxtga yangi tugun qo’yish;

daraxt tugunini o’chirish;

daraxt tugunini qidirish.
1-amal. Daraxtda o’tish.

Daraxtda o’tish asosan uchta ko’rinishi mavjud, ya’ni berilgan daraxtda:

To’g’ri o’tish: Ildiz »» Chap qismdaraxt »» O’ng qismdaraxt Natijada hosil bo’lgan ro’yxat: {1, 2, 4, 8, 5, 9, 10, 3, 6, 7} Teskari o’tish: Chap qismdaraxt »» Ildiz »» O’ng qismdaraxt Natijada hosil bo’lgan ro’yxat: {8, 4, 2, 9, 5, 10, 1, 6, 3, 7} Oxiridan o’tish: Chap qismdaraxt »» O’ng qismdaraxt »» Ildiz Natijada hosil bo’lgan ro’yxat: {8, 4, 9, 10, 5, 2, 6, 7, 3, 1}