Advertisement
Guest User

Untitled

a guest
Nov 17th, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.41 KB | None | 0 0
  1. #include <iostream>
  2. struct Node {
  3. int data;
  4. Node* left = nullptr;
  5. Node* right = nullptr;
  6. Node(int value) {
  7. data = value;
  8. }
  9. };
  10.  
  11. class BST {
  12. private:
  13. Node* root = nullptr;
  14.  
  15.  
  16. Node* addNode(int value, Node* current) {
  17. if (!current) {
  18. return new Node(value);
  19. }
  20.  
  21. if (value < current->data) {
  22. current->left = addNode(value, current->left);
  23. }
  24. else if (value > current->data) {
  25. current->right = addNode(value, current->right);
  26. }
  27.  
  28. return current;
  29. }
  30. void _inorder(Node* current) const {
  31. if (current) {
  32. _inorder(current->left);
  33. std::cout << current->data << " ";
  34. _inorder(current->right);
  35. }
  36. }
  37.  
  38. public:
  39. void insert(int value) {
  40. root = addNode(value, root);
  41. }
  42.  
  43. void inorder() const {
  44. _inorder(root);
  45. std::cout << "\n";
  46. }
  47. };
  48.  
  49. int findDistance(Node *root, int x)
  50. {
  51. if (root == NULL)
  52. return -1;
  53.  
  54. int dist = -1;
  55.  
  56. if ((root->data == x) ||
  57. (dist = findDistance(root->left, x)) >= 0 ||
  58. (dist = findDistance(root->right, x)) >= 0)
  59. return dist + 1;
  60.  
  61. return dist;
  62. }
  63. int main()
  64. {
  65. BST s;
  66. int nodes = 0;
  67. int findNode = 0;
  68. int N = 0;
  69. std::cin >> N;
  70. int K = 0;
  71. std::cin >> K;
  72.  
  73. for (int i = 0; i < N; i++) {
  74. std::cin >> nodes;
  75. s.insert(nodes);
  76. }
  77.  
  78. for (int i = 0; i < K; i++)
  79. {
  80. std::cin >> findNode;
  81. }
  82. for (int i = 0; i < K; i++)
  83. {
  84. std::cout << findDistance(, findNode) << std::endl;
  85. }
  86.  
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement