Рекурсив маълумотлар тузилмаси


Алгоритм амаллар кетма-кетлиги қуйида келтирилган


Download 0.95 Mb.
bet2/5
Sana03.02.2023
Hajmi0.95 Mb.
#1153754
1   2   3   4   5
Bog'liq
DdIPU5G3ejYJi3INtebeotSxmk5awWPOtwDPrjUB

Алгоритм амаллар кетма-кетлиги қуйида келтирилган.
ёки
  • дарахт кўруви (элементларини маълум бир кўринишда тартиблаш ёки чоп этиш);
  • дарахтга янги тугун қўйиш;
  • дарахт тугунини ўчириш;
  • дарахт тугунини қидириш.

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

Daraxtni e’lon qilish.

  • include
  • using namespace std;
  • class node{
  • public:
  • int info;
  • node *left;
  • node *right;
  • };

КФ

  • 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);}

Кўриш функцияси

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

Тугунларнинг холати

  • Ildiz . if(p==tree) cout<<”bu tugun ildiz ekan”;
  • else cout<<”bu tugun ildiz emas”;
  • Oraliq tugun. 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”;

Терминал тугун

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

Янги элемент

  • node *q=new node;
  • Qo’yilayotgan yangi element chap yoki o’ng o’g’il bo’lishini aniqlash lozim.
  • If(keykey) q->left=yangi;
  • else q->right=yangi;
  • search=yangi;
  • return 0;

int pretrave(node *tree){

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

Кўриш функцияси

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

int postrave(node *tree){

int postrave(node *tree){

  • if(tree!=NULL) {
  • postrave(tree->left);
  • postrave(tree->right);
  • cout<info;
  • }
  • return 0;
  • };

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

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

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

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

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


Бинар дарахтдан элементни ўчириш
 
Дарахт тугуни ўчирилаётганда 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).

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

  • node *del(node *tree, int key){
  • node *p=new node;
  • node *next=tree;
  • node *q=NULL;
  • while(next!=NULL)
  • { if (next->info==key){cout<<"Binar daraxtda "<
  • Mavjud"<

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

  • if (next->info>key){ q=next; next=next->left; }
  • else {q=next;next=next->right;}
  • }
  • if(next==NULL) cout<<"tuzilmada izlangan element yo’q!!!"<
  • node *v=NULL,*t=NULL,*s=NULL;
  • if(p->left==NULL)v=p->right;
  • else

Download 0.95 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling