Вывести число вершин n-го уровня (Бинарное дерево поиска)
всем привет, дано такое задание:
Напишите программу, которая формирует бинарное дерево поиска, выводит построенное дерево на экран и подсчитывает число вершин на n-ом уровне сформированного дерева. Корень считать вершиной 0-го уровня. Обход дерева выполните с помощью не рекурсивного алгоритма. Данные могут вводиться с клавиатуры, из файла или генерироваться с помощью генератора случайных чисел. Перед завершением работы программы освободить занимаемую динамическую память. Для этого используйте поэлементное удаление элементов динамической структуры данных.
пока пытаюсь реализовать удаление поэлементное
уже мучаюсь целый день, и не могу понять в чем проблема, почему строчка 87 while ( cin >>dig2 ) TRoot=Del(TRoot, dig2);
неправильно срабатывает. не дает ввести элементы которые надо удалить, а просто пропускает, подскажите в чем дело??
заранее спасибо, вот мой код:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
#include #include #include #include #include #include using namespace std; struct BSTree { int key; BSTree *Left; BSTree *Right; }; BSTree *TRoot=NULL; int lvl=0; BSTree* AddTree(BSTree *t, int k) { if (t == NULL) { t = new BSTree; t->Left = NULL; t->Right = NULL; t->key = k; } else if(t->key==k) return t; else { if (k > t->key ) t->Right=AddTree(t->Right, k); else t->Left=AddTree(t->Left, k); } return t; } void TreeShow(BSTree *t, int lvl ) { int tab = 5; if (t == NULL) cout "Derevo pusto \n"; else { if (t->Right != NULL) TreeShow(t->Right, lvl+1); cout setw(tab*lvl) t->key endl; if (t->Left != NULL) TreeShow(t->Left, lvl+1); } } BSTree* Del(BSTree* T, int k) { BSTree *P, *v; if (T!=NULL) cout "this element in the tree there!" endl; else if (k T->key) T->Left = Del(T->Left, k); else if (k > T-> key) T->Right = Del(T->Right, k); else {P = T; if (T->Right!=NULL) T = T->Left; // случай 1 else if (T->Left!=NULL) T = T->Right; // случай 1 else // случай 2 { v = T->Left; if (v->Right) { while (v->Right->Right) v = v->Right; T->key = v->Right->key; P = v->Right; v->Right = v->Right->Left; } else { T->key = v->key; P = v; T->Left=T->Left->Left; } } free(P); } return T; } void main() { int dig, dig2; cout "Enter the numbers, for the end of any character other than numbers:\n"; while ( cin >>dig ) TRoot=AddTree(TRoot, dig); cout endl; TreeShow(TRoot, lvl); cout "Enter number of items you want to delete, for the end of any character other than numbers:\n"; while ( cin >>dig2 ) TRoot=Del(TRoot, dig2); coutendl; lvl=0; TreeShow(TRoot, lvl); system("PAUSE"); } Источник
Вывести количество вершин дерева, являющихся левыми дочерними вершинами
Дан указатель P на корень непустого дерева. Вывести количество вершин дерева, являющихся левыми дочерними вершинами(корень дерева не учитывать).
Есть программа, нужно дописать функцию подсчета левых дочерних вершин (всех тех вершин, чтобы дойти до которых, нужно свернуть налево)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
#include using namespace std; struct Tree { float data; Tree *left; Tree *right; }; Tree *BalanceTree(Tree *root, int n) { if (n==0) { root = 0; return root; } int nl = n/2; int nr = n-nl-1; Tree *p = new Tree; cin >> p->data; p->left = BalanceTree(p->left, nl); p->right = BalanceTree(p->right, nr); root = p; return root; } void Print(Tree *root, int l) { if (root) { Print(root->left, l+5); for (int i = 0; i l; i++) cout <" "; cout - >data ; Print(root->right, l+5); } } int main() { Tree *root=0; int n; float g,b; cout <"Enter the count of elements: "; cin >> n; root = BalanceTree(root, n); Print(root, n); cout ; g=0; kolichestvo(root, g); cout <"Kolichestvo: " ; return 0; } Источник
Вывести количество вершин в бинарном дереве
Подсчет вершин в бинарном дереве
Здравствуйте,помогите написать функцию ,которая подсчитывает число вершин на N-ом уровне бинарного.
Количество листов в бинарном дереве
дан указатель р1 на корень непустого дерева. найти количество листов void print (PNode Tree, int.
Количество листьев в бинарном дереве
Задача: Найти количество листьев в дереве. Собственно ввод и вывод дерева есть: #include.
Бинарные деревья: Посчитать количество дедов в бинарном дереве
Функция выбрасывает исключение. Что здесь неправильно,и как написать правильно? int.
Сообщение было отмечено Лена Есеева как решение
Решение
Сообщение от Лена Есеева 
Нужно найти количество вершин в бинарном дереве, но у меня в коде где-то ошибка, потому что выводится неправильное число.
//подсчет количества вершин size_t nodes_count(const Node *tree) { return tree? 1 + nodes_count(tree->l) + nodes_count(tree->r): 0; }
Источник
Как найти количество вершин на заданном уровне бинарного дерева ( поиска )
Хочу рассмотреть следующее двоичное дерево ( в данном случае — поисковое ):
Рисунок — обыкновенное двоичное поисковое дерево
➡ Для начала надо понять, как нумеруются уровни дерева, на каком уровне лежит корневая вершина и т.п.
Следующая картинка дает ответы на подобные вопросы:
Рисунок — уровни двоичного дерева
Из рисунка видно, что корневая вершина лежит на первом уровне. Иногда в теории алгоритмов нумерацию уровней бинарного дерева начинают с $0$. По-большему счету это непринципиально и мало влияет на логику алгоритма определения количества узлов на заданном уровне.
Визуально посчитаем количество вершин, а также их ключевые значения на каждом уровне рассматриваемого бинарного дерева и сведем информацию в сводную таблицу:
| # уровня | Количество вершин | Значения вершин |
| $1$ | $1$ | $52$ |
| $2$ | $2$ | $45,\ 125$ |
| $3$ | $3$ | $24,\ 88,\ 154$ |
| $4$ | $4$ | $61,\ 100,\ 132,\ 167$ |
| $5$ | $3$ | $82,\ 102,\ 155$ |
| $6$ | $2$ | $74,\ 118$ |
| $7$ | $0$ | $—$ |
💡 Но хочу напомнить, что моя задача — написать программную функцию, которая вычисляет количество вершин на заданном ( $N$-ом ) уровне двоичного дерева.
То есть меня мало интересуют значения вершин ( ключевые данные ), а лишь их количество. Из этого следует, что мне не важно, является бинарное дерево поисковым или нет. Поэтому сейчас покажу анонимное двоичное дерево аналогичной топологии:
Рисунок — уровни анонимного двоичного дерева ( поиска )
Например, пользователь «говорит», что хочет узнать количество вершин на $5$-ом уровне. Моя программная функция должна в качестве результата выдать ответ $3$, так как на уровне #$5$ находится три вершины:
Рисунок — на уровне #$5$ находится $3$ вершины
➡ Если пользователь сделает запрос по номеру уровня, которого не существует в двоичном дереве, то программа должна выдать ответ $0$. Например, уровня #17 в анализируемом анонимном двоичном дереве нет физически, поэтому и узлов на этом уровне также нет физически.
Кстати, в одной из своих статей-шпаргалок я показывал, как реализовать поуровневый вывод вершин бинарного дерева ( поиска ). Мне пришлось задействовать классическую структуру данных «Очередь» ( Queue, FIFO — First-In, First-Out ). Весь процесс был построен итеративно, то есть без рекурсии. В текущем алгоритме ( нахождения количества узлов на заданном уровне ) мне не придется прибегать к вспомогательным структурам данных и, думаю, все реализую рекурсивно в одной компактной функции.
💡 Основная идея алгоритма определения количества узлов двоичного дерева ( поиска ) на заданном ( $N$-ом ) уровне: так как до каждой вершины дерева существует строго один путь от корневой вершины ( корень лежит на уровне #$1$ ), то я буду рекурсивно перебирать все пути до тех пор, пока не будет достигнут заданный уровень или NULL.
Под перебором я понимаю стандартный обход двоичного дерева. Всего их существует $6$ штук. Я выберу LKP-обход ( симметричный левый, левый-корень-правый ).
Если в процессе обхода дерева я вышел на заданный уровень, то дальше спускаться по дереву смысла нет, поэтому это будет окончанием рекурсивного спуска для текущего пути и в качестве ответа верну из функции $1$.
В результате закодировал на языке «чистый» Си следующую функцию, а также поставил детальные комментарии к каждой строке кода:
Источник
Бинарное дерево. Вывести количество вершин
Дан адрес P1 записи типа TNode — корня дерева. Эта запись связана полями Left и Right с другими записями того же типа (дочерними вершинами), они, в свою очередь, — со своими дочерними вершинами, и так далее до записей, поля Left и Right которых равны nil (у некоторых вершин может быть равно nil одно из полей — Left или Right) и число K. Вывести количество вершин дерева, значение которых равно K.
Входные значения n и к — целое, количество узлов дерева и число К соответственно, ai — целые, значение в узлах дерева, разделенные пробелом, где i < n.
Выходные: количество вершин — целое.
Есть что-то похожее. Помогите подстроить под условие.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
#include #include #include using namespace std; //структура эл-та дерева struct Node { int info; //значение Node *left; //левая дочерняя вершина Node *right; //правая дочерняя вершина Node *parent; //родительская вершина }; //ф-ция построения дерева (алг. лабы 32) //параметры: ссылка на файл, кол-во вершин, указатель на родительскую в-ну, ссылка на указатель на текущий эл-т void BuildTree(ifstream &f, int N, Node* Parent, Node* &Current) { Current = new Node; //создаем тек. вер-ну f >> Current->info; //читаем очередное значение из файла Current->left = NULL; //указатель на левую в-ну = NULL Current->right = NULL; //на правую = NULL Current->parent = Parent; //на родительскую соответствует переданному в параметрах //если нужно добавлять левую в-ну if (N>1) //добавляем в соответствии с алгоритмом, текущая в-на является для добавляемой родительской BuildTree(f, N/2, Current, Current->left); //аналогично для правой if (N>2) BuildTree(f, N-1-N/2, Current, Current->right); } //вывод указателей на эл-ты дерева //параметр: указатель на тек в-ну void PrintNodePointers(Node* Current) { //вывести указатель на тек. в-ну cout Current endl; //если есть левая, то вывести на нее указатель if (Current->left != NULL) PrintNodePointers(Current->left); //аналогично для правой if (Current->right != NULL) PrintNodePointers(Current->right); } //выводим информацию о вершине void PrintVertexData(Node* Vertex) { cout "Left: "; //если существует левая в-на, то выводим на нее указатель, иначе пишнм "nil" (Vertex->left != NULL) ? cout Vertex->left : cout "nil"; cout endl; cout "Right: "; //аналогично для правой (Vertex->right != NULL) ? cout Vertex->right : cout "nil"; cout endl; cout "Parent: "; //аналогично для родительской (Vertex->parent != NULL) ? cout Vertex->parent : cout "nil"; cout endl; cout "Sister: "; //если существут родительская в-на, то возможно существует "сестра" if (Vertex->parent != NULL) { //если текущая в-на является левой по отношению к родительской, то ее "сестра" - правая if (Vertex->parent->left == Vertex) //если правая "сестра" существует, то вывести на нее указатель, иначе "nil" (Vertex->parent->right != NULL) ? cout Vertex->parent->right : cout "nil"; else //иначе "сестра" - левая, если существует, то вывести на нее указатель (Vertex->parent->left != NULL) ? cout Vertex->parent->left : cout "nil"; } else cout "nil"; cout endl; } //ф-ция печати дерева //параметры: вершина, уровень в-ны в дереве void print_Tree(Node * p,int level) { //если указатель на текущую в-ну не NULL if(p) { //напечатать левую дочернюю в-ну print_Tree(p->left,level + 1); //сместить курсор до позиции соответствуещей уровню в-ны for(int i = 0;i level;i++) cout" "; //вывести значение в-ны cout p->info endl; //напечатать правую в-ну print_Tree(p->right,level + 1); } } int main() { Node *first=NULL; //указатель на корневой эл-т cout "Enter file name\n"; char fname[100]; //имя файла cin.getline(fname, 100); //читаем имя файла ifstream f; f.open(fname, ios::in); //открыть файл для чтения int N; f >> N; //читаем число в-н дерева BuildTree(f, N, NULL, first); //строим дерево, родительская в-на корневого эл-та не существует print_Tree(first, 0); //печать дерева PrintNodePointers(first); //выводим все указатели на эл-ты дерева cout "Enter vertex pointer from list\n"; //читаем указатель на эл-т дерева как целое число в HEX формате cin >> hex >> N; //выводим информацию в-ны. в параметрах приводим тип int к Node* (целое число - это адрес в памяти) PrintVertexData((Node*)N); //ждать нажатия кнопки завершения _getch(); return 0; } Источник