Исходник на Си: Организовать двоичное/бинарное дерево поиска, состоящее из целых чисел. Обход дерева в ширину используя очередь.


Добавил:DMT
Дата создания:7 мая 2008, 21:57
Дата обновления:7 мая 2008, 21:57
Просмотров:22147 последний вчера, 11:32
Комментариев: 0

Организовать двоичное/бинарное дерево поиска, состоящее из целых чисел. Вывести содержимое его узлов, обходя это дерево в ширину.

Двоичное дерево, для всех узлов которого v значения информационной части info ( v ) этих узлов удовлетворяют соотношению:

info ( левый сын v ) <= info ( v ) <= info ( правый сын v ), называется деревом поиска .

Определим структуру элемента дерева:

typedef struct tagTREE

{

int inf;

tagTREE *left;

tagTREE *right;

}TREE;

 

Также определим операции для работы с деревом:

TREE* Insert(TREE *root, char *s); // добавление элемента

TREE* Remove(TREE *root, char *s); // удаление элемента

TREE* Find(TREE *root, char *s); // поиск элемента

void ShowTree ( TREE * root ); //вывод всего дерева на экран

Добавление, поиск и удаление элементов производятся рекурсивно.

В подпрограмме добавления элемента число сравнивается со значением в корне. Если оно не больше, то подпрограмма вызывается для добавления этого числа к левому поддереву, если больше, то к правому. В результате, происходит спуск к пустому поддереву, вместо которого формируется новый элемент и добавляется к дереву. Аналогично работает подпрограмма поиска.

Подпрограмма симметричного обхода вызывает себя рекурсивно для левого поддерева, затем выводит значение в узле и вызывает себя для правого поддерева.

В подпрограмме удаления элемента x сначала находится узел, содержащий x . Теперь, если нет левого поддерева, то этот узел уничтожается и вместо него ставится корень правого поддерева. В противном случае производится спуск вправо по левому поддереву, до тех пор, пока он возможен. В результате получаем узел, не имеющий правого поддерева. Этот узел ставится на место найденного элемента x , а его левое поддерево становится на старое место этого узла.

Прохождение вершин дерева, при котором смежные вершины запоминаются в очередь, называются обходом вершин дерева в ширину .

Определим структуру элемента очереди, как состоящую из информационной части и указателя на следующий элемент очереди. Для последнего элемента указатель на следующий элемент будет равен NULL .

typedef struct tagQUEUE

{

int inf;

tagQUEUE *next;

}QUEUE;

Также определим операции для работы с очередью:

void Put ( TREE * a ); //функция добавления элемента в очередь

TREE * Get (); //функция удаления элемента из очередь

 

Для того, чтобы добавить элемент в очередь, надо сначала найти последний элемент и затем изменить его указатель, равный NULL , адресом добавляемого элемента.

При удалении элемента из очереди, удаляется первый элемент очереди, а началом очереди назначается следующий за первый элемент очереди.


