Minimal narxli daraxt skeleti dasturiy ta’minotini tuzish

Бинар дарахт устида бажариладиган асосий амаллар
Дарахт кўруви

• Тўғри (Юқоридан қуйига). Кўрув қуйидаги кетма-кетликда бажарилади: A-B-C;
• Симметрик (Чапдан ўнгга). Кўрув қуйидаги кетма-кетликда бажарилади: B-A-C.
• Тескари (Қуйидан юқорига). Кўрув қуйидаги кетма-кетликда бажарилади: B-C-A.

Бинар дaraxtni e’lon qilish Объявление бинарного дерева

• include
• using namespace std;
• class node{
• public: // kirish spesifikatsiyasi
• int info; // axborot maydoni
• node*left; // chap ko’rsatkich
• node*right; // o’ng ko’rsatkich
• };

int intrave(node *tree){

• int intrave(node *tree){
• if(tree!=NULL) {
• intrave(tree->left);
• cout<info<<",";
• intrave(tree->right);
• }
• return 0; };

int main(){

• int main(){
• node*tree=0;
• node*next=0;
• int n, key;
• cout<<" n= " ;
• cin>>n;
• for(int i=1; i<=n;i++){
• node *p=new node;
• node *last=new node;
• cin>>key;
• p->info=key;

p->left=0;

• p->left=0;
• p->right=0;
• if(i==1){tree=p; next=tree; continue;
• }next=tree;
• while(1){last=next;
• if(p->infoinfo)next=next->left;
• else next=next->right;
• if(next==0) break;

}

• }
• if(p->infoinfo) last->left=p;
• else last->right=p;
• }
• intrave(tree);}

Ko’rish funksiyasi

• int intrave(node *tree){
• if(tree!=NULL) {
• intrave(tree->left);
• cout<info<<",";
• intrave(tree->right);
• }
• return 0;
• };

Tugunlarning holati

• if(p==tree) cout<<”bu tugun ildiz ekan”;
• else cout<<”bu tugun ildiz emas”;
• if(p!=tree){
• if((p->left!=NULL)&&(p->right!=NULL)) cout<<”bu tugun 2 ta farzandga
• ega oraliq tugun”;
• else if((p->left!=NULL)||(p->right!=NULL) cout<<”bu 1 ta farzandga ega
• oraliq tugun”;
• } else cout<<”bu tugun oraliq tugun emas”;

Terminal tugun

• if((p->left==NULL)&&(p->right==NULL)) cout<<”bu tugun terminal tugun”;
• else cout<<”bu terminal tugun emas”;

Дарахтга янги тугун қўйиш

Дарахтга янги тугун қўйиш

Дарахтга бирор бир тугун қўйишдан олдин дарахтда берилган калит бўйича қидирувни амалга ошириш лозим бўлади. Агар берилган калитга тенг калитли тугун мавжуд бўлса, у ҳолда дастур ўз ишини якунлайди, акс ҳолда дарахтга тугун қўйиш амалга оширилади.

Эслатма: Дарахтда янги тугун фақатгина кўрсаткичларини камида биттаси бўш бўлган тугундан кейин қўйилади.

Элемент қўйиш

Бинар дарахтдан элементни ўчириш
 
Дарахт тугуни ўчирилаётганда 3 ҳил ҳолат бўлиши мумкин:

• Топилган тугун терминал (барг). Бу ҳолатда тугун шунчаки ўчириб ташланади.
• Топилган тугун фақатгина битта ўғилга эга. У ҳолда ўғил ота ўрнига жойлаштирилади.
• Ўчирилаётган тугун иккита ўғилга эга. Бундай ҳолатда шундай қисм дарахтлар звеносини топиш лозимки, уни ўчирилаётган тугун ўрнига қўйиш мумкин бўлсин. Бундай звено ҳар доим мавжуд бўлади. Бу
• ёки чап қисм дарахтнинг энг ўнг томондаги тугуни (ушбу звенога эришиш учун кейинги учига чап шоҳ орқали ўтиб, навбатдаги учларига эса, мурожаат NIL бўлмагунча, фақатгина ўнг шоҳлари орқали ўтиш зарур).
• ёки ўнг қисм дарахтнинг энг чап тугуни (ушбу звенога эришиш учун кейинги учига ўнг шоҳ орқали ўтиб, навбатдаги учларига эса, мурожаат NIL бўлмагунча, фақатгина чап шоҳлари орқали ўтиш зарур).

Элемент ўчириш

• p – ishchi ko‟rsatkich;
• q - p dan bir qadam orqadagi ko‟rsatkich;
• v – o‟chirilayotgan tugun merosxo‟rini ko‟rsatadi;
• t – v dan bir qadam orqada yuradi;
• s - v dan bir qadam oldinda yuradi (chap o‟g‟ilni yoki bo‟sh joyni ko‟rsatib
• boradi).