fork download
copy 
  1. /* Author : Nguyen Thanh Tung */
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define endl 		         '\n'
  6. #define int 		         long long
  7.  
  8. using namespace 	         std;
  9.  
  10. typedef pair<int, int>       ii;
  11.  
  12. const int       N            = 1e5 + 7;
  13. const long long oo           = 1e18 + 7;
  14. const long long MOD          = 1e9 + 7;
  15.  
  16. int n;
  17. struct node {
  18.     int key;
  19.     struct node *left;
  20.     struct node *right;
  21. };
  22. typedef struct node * nodeTree;
  23. nodeTree t;
  24. void khoitao(nodeTree &t) {
  25.     t = NULL;
  26. }
  27. nodeTree newNode() {
  28.     nodeTree p = (nodeTree)malloc(sizeof(struct node));
  29.     return p;
  30. }
  31. nodeTree insertNode(nodeTree &p, int x) 
  32. { 
  33.     if (p == NULL) {
  34.         p = newNode();
  35.         p -> key = x;
  36.         p -> left = p -> right = NULL;
  37.     }
  38.     else if (x < p->key) 
  39.         p->left  = insertNode(p->left, x); 
  40.     else if (x > p->key) 
  41.         p->right = insertNode(p->right, x);   
  42.     return p; 
  43. } 
  44. void nhap(nodeTree &t) {
  45.     cin >> n;
  46.    // t = insertNode(t, x);
  47.     for(int i = 1; i <= n; ++i) {
  48.         int x;
  49.         cin >> x;
  50.         insertNode(t, x);
  51.     }
  52. }
  53. void nlrdq(nodeTree t) {
  54.     if(t != NULL) {
  55.         cout << (t -> key) << " ";
  56.         nlrdq(t -> left);
  57.         nlrdq(t -> right);
  58.     }
  59. }
  60. void nlrst(nodeTree t) {
  61.     if (t == NULL) return;
  62.     stack<nodeTree> s;
  63.     s.push(t);
  64.     while (!s.empty()) {
  65.         nodeTree current = s.top();
  66.         s.pop();
  67.         cout << current->key << " ";
  68.         if (current->right != NULL) {
  69.             s.push(current->right);
  70.         }
  71.         if (current->left != NULL) {
  72.             s.push(current->left);
  73.         }
  74.     }
  75. }
  76. void lnrdq(nodeTree t) {
  77.     if(t != NULL) {
  78.         lnrdq(t -> left);
  79.         cout << (t -> key) << " ";
  80.         lnrdq(t -> right);
  81.     }
  82. }
  83. void lnrst(nodeTree t) {
  84.     stack<nodeTree> s;
  85.     nodeTree current = t;
  86.     while (current != NULL || !s.empty()) {
  87.         while (current != NULL) {
  88.             s.push(current);
  89.             current = current->left;
  90.         }
  91.         current = s.top();
  92.         s.pop();
  93.         cout << current->key << " ";
  94.         current = current->right;
  95.     }
  96. }
  97. void lrndq(nodeTree t) {
  98.     if(t != NULL) {
  99.         lrndq(t -> left);
  100.         lrndq(t -> right);
  101.         cout << (t -> key) << " ";
  102.     }
  103. }
  104. void lrnst(nodeTree t) {
  105.     if (t == NULL) return;
  106.     stack<nodeTree> s;
  107.     stack<nodeTree> p;
  108.     s.push(t);
  109.     while (!s.empty()) {
  110.         nodeTree current = s.top();
  111.         s.pop();
  112.         p.push(current);
  113.         if (current->left != NULL) {
  114.             s.push(current->left);
  115.         }
  116.         if (current->right != NULL) {
  117.             s.push(current->right);
  118.         }
  119.     }
  120.     while (!p.empty()) {
  121.         cout << p.top()->key << " ";
  122.         p.pop();
  123.     }
  124. }
  125. void duyetmuc(nodeTree t) {
  126.     if(t == NULL) {
  127.         return;
  128.     }
  129.     queue<nodeTree> st;
  130.     st.push(t);
  131.     while(!st.empty()) {
  132.         nodeTree cur = st.front();
  133.         st.pop();
  134.         cout << cur -> key << " ";
  135.         if(cur -> left != NULL) {
  136.             st.push(cur -> left);
  137.         }
  138.         if(cur -> right != NULL) {
  139.             st.push(cur -> right);
  140.         }
  141.     }
  142. }
  143.  
  144. void tv1() {
  145.     cout <<"1/ " << endl;
  146.     cout << "NLR : ";
  147.     nlrst(t);
  148.     cout << endl;
  149.     cout << "LNR : ";
  150.     lnrst(t);
  151.     cout << endl;
  152.     cout << "LRN : ";
  153.     lrnst(t);
  154.     cout << endl;
  155.     cout << "Duyet Muc : ";
  156.     duyetmuc(t);
  157.     cout << endl;
  158. }
  159.  
  160. int nct(nodeTree t, int cnt) {
  161.     if(t -> left == NULL) return cnt;
  162.     nct(t -> left, cnt + 1);
  163. }
  164.  
  165. int ncp(nodeTree t, int cnt) {
  166.     if(t -> right == NULL) return cnt;
  167.     ncp(t -> right, cnt + 1);
  168. }
  169.  
  170. void tv2() {
  171.     cout << "2/ ";
  172.     cout << nct(t, 0) << endl;
  173. }
  174.  
  175. void tv3() {
  176.     cout << "3/ ";
  177.     cout << ncp(t, 0) << endl;
  178. }
  179.  
  180. int dem_node(nodeTree t) {
  181.     int Left;
  182.     if(t -> left == NULL) {
  183.         Left = 1;
  184.     }
  185.     else {
  186.         Left = dem_node(t -> left) + 1; 
  187.     }
  188.     int Right;
  189.     if(t -> right == NULL) {
  190.         Right = 1;
  191.     }
  192.     else {
  193.         Right = dem_node(t -> right) + 1;
  194.     }
  195.     return Right + Left - 1;
  196. }
  197.  
  198. void tv4() {
  199.     cout << "4/ ";
  200.     cout << dem_node(t -> left) << endl;
  201. }
  202.  
  203. void tv5() {
  204.     cout << "5/ ";
  205.     cout << dem_node(t -> right) << endl;
  206. }
  207.  
  208. int dem_1_ccon(nodeTree t) {
  209.     if(t -> right == NULL && t -> left == NULL) 
  210.         return 0;
  211.     if(t -> right == NULL) 
  212.         return dem_1_ccon(t -> left) + 1;
  213.     if(t -> left == NULL) 
  214.         return dem_1_ccon(t -> right) + 1;
  215.     if(t -> left != NULL && t -> right != NULL)
  216.         return dem_1_ccon(t -> left) + dem_1_ccon(t -> right);
  217. }
  218.  
  219. void tv6() {
  220.     cout << "6/ " << dem_1_ccon(t) << endl;
  221. }
  222.  
  223. int dem_la(nodeTree t) {
  224.     if(t == NULL) 
  225.         return 0;
  226.     if(t -> right == NULL && t -> left == NULL) 
  227.         return 1;
  228.     return dem_la(t -> right) + dem_la(t -> left);
  229. }
  230.  
  231. void tv7() {
  232.     cout << "7/ " << dem_la(t) << "\n";
  233. }
  234.  
  235. int ccao(nodeTree t) {
  236.     if(t -> left == NULL && t -> right == NULL) 
  237.         return 1;
  238.     if(t -> left == NULL) 
  239.         return ccao(t -> right) + 1;
  240.     if(t -> right == NULL) 
  241.         return ccao(t -> left) + 1;
  242.     return max(ccao(t -> right), ccao(t -> left)) + 1;
  243.  
  244. }
  245.  
  246. void tv8() {
  247.     cout << "8/ " << ccao(t) << "\n";
  248. }
  249.  
  250. int maxx(nodeTree t) {
  251.     if(t -> right == NULL) {
  252.         return t -> key;
  253.     }
  254.     return maxx(t -> right);
  255. }
  256.  
  257. void tv9() {
  258.     cout << "9/ " << maxx(t) << endl;
  259. }
  260. void solve() {
  261.     khoitao(t);
  262.     nhap(t);
  263.     tv1();
  264.     tv2();
  265.     tv3();
  266.     tv4();
  267.     tv5();
  268.     tv6();
  269.     tv7();
  270.     tv8();
  271.     tv9();
  272. }
  273.  
  274. #define TASK "code"
  275.  
  276. signed main () {
  277.     ios_base::sync_with_stdio (false);
  278.     cin.tie(nullptr), cout.tie(nullptr);
  279.     if (fopen(TASK".INP", "r")) {
  280.        freopen(TASK".INP", "r", stdin);
  281.        freopen(TASK".OUT", "w", stdout);
  282.     }
  283.     solve();
  284.     return 0;
  285. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
11
20
10
30
15
25
40
27
26
5
13
14
stdout
copy 
1/ 
NLR : 20 10 5 15 13 14 30 25 27 26 40 
LNR : 5 10 13 14 15 20 25 26 27 30 40 
LRN : 5 14 13 15 10 26 27 25 40 30 20 
Duyet Muc : 20 10 30 5 15 25 40 13 27 14 26 
2/ 0
3/ 0
4/ 5
5/ 5
6/ 4
7/ 4
8/ 5
9/ 40
https://ideone.com/ymuPIl
language:
C++14 (clang 8.0)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!