fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. /*
  4.     Bianry tree
  5.     1 thu tu giua
  6.     2 thu tu truoc
  7.     3 thu tu sau
  8.     4 thu tu muc level
  9.     5 free cay
  10.     6 dem so node
  11.     7 tinh do sau
  12.     8 dem so nut la cua cay
  13.     9 dem so node la co gia tri chan
  14.     10 dem so node la co gia tri lon hon k
  15.     11duong di dai nhat trong cay
  16. */
  17.  
  18.  
  19. typedef struct node {
  20.     int data;
  21.     struct node *left;
  22.     struct node *right;
  23. }node;
  24.  
  25. int deepth_tree(node *root);
  26.  
  27. node* create_node(int data) {
  28.     node *root = (node*)malloc(sizeof(node));
  29.     root->data = data;
  30.     root->left = NULL;
  31.     root->right = NULL;
  32.     return root;
  33. }
  34.  
  35. node* create_tree() {
  36.     node *a = create_node('A');
  37.     node *b = create_node('B');
  38.     node *c = create_node('C');
  39.     node *d = create_node('D');
  40.     node *e = create_node('E');
  41.     node *f = create_node('F');
  42.     node *g = create_node('G');
  43.     node *h = create_node('H');
  44.     node *i = create_node('I');
  45.     node *k = create_node('K');
  46.     node *j = create_node('J');
  47.     node *l = create_node('L');
  48.  
  49.  
  50.     // link notes
  51.  
  52.     h->left = d;
  53.     h->right= k;
  54.  
  55.     d->left = b;
  56.     d->right = f;
  57.  
  58.     k->left = j;
  59.     k->right = l;
  60.  
  61.     b->left = a;
  62.     b->right = c;
  63.  
  64.     f->right = e;
  65.  
  66.     return h;
  67.  
  68. //    node *a = create_node('A');
  69. //    node *b = create_node('B');
  70. //    node *c = create_node('C');
  71. //    node *d = create_node('D');
  72. //    node *e = create_node('E');
  73. //    node *f = create_node('F');
  74. //    node *g = create_node('G');
  75. //    node *h = create_node('H');
  76. //    node *i = create_node('I');
  77. //    node *j = create_node('J');
  78. //    node *k = create_node('K');
  79. //    node *l = create_node('L');
  80. //    node *m = create_node('M');
  81. //    node *n = create_node('N');
  82. //    node *o = create_node('0');
  83. //
  84. //    a->left = b;
  85. //    a->right = c;
  86. //    b->left = d;
  87. //    b->right = e;
  88. //    c->right = f;
  89. //    d->left = g;
  90. //    d->right = h;
  91. //    e->right = i;
  92. //    h->left = j;
  93. //    i->left = k;
  94. //    i->right = l;
  95. //    j->left = m;
  96. //    j->right = n;
  97. //    l->right = o;
  98. //
  99. //    return a;
  100. }
  101.  
  102.  
  103. void preOrder(node *root) {
  104.     if(root != NULL) {
  105.         printf("%c  ",root->data);
  106.         preOrder(root->left);
  107.         preOrder(root->right);
  108.     }
  109.  
  110. }
  111.  
  112.  
  113. void inOrder(node *root) {
  114.     if(root != NULL) {
  115.         inOrder(root->left);
  116.         printf("%c  ",root->data);
  117.         inOrder(root->right);
  118.     }
  119.  
  120. }
  121.  
  122. void postOrder(node *root) {
  123.     if(root != NULL) {
  124.         postOrder(root->left);
  125.         postOrder(root->right);
  126.         printf("%c  ",root->data);
  127.     }
  128. }
  129.  
  130.  
  131. void my_level_order(node* root, int lvl)
  132.     {
  133.         if (!root)  return;
  134.         if (lvl==1) {
  135.             printf("%c ",root->data);
  136.         }
  137.         else
  138.         {
  139.             my_level_order(root->left, lvl-1);
  140.             my_level_order(root->right, lvl-1);
  141.         }
  142.     }
  143.  
  144. void levelOrder(node * root) {
  145.     int h = deepth_tree(root);
  146.     for(int i = 1 ; i <= h ; i++) {
  147.         my_level_order(root,i);
  148.     }
  149. }
  150.  
  151.  
  152. void free_tree(node *root) {
  153.     if (root == NULL) {
  154.         return;
  155.     }
  156.     free_tree(root->left);
  157.     free_tree(root->right);
  158.     free(root);
  159. }
  160.  
  161. int countNodes(node *root) {
  162.     /*
  163.         dem so note cua cay
  164.     */
  165.     if( root == NULL) return 0;
  166.     else {
  167.         int ld = countNodes(root->left);
  168.         int rd = countNodes(root->right);
  169.         return 1 + ld + rd;
  170.     }
  171. }
  172.  
  173. int deepth_tree(node *root) {
  174.     /*
  175.         tinh do sau cau cay
  176.     */
  177.     if(root == NULL ) return 0;
  178.     else {
  179.         int ld = deepth_tree(root->left);
  180.         int rd = deepth_tree(root->right);
  181.         return 1 + ( ld > rd ? ld : rd) ;
  182.     }
  183. }
  184. int count_ = 0;
  185. int countLeaf(node *root) {
  186. /*
  187.     dem so nut la cua cay
  188. */
  189.     if( root == NULL) {
  190.         return 0;
  191.     }
  192.     else {
  193.         int ld = countLeaf(root->left);
  194.         int rd = countLeaf(root->right);
  195.         if( ld == 0 && rd == 0) {
  196.             count_ ++;
  197.         }
  198.     }
  199.     return count_;
  200. }
  201.  
  202. int count_1 = 0;
  203. int count_notLeaf(node *root) {
  204. /*
  205.     dem so nut khong la cua cay
  206. */
  207.     if( root == NULL || ( root->left == NULL && root->right == NULL)) {
  208.         return 0;
  209.     }
  210.     else {
  211.         int ld = count_notLeaf(root->left);
  212.         int rd = count_notLeaf(root->right);
  213.         return 1 + ld + rd;
  214.         }
  215.     return count_1;
  216. }
  217.  
  218.  
  219. void t1(node *root) {
  220.     if(root != NULL ) {
  221.         printf("%c",root->data);
  222.         t1(root->left);
  223.         t1(root->right);
  224.         printf("%c",root->data);
  225.     }
  226. }
  227.  
  228.  
  229. int evenleaf(node *root) {
  230.     /*
  231.         dem so leaf co gia tri chan
  232.     */
  233.  
  234.     if( root == NULL) {
  235.         return 0;
  236.     } 
  237.     else if ( root->left == NULL && root->right == NULL) {
  238.         if(root->data%2 == 0) {
  239. //            printf("%c ",root->data);
  240.             return 1;
  241.         } else return 0;
  242.     }
  243.     else {
  244. //        printf("%d ",root->data);
  245.         int ld = evenleaf(root->left);
  246.         int rd = evenleaf(root->right);
  247.         return ld + rd; 
  248.     }
  249. }
  250.  
  251. int countLeaf(node *root, int k) {
  252.     // dem so nut co gia tri lon hon k
  253.     if( root == NULL) {
  254.         return 0;
  255.     }
  256.     else {
  257. //        printf("%d ",root->data);
  258.         int ld = countLeaf(root->left,k);
  259.         int rd = countLeaf(root->right,k);
  260.         if(root->data > k) {
  261.             return 1 + ld + rd; 
  262.         } else return 0;
  263.  
  264.     }
  265. }
  266.  
  267. int bt_diag(node *root) {
  268.     /*
  269.     duong di dai nhat trong cay
  270.     */
  271.     if( root == NULL) {
  272.         return 0;
  273.     }
  274.     else {
  275.         int lheight = deepth_tree(root->left);
  276.         int rheight = deepth_tree(root->right);
  277.  
  278.         int l_bt_diag = bt_diag(root->left);
  279.         int r_bt_diag = bt_diag(root->right);
  280.  
  281.         return max(lheight + rheight + 1, max(l_bt_diag, r_bt_diag));
  282.     }
  283. }
  284.  
  285. int main() {
  286.     node *root = create_tree();
  287.     printf("Thu tu truoc\n");
  288.     preOrder(root);
  289.     printf("\n");
  290.     printf("Thu tu giua\n");
  291.     inOrder(root);
  292.     printf("\n");
  293.     printf("Thu tu sau\n");
  294.     postOrder(root);
  295.     printf("\n");
  296.     printf("Thu tu level\n");
  297.     levelOrder(root);
  298.     printf("\nNumber of node = %d ", countNodes(root));
  299.     printf("\nDeep tree = %d ", deepth_tree(root));
  300.     printf("\nNumber of leaf = %d ", countLeaf(root));
  301.     printf("\nNumber of not leaf = %d ", count_notLeaf(root));
  302.  
  303.     printf("\nExercise\n");
  304.     t1(root);
  305.  
  306.     printf("\nLeaf, data even = ");
  307.     printf("%d",evenleaf(root));
  308.  
  309.     printf("\nLeaf, data > k  : ");
  310.     printf("%d",countLeaf(root,69));
  311.  
  312.     printf("\nDiameter of tree : %d", bt_diag(root));
  313.     free_tree(root);
  314. }
Success #stdin #stdout 0s 4408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Thu tu truoc
H  D  B  A  C  F  E  K  J  L  
Thu tu giua
A  B  C  D  F  E  H  J  K  L  
Thu tu sau
A  C  B  E  F  D  J  L  K  H  
Thu tu level
H D K B F J L A C E 
Number of node = 10 
Deep tree = 4 
Number of leaf = 5 
Number of not leaf = 5 
Exercise
HDBAACCBFEEFDKJJLLKH
Leaf, data even = 2
Leaf, data > k  : 4
Diameter of tree : 6
https://ideone.com/RY2uq4
language:
C++ (gcc 8.3)
created:
4 years 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!