Дерева от него целые числа

Линейные структуры данных

(англ. ) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Стек должен поддерживать следующие операции: push Добавить (положить) в конец стека новый элемент
pop Извлечь из стека последний элемент
top Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в стеке
clear Очистить стек (удалить из него все элементы)

Стек можно хранить двумя способами: либо массивом некоторого фиксированного размера, либо при помощи ссылочной реализации.

Структура данных Stack

Для работы со стеком создадим структуру данных Stack . Поскольку элементами стека могут быть любые данные (числа, строки и т.д.), то эта структура будет шаблоном (template) над произвольным типом данных T . Вот каким должен быть интерфейс стека:

Реализация на базе массива

В простейшем случае для хранения элементов стека можно использовать массив. Элементы стека будем класть в начало стека. Заведем два поля в структуре: поле m_data — массив элементов стека и m_size — число элементов в стеке. Объявим их, как приватные члены класса.

private: T m_data[MAXSIZE]; int m_size;

Значение m_size инициализируем в конструкторе:

Добавление элементов в стек заключается в увеличении поля m_size и записи элемента в массив m_data :

Оставшиеся методы реализовать также просто:

T top() < return m_data[m_size - 1]; >T pop() < --m_size; return m_data[m_size]; >void size() < return m_size; >void clear()

Массив переменного размера

Данная реализация имеет недостаток: размер стека фиксирован константой MAXSIZE . Попробуем сделать реализацию, в которой размер массива будет увеличиваться динамически. Для этого заменим статический массив m_data на указатель и будем динамически выделять память. Размер выделенной памяти (т.е. максимальное число элементов в стеке без увеличения его размера) будем хранить в поле m_maxsize . В конструкторе необходимо выделить память для хранения данных:

В деструкторе нужно освободить выделенную память:

Создадим вспомогательный метод resize , выделяющий дополнительную память:

Теперь при добавлении нового элемента в стек проверим, не заполнен ли стек полностью. Если это произошло, то вызовем метод resize для увеличения размера стека:

Ссылочная реализация стека

Другой способ реализации стека: ссылочная реализация. В ссылочной реализации стек хранится в виде последовательности отдельных элементов. Каждый элемент состоит из двух полей: данных и указателя на предыдущий элемент стека:

template struct StackElem < T m_data; StackElem* m_prev; >

В самой структуре Stack хранится число элементов в стеке m_size и указатель на последний элемент стека m_top :

private: int m_size; StackElem * m_top;

При создании стека нужно проинициализировать поле m_top нулевым указателем (указатель в “никуда” свидетельствует о том, что в стеке нет ни одного элемента:

Чтобы вернуть значение последнего элемента в стеке, разыменуем указатель m_top и вернем поле m_data результирующей структуры:

Чтобы удалить верхний элемент в стеке нужно освободить занимаемую им память и передвинуть указатель:

void pop() < StackElemprev = m_top -> m_prev; delete m_top; m_top = prev; --m_size; >

Для добавления нового элемента необходимо выделить для него память и связать его с последним элементом стека:

void push(T val) < StackElemnew_top = new StackElem new_top -> m_data = val; new_top -> m_prev = m_top; m_top = new_top; ++m_size; >

Для очистки стека будем удалять из него элементы по одному, пока стек не пуст:

Также в деструкторе нужно вызвать метод очистки стека, чтобы осводить всю выделенную память:

Упражнения

A: Стек

Реализуйте структуру данных “стек“, релизовав все методы стека. Стек должен быть реализован в виде шаблона над произвольным типом данных. Стек должен иметь произвольный размер. Можно выбрать одну из двух реализаций: на базе динамического массива или ссылочную реализацию.

Программа получает на вход последовательность команд: push n Добавить в стек число n (значение n задается после команды). Программа должна вывести ok .
pop Удалить из стека последний элемент. Программа должна вывести его значение. Если стек пуст, то программа выводит error .
top Программа должна вывести значение последнего элемента, не удаляя его из стека. Если стек пуст, то программа выводит error .
size Программа должна вывести количество элементов в стеке.
clear Программа должна очистить стек и вывести ok .
exit Программа должна вывести bye и завершить работу.

push 2 top pop size pop push 1 size exit

Очередь

Очередью (aнгл. )) называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других.

Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать все элементы очереди, будем в отдельном поле m_start хранить индекс элемента массива, с которого начинается очередь. При удалении элементов, очередь будет «ползти» дальше от начала массива. Чтобы при этом не происходил выход за границы массива, замкнем массив в кольцо: будем считать, что за последним элементом массива следует первый.

