}
if(temp->right!=NULL)
{
q.push(temp->right);
}
}
cout<<endl;
}
void add(Node* root,int value)
{
queue<Node*> q;
q.push(root);
while(!q.empty())
{
Node* temp=q.front();
q.pop();
if(temp->left==NULL)
{
temp->left=new Node(value);
goto label;
}
if(temp->right==NULL)
{
temp->right=new Node(value);
goto label;
}
if(temp->left!=NULL)
{
q.push(temp->left);
}
if(temp->right!=NULL)
{
q.push(temp->right);
}
}
label:;
}
int main()
{
/*construct tree*/
Node* root= new Node(9);
root->left= new Node(1);
root->right= new Node(8);
root->left->left= new Node(5);
root->left->right= new Node(4);
root->right->left= new Node(6);
root->right->right= new Node(7);
root->left->left->right= new Node(2);
root->left->right->right= new Node(3);
int value;
cin>>value;//input the data of node which we want to insert;
cout<<"Level order traversal before Insertion of node: ";
level_order(root);
/*add the node*/
add(root, value);
cout<<"Level order traversal after Insertion of node: ";
level_order(root);
return 0;
}
Output:
Level order traversal before Insertion of node: 9 1 8 5 4 6 7 2 3
Level order traversal after Insertion of node: 9 1 8 5 4 6 7 10 2 3
Ikkilik daraxtga qo'shilish vaqtining murakkabligi
O (N) bu erda N - berilgan ikkilik daraxtdagi tugunlar soni. Vaqtning eng yomon holati, har bir tugunda bittadan bolaga ega bo'lganda yuz beradi. Bu erda biz chiziqli vaqtda tashrif buyuramiz. Vaqtning chiziqli murakkabligi bu N tartibida ekanligini anglatadi.
Ikkilik daraxt turlari
Davom etishdan oldin, avval BT nima ekanligini bilamizmi? Ikkilik daraxt - bu bir turi ma'lumotlar tuzilishi bu tabiatan ierarxikdir. BT har bir tugun chap tugunlari, o'ng ko'rsatkichi va tugunning og'irligi sifatida ma'lumotlar bilan ifodalanadi. Har bir tugun eng ko'pi 2 bolani o'z ichiga olishi mumkin, ular ota tugunning chap va o'ng farzandiga tegishli.
Nima uchun ikkilik daraxtlar kerak? | Nima uchun biz ikkilik daraxtlardan foydalanamiz?
BT yordamida biz tezda qidirish, kiritish va o'chirishni amalga oshiramiz (ba'zi bir ustuvor tartibda berilgan ... BST kabi).
BT yordamida biz eng yaqin narsani ham topishimiz mumkin.
Ma'lumotlarni ierarxik tarzda saqlang (masalan, kompyuterdagi fayl tizimi).
Har qanday harakatni amalga oshirish uchun kam vaqt talab qiladigan ko'rsatgich yordamida BTni amalga oshiring.
Lug'atlarni prefiks izlash bilan amalga oshiring.
Ushbu ma'lumotlar to'plamining sobit matnida tezkor qidiruv.
Ikkilik daraxtlarning xususiyatlari
Har qanday darajadagi maksimal tugun soni: 2 ^ L bu erda L - bir qator darajalar (0 <= L <= H).
BT balandlikdagi H tugunlarining minimal va maksimal soni: Minimal- H + 1 va maksimal- 2 ^ (H + 1) - 1 bu erda 0 darajasi 0 ga teng.
N tugunlarga ega bo'lgan ma'lum bir BTning minimal balandligi: log2 (N + 1) -1 bu erda 0 darajasi 0 ga teng.
Barg tugunlarining umumiy soni: 2 bolali tugunlarning umumiy soni + 1.
L bargli tugunlarga ega bo'lgan BT darajalarining minimal soni: (log2 L) +1.
Do'stlaringiz bilan baham: |