Используя стек обойти бинарное/двоичное дерево поиска в глубину. Язык программирования Си.


Добавил:DMT
Дата создания:7 мая 2008, 21:46
Дата обновления:7 мая 2008, 21:46
Просмотров:9376 последний сегодня, 23:34
Комментариев: 0
Используя стек обойти бинарное/двоичное дерево поиска в глубину на Си
Текст программы
Код на C++
  1. #include <stdio.h>
  2. #include <conio.h>
  3. #include <string.h>
  4. #include <alloc.h>
  5.  
  6. #define pop() stx[--deep]
  7. #define push(x) stx[deep++] = x
  8.  
  9. struct NODE
  10. {
  11. int info ;
  12. struct NODE *left, *right;
  13. };
  14. NODE *s1 = 0, *s2 = 0 ;
  15.  
  16. int deep = 0;
  17. NODE *stx[1000];
  18.  
  19. NODE* insert(NODE *root, int x)
  20. {
  21. if (root==0)
  22. {
  23. root = (NODE *) malloc (sizeof(NODE));
  24. root->info = x ;
  25. root->left = root->right = 0 ;
  26. }
  27. else
  28. if (x <= root->info)
  29. root->left = insert(root->left, x);
  30. else
  31. root->right = insert(root->right, x);
  32. return root ;
  33. }
  34.  
  35. void display( NODE *p )
  36. {
  37. push(p);
  38. while (deep)
  39. {
  40. p = pop();
  41. printf(" %-7d ", p->info);
  42. if (p->right)
  43. push(p->right);
  44. if (p->left)
  45. push(p->left);
  46. }
  47. }
  48.  
  49. //Используя стек обойти бинарное/двоичное дерево поиска в глубину
  50. NODE* find(NODE* t, int x)
  51. {
  52. if(t)
  53. {
  54. if(x == t->info)
  55. return t;
  56. else
  57. if (x < t->info)
  58. return find(t->left,x);
  59. else
  60. return find(t->right,x);
  61. }
  62. else
  63. return 0;
  64. }
  65.  
  66. NODE* remove(NODE* root, int x)
  67. {
  68. NODE* b;
  69. if (root==0)
  70. return 0;
  71. if (x==root->info)
  72. {
  73. if (root->left==0)
  74. {
  75. b=root->right;
  76. delete root;
  77. return b;
  78. }
  79. b = root->left;
  80. while (b->right)
  81. b=b->right;
  82. b->right=root->right;
  83. return root->left;
  84. }
  85. if (x<=root->info)
  86. root->left = remove(root->left,x);
  87. else
  88. root->right = remove(root->right,x);
  89. return root;
  90. }
  91.  
  92. void main()
  93. {
  94. clrscr() ;
  95. s1 = insert ( s1, 2) ;
  96. s1 = insert ( s1, 1) ;
  97. s1 = insert ( s1, 3) ;
  98. puts("\n s1 = ");
  99. display (s1) ;
  100. s2 = insert ( s1, 1) ;
  101. s2 = insert ( s1, 9) ;
  102. puts("\n s2 = ");
  103. display (s1) ;
  104. getch() ;
  105. }
При использовании обязательна ссылка на http://DMTSoft.ru
up