Исходник программы - обход двоичного дерева в ширину, поиск в двоичном дереве целых чисел на Си(C++)
Двоичное дерево поиска, состоящее из целых чисел. Вывод содержимого узлов дерева, обходя это дерево в ширину.
При обходе в ширину узлы посещаются уровень за уровнем (N-й уровень дерева - множество узлов с высотой N). Каждый уровень обходится слева направо.
Для реализации используется очередь.
Код на C++ dequeue - взять из очереди enqueue - поставить в очередь empty - возвращает 1, если очередь пуста, иначе - 0 q.enqueue(root); // корень в очередь while (! q.empty) { x = q.dequeue(); visit x; // посетить x if (! x.left.empty) // x.left - левое поддерево q.enqueue(x.left); if (! x.right.empty) // x.right - правое поддерево q.enqueue(x.right); }
Многочлен от одной переменной задается массивом вещественных коэффициентов и степенью многочлена.
Код на C++ #include <stdio.h> #include <string.h> #include <alloc.h> #include <conio.h> struct NODE { int info ; struct NODE *left, *right; }; #define QUEUE struct queue QUEUE { NODE *info ; QUEUE *next ; }; // QUEQUE // добавление в конец очереди void append( QUEUE **q, NODE *item ) { // указатель на текущий и предшествующий элементы QUEUE *current = *q, *prev = 0; QUEUE *new_node = (QUEUE * ) malloc (sizeof(QUEUE) ); new_node -> info = item; // информационная часть // адресная часть последнего элемента = 0 new_node -> next = 0; while(current) // пока не конец очереди { // переход на следующий элемент prev = current; current = current->next; } if (prev) prev->next = new_node; // если очередь не пуста else *q = new_node; // если пуста } // извлечение первого элемента NODE *take_out ( QUEUE **q, int *error) { QUEUE *old_item = *q ; // начало очереди NODE *old_info = 0 ; if ( *q ) // если очередь не пуста { old_info = old_item -> info; *q = ( *q ) -> next; free (old_item ); // уничтожение элемента *error = 0; } else *error = 1; return ( old_info ); } int isempty(QUEUE **q) { if(*q) return 0; // если очередь не пуста, возвращается 0 else return 1; } // BINARY TREE ------------------------------------------------------- NODE* insert( NODE *root, int x ) { if (root==0) { root = (NODE *) malloc (sizeof(NODE)); root->info = x ; root->left = root->right = 0 ; } else if (x<=root->info) root->left = insert ( root-> left, x ); else root->right = insert ( root-> right, x ); return root ; } // ------------------------------------------------------------------------ int istnempty(NODE* t) { if (t) return 1; else return 0; } void display( NODE *p ) { QUEUE *q = 0; int e; append( &q, p); while (!isempty(&q)) { p = take_out(&q, &e); printf(" %-7d ", p->info ); if (istnempty(p->left)) append( &q, p->left ); if (istnempty(p->right)) append( &q, p->right ); } } NODE* find(NODE* t, int x) { if(t) { if(x==t->info) return t; else if (x<t->info) return find(t->left,x); else return find(t->right,x); } else return 0; } NODE* remove(NODE* root, int x) { NODE* b; if (root==0) return 0; if (x==root->info) { if (root->left==0) { b=root->right; delete root; return b; } b = root->left; while (b->right) b=b->right; b->right=root->right; return root->left; } if (x<=root->info) root->left = remove(root->left,x); else root->right = remove(root->right,x); return root; } main() { clrscr(); NODE *tree = 0; tree = insert(tree, 2); tree = insert(tree, 1); tree = insert(tree, 3); tree = insert(tree, 5); tree = insert(tree, 2); tree = insert(tree, 6); tree = insert(tree, 4); display(tree); getch(); }
|
Выход