Həqiqətən nə olduğunu onsuz da bilirikmi? İkili ağac var? İndi bu yazıda, dəyəri verilən bir nodu necə silməyə diqqət yetiririk. Silmək istədiyimiz qovşağın dəyərinin BT-də silinmədən əvvəl hər zaman mövcud olduğuna əminik. İkili Ağac silməsində, -dən istifadə edirik BFS keçidi. Bu alqoritm məntiq aşağıdakı kimidir:
Alqoritm
Addım 1 Verilən ağacda BFS tətbiq edin və kök düyünündən başlayır.
Addım 2 Silmədən əvvəl səviyyə sifarişini çap edin.
Addım 3 BFS istifadə edərək son qovşağın ana və məlumatlarını tapın.
Addım 4 Son nodu silin.
Addım 5 Dəyəri düyünün dəyərinə bərabər olan hər hansı bir qovşaq tapdıqda, silmək istədiyimizdən sonra BFS-ni dayandırın.
Addım 6 BT-də son səviyyə indiki node və son node (sağda) məlumatlarını dəyişdirin.
Addım 7 Sildikdən sonra səviyyə sifarişini çap edin.
BT-də silinmə ilə bağlı sürətli bir anlayışı görək:
Dəyəri 4-ə bərabər olan bir düyünü silmək istəyirik. Buna görə də son düyünün (9) dəyərini silməklə (4) dəyişdiririk. Mübadilə etdikdən sonra son qovluğu silin.
İkili Ağacda Silmək üçün C ++ Kodu
/*C++ Implementation of Deletion in Binary Tree(Iterative Way)*/
#include<bits/stdc++.h>
using namespace std;
/*Structure of Node of BT which contain pointer to left child and right child and a data for node.*/
struct Node{
int data;
struct Node* left;// for left child;
struct Node* right;// for right child;
Node(int value)// create a node using new_Node;
{
data=value;
left=NULL;
right=NULL;
}
};
/*Function which print level order of the given tree*/
void level_order(Node* root)
{
if(root==NULL)
{
return;
}
queue<Node*> q;
q.push(root);
while(!q.empty())
{
Node* temp=q.front();
cout<<temp->data<<" ";
q.pop();
if(temp->left!=NULL)
{
q.push(temp->left);
}
if(temp->right!=NULL)
{
q.push(temp->right);
}
}
cout<<endl;
}
pair<Node*,int> last_node(Node* root)
{
if(root==NULL)
{
return make_pair(root,0);
}
queue<Node*> q;
q.push(root);
Node* last_parent=NULL;
int last_value;
while(!q.empty())
{
Node* temp=q.front();
/*store the parent of last node*/
if((temp->left!=NULL)&&(temp->right!=NULL))//if left and right sub tree are present;
{
if(temp->left->left==NULL&&temp->left->right==NULL&&temp->right->left==NULL&&temp->right->right==NULL)
{
last_parent=temp;
}
}
if(temp->left!=NULL)//if left subtree only present;
{
if(temp->left->left==NULL&&temp->left->right==NULL)
{
last_parent=temp;
}
}
if(temp->right!=NULL)//if right subtree only present;
{
if(temp->right->left==NULL&&temp->right->right==NULL)
{
last_parent=temp;
}
}
/*---------------end here---------------*/
/*for storing the value of last node.*/
last_value=temp->data;
q.pop();
if(temp->left!=NULL)
{
q.push(temp->left);
}
if(temp->right!=NULL)
{
q.push(temp->right);
}
}
/*return the parent of last node and the data of the last node*/
return make_pair(last_parent,last_value);
}
void delete_node(Node* root,int value,int last_value)
{
/*if only one node is present and we want to delete it*/
if(root->left==NULL&&root->right==NULL)
{
root=NULL;
return;
}
queue<Node*> q;
q.push(root);
while(!q.empty())
{
Node* temp=q.front();
q.pop();
/*if we find the node which we want to delete then change the data with last node data*/
if(temp->data==value)
{
temp->data=last_value;
}
if(temp->left!=NULL)
{
q.push(temp->left);
}
if(temp->right!=NULL)
{
q.push(temp->right);
}
}
}
int main()
{
/*construct tree*/
Node* root= new Node(0);//root node;
root->left= new Node(1);
root->right= new Node(2);
root->left->left= new Node(3);
root->left->right= new Node(4);
root->right->left= new Node(5);
root->right->right= new Node(6);
root->left->left->left= new Node(7);
root->left->right->left= new Node(8);
root->right->left->right= new Node(9);//last node
int value;
cin>>value;//input the data of node which we want to delete;
cout<<"Level order traversal before Deletion of node: ";
level_order(root);
/*Find the last node and its parent to remove last node from tree.*/
pair<Node*,int> last=last_node(root);
/*remove last node*/
if(last.first->left!=NULL&&last.first->left->data==last.second)
{
last.first->left=NULL;
}
if(last.first->right!=NULL&&last.first->right->data==last.second)
{
last.first->right=NULL;
}
/*delete the node*/
delete_node(root, value,last.second);
cout<<"Level order traversal after Deletion of node: ";
level_order(root);
return 0;
}
4
Level order traversal before Deletion of node: 0 1 2 3 4 5 6 7 8 9 Level order traversal after Deletion of node: 0 1 2 3 9 5 6 7 8
Zamanın mürəkkəbliyi
O (N) burada N ikili ağacdakı qovşaq sayıdır.