Текст программы
Код на C++
  1. #include <conio.h>
  2. #include <iostream.h>
  3.  
  4. //обход, двоичное/бинарное дерево поиска в ширину используя очередь
  5. //структура элемента дерева
  6. typedef struct tagTREE
  7. { int inf;
  8. tagTREE *left;
  9. tagTREE *right;
  10. }TREE;
  11.  
  12. //структура элемента очереди
  13. typedef struct tagQUEUE
  14. { TREE *tr;
  15. tagQUEUE *next;
  16. }QUEUE;
  17.  
  18. QUEUE *q;
  19. //функция уничтожения очереди
  20. void DestroyQueue()
  21. { QUEUE *prev;
  22. if (q != NULL)
  23. { prev = q;
  24. while(q->next != NULL)
  25. { q = q->next;
  26. delete prev;
  27. prev = q;
  28. }
  29. delete prev;
  30. }
  31. }
  32. //функция добавления элемента в очередь
  33. void Put(TREE *a)
  34. { QUEUE *n, *prev;
  35. prev = q;
  36. n = new QUEUE;
  37. n->tr = a;
  38. n->next = NULL;
  39. if (q != NULL)
  40. { while(prev->next != NULL)
  41. prev = prev->next;
  42. prev->next = n;
  43. }
  44. else
  45. q = n;
  46. }
  47. //функция удаления элемента из очередь
  48. TREE* Get()
  49. { QUEUE *prev;
  50. TREE *a;
  51. if (q != NULL)
  52. { prev = q;
  53. a = q->tr;
  54. if (q->next != NULL)
  55. q = q->next;
  56. else
  57. q = NULL;
  58. delete prev;
  59. return a;
  60. }
  61. else
  62. return NULL;
  63. }
  64. //функция проверки на пустоту очереди
  65. int IsEmpty(QUEUE *q)
  66. { if (q == NULL) return 1;
  67. else return NULL;
  68. }
  69. //-----------------------------------------------
  70. //функция добавления элемента в дерево
  71. TREE* Insert(TREE *root, int x)
  72. { if (root == NULL)
  73. { root = new TREE;
  74. root->inf = x;
  75. root->left = root->right = NULL;
  76. }
  77. else
  78. { if (x <= root->inf)
  79. root->left = Insert(root->left, x);
  80. else
  81. root->right = Insert(root->right, x);
  82. }
  83. return root;
  84. }
  85. //функция удаления элемента из дерева
  86. TREE* Remove(TREE *root, int x)
  87. { TREE *t;
  88. if (root == NULL) return 0;
  89. if (x == root->inf)
  90. { if (root->left == NULL)
  91. { t = root->right;
  92. delete root;
  93. return t;
  94. }
  95. t = root->left;
  96. while(t->right) t = t->right;
  97. t->right = root->right;
  98. return root->left;
  99. }
  100. if (x <= root->inf)
  101. root->left = Remove(root->left, x);
  102. else
  103. root->right = Remove(root->right, x);
  104. return root;
  105. }
  106. //функция вывода дерева на экран
  107. //обходя дерево в ширину
  108. void ShowTree(TREE *root)
  109. { q = NULL;
  110. TREE *t;
  111. Put(root);
  112. while(!IsEmpty(q))
  113. { t = Get();
  114. if (t->left != NULL)
  115. Put(t->left);
  116. if (t->right != NULL)
  117. Put(t->right);
  118. cout<<t->inf<<" ";
  119. }
  120. cout<<endl;
  121. }
  122. //обход, двоичное/бинарное дерево поиска в ширину используя очередь
  123. //функция удаления всего дерева
  124. TREE* DestroyTree(TREE *root)
  125. { if (root)
  126. { if (root->left != NULL)
  127. root->left = DestroyTree(root->left);
  128. if (root->right != NULL)
  129. root->right = DestroyTree(root->right);
  130. delete root;
  131. }
  132. return NULL;
  133. }
  134.  
  135. //главная функция
  136. void main(void)
  137. { TREE *mytree = NULL; //указатель на дерево
  138. int i, mas[10] = {5, 34, 8, 10, 15, 1, 0, 21, -5, 100};
  139. clrscr(); //очищаем экран
  140. //добавляем элементы в дерево
  141. for (i = 0; i<10; i++)
  142. mytree = Insert(mytree, mas[i]);
  143. cout<<"Дерево:"<<endl;
  144. ShowTree(mytree); //выводим дерево
  145. //удаляем элементы
  146. mytree = Remove(mytree, 1);
  147. mytree = Remove(mytree, -5);
  148. cout<<"Дерево после удаления элементов 1 и -5:"<<endl;
  149. ShowTree(mytree); //выводим дерево
  150. }
При использовании обязательна ссылка на http://DMTSoft.ru

 

Результат выполнения программы:

Дерево:

5 1 34 0 8 100 -5 10 15 21

Дерево после удаления элементов 1 и -5:

5 0 34 8 100 10 15 21

up