Guest User

Untitled

a guest
May 22nd, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.64 KB | None | 0 0
  1. #include <iostream>
  2. #include <iostream>
  3. #include <vector>
  4. #include <fstream>
  5. #include <algorithm>
  6. #include <string>
  7. #include <climits>
  8. using namespace std;
  9.  
  10. struct Node{
  11. int data;
  12. Node *left, *right;
  13.  
  14. void createBalancedTree(int n, Node *&curNode, ifstream& inp) {
  15. int temp;
  16. if (n > 0) {
  17. curNode = new Node;
  18. inp >> temp;
  19. curNode->data = temp;
  20. curNode->left = curNode->right = NULL;
  21. int nLeft = n / 2;
  22. int nRight = n - nLeft - 1;
  23. createBalancedTree(nLeft, curNode->left, inp);
  24. createBalancedTree(nRight, curNode->right, inp);
  25. }
  26. }
  27.  
  28. void add(int data, Node *&curNode) {
  29. if (!curNode) {
  30. curNode = new Node;
  31. curNode->data = data;
  32. curNode->left = curNode->right = NULL;
  33. }
  34.  
  35. else if (data < curNode->data)
  36. add (data, curNode->left);
  37.  
  38.  
  39. else if (data > curNode->data)
  40. add (data, curNode->right);
  41.  
  42. }
  43.  
  44. void search(int data, Node *curNode) {
  45. if (!curNode)
  46. cout << "Error" << endl;
  47. else if (data < curNode->data)
  48. search(data, curNode->left);
  49. else if (data > curNode->data)
  50. search(data, curNode->right);
  51. else
  52. cout << "Search is successful" << endl;
  53. }
  54.  
  55. void preorder(Node *curNode, ofstream& out) {
  56. if (curNode) {
  57. out << curNode->data << ' ';
  58. preorder(curNode->left, out);
  59. preorder(curNode->right, out);
  60. }
  61. }
  62.  
  63. void inorder(Node *curNode, ofstream& out) {
  64. if (curNode) {
  65. inorder(curNode->left, out);
  66. out << curNode->data << ' ';
  67. inorder(curNode->right, out);
  68. }
  69. }
  70.  
  71. void postorder(Node *curNode, ofstream& out) {
  72. if (curNode) {
  73. postorder(curNode->left, out);
  74. postorder(curNode->right, out);
  75. out << curNode->data << ' ';
  76. }
  77. }
  78.  
  79. int minLeaf(Node *curNode, int &min, ofstream& out) {
  80. if(curNode) {
  81. if (curNode->left == NULL && curNode->right == NULL) {
  82. if (curNode->data < min) {
  83. min = curNode->data;
  84. }
  85. }
  86. minLeaf(curNode->left, min, out);
  87. minLeaf(curNode->right, min, out);
  88.  
  89. }
  90. return min;
  91. }
  92.  
  93. int counter(Node *curNode, int &count) {
  94. if(curNode) {
  95. if (curNode->left != NULL && curNode->right == NULL) {
  96. count++;
  97. }
  98. counter(curNode->left, count);
  99. counter(curNode->right, count);
  100. }
  101. return count;
  102. }
  103.  
  104. };
  105.  
  106.  
  107. int main() {
  108. ifstream inp("input.txt");
  109. ofstream out("output.txt");
  110.  
  111. // Node *btree = NULL;
  112. // int x;
  113.  
  114. //Binary Search Tree
  115. /* while(!inp.eof()) {
  116. inp >> x;
  117. btree->add(x, btree);
  118. }
  119.  
  120. btree->preorder(btree, out);
  121.  
  122. int min = INT_MAX;
  123. int minLeaf = btree->minLeaf(btree, min, out);
  124. out << endl << minLeaf << endl;
  125. inp.close();
  126. */
  127. //Balanced Tree
  128. Node *tree = NULL;
  129. int n = 9;
  130. tree->createBalancedTree(n, tree, inp);
  131. tree->preorder(tree, out);
  132. int c = 0;
  133. c = tree->counter(tree, c);
  134. out << endl << c << endl;
  135. return 0;
  136.  
  137. }
Add Comment
Please, Sign In to add comment