Исходник программы - обход двоичного дерева в ширину, поиск в двоичном дереве целых чисел на Си(C++)


Добавил:DMT
Дата создания:30 апреля 2008, 23:06
Дата обновления:30 апреля 2008, 23:06
Просмотров:14798 последний сегодня, 17:16
Комментариев: 1
Исходник программы - обход двоичного дерева в ширину, поиск в двоичном дереве целых чисел на Си(C++)
Двоичное дерево поиска, состоящее из целых чисел. Вывод содержимого узлов дерева, обходя это дерево в ширину.
При обходе в ширину узлы посещаются уровень за уровнем (N-й уровень дерева - множество узлов с высотой N). Каждый уровень обходится слева направо.
Для реализации используется очередь.
Код на C++
  1. dequeue - взять из очереди
  2. enqueue - поставить в очередь
  3. empty - возвращает 1, если очередь пуста, иначе - 0
  4. q.enqueue(root); // корень в очередь
  5. while (! q.empty) {
  6. x = q.dequeue();
  7. visit x; // посетить x
  8. if (! x.left.empty) // x.left - левое поддерево
  9. q.enqueue(x.left);
  10. if (! x.right.empty) // x.right - правое поддерево
  11. q.enqueue(x.right);
  12. }
При использовании обязательна ссылка на http://DMTSoft.ru

Многочлен от одной переменной задается массивом вещественных коэффициентов и степенью многочлена.
Код на C++
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <alloc.h>
  4. #include <conio.h>
  5.  
  6. struct NODE
  7. {
  8. int info ;
  9. struct NODE *left, *right;
  10. };
  11.  
  12. #define QUEUE struct queue
  13.  
  14. QUEUE
  15. {
  16. NODE *info ;
  17. QUEUE *next ;
  18. };
  19.  
  20. // QUEQUE
  21.  
  22. // добавление в конец очереди
  23. void append( QUEUE **q, NODE *item )
  24. {
  25. // указатель на текущий и предшествующий элементы
  26. QUEUE *current = *q, *prev = 0;
  27.  
  28. QUEUE *new_node = (QUEUE * ) malloc (sizeof(QUEUE) );
  29. new_node -> info = item; // информационная часть
  30. // адресная часть последнего элемента = 0
  31. new_node -> next = 0;
  32.  
  33. while(current) // пока не конец очереди
  34. {
  35. // переход на следующий элемент
  36. prev = current; current = current->next;
  37. }
  38. if (prev) prev->next = new_node; // если очередь не пуста
  39. else *q = new_node; // если пуста
  40. }
  41.  
  42. // извлечение первого элемента
  43. NODE *take_out ( QUEUE **q, int *error)
  44. {
  45. QUEUE *old_item = *q ; // начало очереди
  46. NODE *old_info = 0 ;
  47. if ( *q ) // если очередь не пуста
  48. {
  49. old_info = old_item -> info;
  50. *q = ( *q ) -> next;
  51. free (old_item ); // уничтожение элемента
  52. *error = 0;
  53. } else *error = 1;
  54. return ( old_info );
  55. }
  56.  
  57. int isempty(QUEUE **q)
  58. {
  59. if(*q) return 0; // если очередь не пуста, возвращается 0
  60. else return 1;
  61. }
  62.  
  63. // BINARY TREE -------------------------------------------------------
  64.  
  65. NODE* insert( NODE *root, int x )
  66. {
  67. if (root==0)
  68. {
  69. root = (NODE *) malloc (sizeof(NODE));
  70. root->info = x ;
  71. root->left = root->right = 0 ;
  72. }
  73. else if (x<=root->info) root->left = insert ( root-> left, x );
  74. else root->right = insert ( root-> right, x );
  75. return root ;
  76. }
  77. // ------------------------------------------------------------------------
  78.  
  79. int istnempty(NODE* t)
  80. {
  81. if (t) return 1;
  82. else return 0;
  83. }
  84.  
  85. void display( NODE *p )
  86. {
  87. QUEUE *q = 0;
  88. int e;
  89. append( &q, p);
  90. while (!isempty(&q))
  91. {
  92. p = take_out(&q, &e);
  93. printf(" %-7d ", p->info );
  94.  
  95. if (istnempty(p->left))
  96. append( &q, p->left );
  97. if (istnempty(p->right))
  98. append( &q, p->right );
  99. }
  100. }
  101.  
  102. NODE* find(NODE* t, int x)
  103. {
  104. if(t)
  105. {
  106. if(x==t->info) return t;
  107. else if (x<t->info) return find(t->left,x);
  108. else return find(t->right,x);
  109. }
  110. else return 0;
  111. }
  112.  
  113. NODE* remove(NODE* root, int x)
  114. {
  115. NODE* b;
  116. if (root==0) return 0;
  117. if (x==root->info)
  118. {
  119. if (root->left==0)
  120. {
  121. b=root->right; delete root; return b;
  122. }
  123. b = root->left;
  124. while (b->right) b=b->right;
  125. b->right=root->right;
  126. return root->left;
  127. }
  128. if (x<=root->info) root->left = remove(root->left,x);
  129. else root->right = remove(root->right,x);
  130. return root;
  131. }
  132.  
  133. main()
  134. {
  135. clrscr();
  136. NODE *tree = 0;
  137. tree = insert(tree, 2);
  138. tree = insert(tree, 1);
  139. tree = insert(tree, 3);
  140. tree = insert(tree, 5);
  141. tree = insert(tree, 2);
  142. tree = insert(tree, 6);
  143. tree = insert(tree, 4);
  144. display(tree);
  145. getch();
  146. }
При использовании обязательна ссылка на http://DMTSoft.ru
up