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

Двоичное дерево, для всех узлов которого 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++
#include <conio.h>
#include <iostream.h>
 
//обход, двоичное/бинарное дерево поиска в ширину используя очередь
//структура элемента дерева
typedef struct tagTREE
	       { int inf;
		 tagTREE *left;
		 tagTREE *right;
	       }TREE;
 
//структура элемента очереди
typedef struct tagQUEUE
	       { TREE *tr;
		 tagQUEUE *next;
	       }QUEUE;
 
QUEUE *q;
//функция уничтожения очереди
void DestroyQueue()
{ QUEUE *prev;
  if (q != NULL)
     { prev = q;
       while(q->next != NULL)
	    { q = q->next;
	      delete prev;
	      prev = q;
	    }
       delete prev;
     }
}
//функция добавления элемента в очередь
void Put(TREE *a)
{ QUEUE *n, *prev;
  prev = q;
  n = new QUEUE;
  n->tr = a;
  n->next = NULL;
  if (q != NULL)
     { while(prev->next != NULL)
	    prev = prev->next;
       prev->next = n;
     }
  else
     q = n;
}
//функция удаления элемента из очередь
TREE* Get()
{ QUEUE *prev;
  TREE *a;
  if (q != NULL)
     { prev = q;
       a = q->tr;
       if (q->next != NULL)
	  q = q->next;
       else
	  q = NULL;
       delete prev;
       return a;
     }
  else
     return NULL;
}
//функция проверки на пустоту очереди
int IsEmpty(QUEUE *q)
{ if (q == NULL) return 1;
  else return NULL;
}
//-----------------------------------------------
//функция добавления элемента в дерево
TREE* Insert(TREE *root, int x)
{ if (root == NULL)
     { root = new TREE;
       root->inf = x;
       root->left = root->right = NULL;
     }
  else
     { if (x <= root->inf)
	  root->left = Insert(root->left, x);
       else
	  root->right = Insert(root->right, x);
     }
  return root;
}
//функция удаления элемента из дерева
TREE* Remove(TREE *root, int x)
{ TREE *t;
  if (root == NULL) return 0;
  if (x == root->inf)
     { if (root->left == NULL)
	  { t = root->right;
	    delete root;
	    return t;
	  }
       t = root->left;
       while(t->right) t = t->right;
       t->right = root->right;
       return root->left;
     }
  if (x <= root->inf)
     root->left = Remove(root->left, x);
  else
     root->right = Remove(root->right, x);
  return root;
}
//функция вывода дерева на экран
//обходя дерево в ширину
void ShowTree(TREE *root)
{ q = NULL;
  TREE *t;
  Put(root);
  while(!IsEmpty(q))
       { t = Get();
	 if (t->left != NULL)
	    Put(t->left);
	 if (t->right != NULL)
	    Put(t->right);
	 cout<<t->inf<<" ";
       }
  cout<<endl;
}
//обход, двоичное/бинарное дерево поиска в ширину используя очередь
//функция удаления всего дерева
TREE* DestroyTree(TREE *root)
{ if (root)
     { if (root->left != NULL)
	  root->left = DestroyTree(root->left);
       if (root->right != NULL)
	  root->right = DestroyTree(root->right);
       delete root;
     }
  return NULL;
}
 
//главная функция
void main(void)
{ TREE *mytree = NULL; //указатель на дерево
  int i, mas[10] = {5, 34, 8, 10, 15, 1, 0, 21, -5, 100};
  clrscr();  //очищаем экран
  //добавляем элементы в дерево
  for (i = 0; i<10; i++)
      mytree = Insert(mytree, mas[i]);
  cout<<"Дерево:"<<endl;
  ShowTree(mytree);      //выводим дерево
  //удаляем элементы
  mytree = Remove(mytree, 1);
  mytree = Remove(mytree, -5);
  cout<<"Дерево после удаления элементов 1 и -5:"<<endl;
  ShowTree(mytree);    //выводим дерево
}
При использовании обязательна ссылка на http://DMTSoft.ru

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

Дерево:

5 1 34 0 8 100 -5 10 15 21

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

5 0 34 8 100 10 15 21