Adrita

task 7 (ds lab 7) 3rd sem

Aug 4th, 2020
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.40 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int y;
  4. struct node
  5. {
  6. int data;
  7. struct node* left;
  8. struct node* right;
  9. };
  10. typedef struct node Node;
  11. Node* create_node(int item)
  12. {
  13. Node* new_node=new Node();
  14. if(new_node==NULL)
  15. cout<<"Error"<<endl;
  16. else
  17. {
  18. new_node->data=item;
  19. new_node->left=new_node->right=NULL;
  20. }
  21. return new_node;
  22. }
  23. Node* insert_key(Node* x,int key)
  24. {
  25. Node* new_node=create_node(key);
  26. if(x==NULL)
  27. return new_node;
  28. if(key>x->data+3)
  29. {
  30. x->right=insert_key(x->right,key);
  31. }
  32. else if(key<x->data-3)
  33. {
  34. x->left=insert_key(x->left,key);
  35. }
  36. else
  37. y=0;
  38. return x;
  39. }
  40. void printlevelorder(Node * x)
  41. {
  42. if(x==NULL)
  43. return;
  44. queue<Node*>q;
  45. q.push(x);
  46. while(q.empty()==false)
  47. {
  48. Node* y=q.front();
  49. cout<<y->data<<" ";
  50. q.pop();
  51. if (y->left != NULL)
  52. q.push(y->left);
  53. if (y->right != NULL)
  54. q.push(y->right);
  55. }
  56. }
  57. Node * findmin(Node* node)
  58. {
  59. Node* current = node;
  60. while (current && current->left != NULL)
  61. current = current->left;
  62.  
  63. return current;
  64. }
  65. Node* deleteNode(Node* root, int key)
  66. {
  67. if (root == NULL)
  68. return root;
  69. if (key < root->data)
  70. root->left = deleteNode(root->left, key);
  71. else if (key > root->data)
  72. root->right = deleteNode(root->right, key);
  73. else
  74. {
  75. Node *temp ;
  76. if (root->left == NULL)
  77. {
  78. temp = root->right;
  79. free(root);
  80. return temp;
  81. }
  82. else if (root->right == NULL)
  83. {
  84. temp = root->left;
  85. free(root);
  86. return temp;
  87. }
  88.  
  89. temp = findmin(root->right);
  90. root->data = temp->data;
  91. root->right = deleteNode(root->right,temp->data);
  92. }
  93. return root;
  94. }
  95.  
  96. int main()
  97. {
  98. Node* root=NULL;
  99. y=1;
  100. while(1)
  101. {
  102. int n;
  103. cin>>n;
  104. if(n!=-1)
  105. {
  106. root=insert_key(root,n);
  107. }
  108. else
  109. break;
  110. }
  111. if(y==0)
  112. cout<<"All the inputs were not inserted."<<endl;
  113. int n;
  114. cin>>n;
  115. while(n--)
  116. {
  117. int key;
  118. cin>>key;
  119. deleteNode(root,key);
  120. printlevelorder(root);
  121. cout<<endl;
  122. }
  123. }
  124.  
Advertisement
Add Comment
Please, Sign In to add comment