Описание структуры очередь:

const int MAX_SIZE=1000; struct queue < int m_size; // Количество элементов в очереди int m_start; // Номер элемента, с которого начинается очередь int m_elems[MAX_SIZE]; // Массив для хранения элементов queue(); // Конструктор ~queue(); // Деструктор void push(int d); // Добавить в очередь новый элемент int pop(); // Удалить из очереди первый элемент // и вернуть его значение int front(); // Вернуть значение первого элемента int size(); // Вернуть количество элементов в очереди void clear(); // Очистить стек >;

B: очередь

Реализуйте очередь. Очередь поддерживает те же операции, что и стек, за исключением операции top , которая заменена операцией front .

Очередь должна быть реализована на базе закольцованного динамического массива.

Дек

Деком (англ. – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека: push_front Добавить (положить) в начало дека новый элемент
push_back Добавить (положить) в конец дека новый элемент
pop_front Извлечь из дека первый элемент
pop_back Извлечь из дека последний элемент
front Узнать значение первого элемента (не удаляя его)
back Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в деке
clear Очистить дек (удалить из него все элементы)

С: дек

Аналогично заданиям A и B, но для дека.

Дек должен быть реализован при помощи ссылочной реализации.

Списки

Списки представляют собой последовательности элементов, в которые можно произвольно вставлять элементы и удалять элементы. Списки реализовываются в виде двусвязных ссылочных структур, поэтому в списках легко перемещаться от одного элемента к следующему и к предыдущему, но нельзя быстро перейти к элементу с заданным номером в списке (как в массиве).

D: двусвязный список

Реализуйте список, элементами которого являются целые числа.

Список состоит из произвольного числа элементов. Один из элементов списка будем называть текущим. Также в качестве текущего элемента может выступать фиктивный элемент, находящийся за последним элементом списка — будем называть его концом списка, это аналог итератора end() . Этот фиктивный элемент нужен для того, чтобы можно было добавлять элементы в конец списка.

В самом начале список пустой, а текущим элементом является конец списка.

insert 1 insert 2 insert 3 next erase get set 4 prev prev erase next next insert 5 prev insert 6 next erase erase get size clear size exit

ok ok ok 2 2 1 ok 3 error 3 end error ok 4 ok 4 4 5 error 1 ok 0 bye

Бинарное дерево поиска

Реализуйте бинарное дерево поиска. Программа получает на вход последовательность чисел и строит из них бинарное дерево поиска. Элементы в деревья добавляются в соответствии с результатом поиска их места. Если элемент уже существует в дереве, добавлять его не надо. Балансировка дерева не производится.

Программа получает на вход последовательность натуральных чисел (типа int ). Последовательность завершается число 0, которое означает конец ввода, и добавлять его в дерево не надо.

Вот пример построенного дерева для последовательности 7 3 2 1 9 5 4 6 8 0 :

После построения дерева решите поставленную задачу.

E-1: Высота дерева

Источник

Создать бинарное дерево целых чисел. Определить максимальное значение узла дерева

Условие: С++ Создать бинарное дерево целых чисел.Определить максимальное значение узла дерева.
Я не знаю правильно ли хоть чуть-чуть написано, но вот кое что есть. Помогите исправить, пожалуйста, чтобы работала правильно. Она выдает неправильное максимальное значение(

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

#pragma hdrstop #include #include //--------------------------------------------------------------------------- #pragma argsused using namespace std; struct node { char data [10]; node *left,*right; }; int n,a,i; char value [10]; node *root; void Tree (node **ptr, char str[10], int AmountNode) { int LeftNodes,RightNodes; if(AmountNode ==0) *ptr=0; else { LeftNodes=AmountNode/2; RightNodes=AmountNode-LeftNodes-1; cout"Enter node data:"; cin>>str; *ptr=new node; strcpy((*ptr)->data,str); (*ptr)->left=0; (*ptr)->right=0; Tree (&((*ptr)->left),str,LeftNodes); Tree (&((*ptr)->right),str,RightNodes); } } void Printtree(node **RootTree,int L) { if((*RootTree!=NULL)) { Printtree(&((*RootTree)->left),L+1); for (int i=0;iL;i++) cout" "; cout(*RootTree)->dataendl; Printtree (&((*RootTree)->right),L+1); } } int main() { cout"Stvorenna ta vidobrashenna dereva"endl; cout"Vvedit chislo vuzliv dereva"endl; cin>>n; root=NULL; cout"Enter "n" integer values:\n"; Tree(&root,value,n); cout"Created tree"endl; Printtree (&root,0); { int a[10]; int max=a[0]; for (int i=0;i10;i++) { if (a[i]>max) { max=a[i]; } } cout"max= "aendl; } system ("pause"); return 0; }

Источник

Создать бинарное дерево целых чисел

Создать бинарное дерево целых чисел. Определить максимальное значение узла дерева.

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

#include struct node { node* left; node* right; int val; node(int v):left(NULL),right(NULL), val(v){} }; const node* node_max(const node* tr); void node_add(node*& tr, int val); void node_clear(node* tr); int main(void){ node* tr = NULL; int a[] = { 5, 4, 8, 3, 7, 2, 1 }; for(unsigned i = 0; i  sizeof(a)/sizeof(a[0]); ++i) node_add(tr, a[i]); const node* pmax = node_max(tr); if(pmax != NULL) std::cout  <"max: "  ->val  ::endl; node_clear(tr); std::cin.get(); return 0; } //максимум const node* node_max(const node* tr){ if(tr == NULL) return NULL; const node* p = tr; while(p->right != NULL) p = p->right; return p; } //вставка void node_add(node*& tr, int val){ node** p = &tr; node* i = tr; while(i != NULL){ if(val  i->val){ p = &i->left; i = i->left; } else if(val > i->val){ p = &i->right; i = i->right; } else return; } *p = new node(val); } //очистка void node_clear(node* tr){ if(tr != NULL){ if(tr->left != NULL) node_clear(tr->left); if(tr->right != NULL) node_clear(tr->right); delete tr; } }

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при.

Создать бинарное дерево
Есть обычное дерево. Узел описывается struct nod int Value; int Number_Of_Sons; nod *Son .

Создать бинарное дерево
Ребята, помогите с такое задачей : нужно написать ф-цию для построения бинарного дерево.

Бинарное дерево создать функцию
Как переделать функцию для бинарного дерева int SumDigit(char *str) < int sum = 0; for (int.

Сообщение было отмечено DenySmirnov как решение

Решение

Сообщение от DenySmirnov

Создать шаблонный класс «бинарное дерево»
Создать шаблон класса «бинарное дерево». Использовать его для сортировки целых чисел и строк.

Создать шаблонный класс «бинарное дерево»
Создать шаблон класса «бинарное дерево». Использовать его для сортировки целых чисел и строк.

На основе вводимой с клавиатуры последовательности чисел до первого нуля формируется бинарное дерево поиска
Страшно каюсь, не подумайте что я ленивый тюлень и мне не хочется вникать в тему, обычно я никогда.

Можно ли создать бинарное дерево поиска с элементами, которые являют собой имена или же что-то другое (НЕ числа)
Если да, как это сделать ? Киньте ссылку/напишите тут, если не сложно. Заранее спасибо!

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

Дан файл целых чисел. Создать новый файл целых чисел, содержащий длины всех серий исходного файла.
Задачу нужно решить в Borland C++ 3.11 Дан файл целых чисел. Создать новый файл целых чисел.

Источник