Guest User

Untitled

a guest
May 19th, 2019
59
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct tree
  5. {
  6. int a; // данные
  7. int *left; // левый сын
  8. int *right; // правый сын
  9. } TREE;
  10.  
  11. TREE *add_to_tree(TREE *root, int new_value)
  12. {
  13. if (root==NULL) // если нет сыновей - создаем новый элемент
  14. {
  15. root = (TREE*)malloc(sizeof(TREE));
  16. root->a = new_value;
  17. root->left = root->right = 0;
  18. return root;
  19. }
  20. if (root->a < new_value) // добавлем ветвь
  21. root->right = add_to_tree(root->right, new_value);
  22. else
  23. root->left = add_to_tree(root->left, new_value);
  24. return root;
  25. }
  26.  
  27. void tree_to_array(TREE *root, int a[]) // процедура заполнения массива
  28. {
  29. static max2=0; // счетчик элементов нового массива
  30. if (root==NULL) return; // условие окончания - нет сыновей
  31. tree_to_array(root->left, a); // обход левого поддерева
  32. a[max2++] = root->a;
  33. tree_to_array(root->right, a); // обход правого поддерева
  34. free(root);
  35. }
  36.  
  37. void sort_tree(int a[], int elem_total) // собственно сортировка
  38. {
  39. TREE *root;
  40. int i;
  41.  
  42. root = NULL;
  43. for (i=0; i<elem_total; i++) // проход массива и заполнение дерева
  44. root = add_to_tree(root, a[i]);
  45. tree_to_array(root, a); // заполнение массива
  46. }
  47. /* тестовая программа */
  48. void main() {
  49. int i;
  50. /* Это будем сортировать */
  51. int a[19]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 ,456, 5 ,78,99,12345};
  52.  
  53. sort_tree(a, 19);
  54.  
  55. printf("sorted array:\n");
  56. for (i=0;i<19;i++) printf("%d ",a[i]);
  57. }
RAW Paste Data