КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Стеки, очереди, деки, списки, кольца
Questions bank for Final exam on SSD5
Binarysearchtrees
Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt. Первые тесты не всегда совпадают с примерами из условия.
Реализуйте бинарное дерево поиска (для maxheap и minheap задачи аналогичны) для целых чисел. Программа получает на вход последовательность целых чисел и строит из них дерево. Элементы в деревья добавляются в соответствии с результатом поиска их места. Если элемент уже существует в дереве, добавлять его не надо. Балансировка дерева не производится.
Формат входных данных
На вход программа получает последовательность натуральных чисел. Последовательность завершается числом 0, которое означает конец ввода, и добавлять его в дерево не надо.
Формат выходных данных
Выведите единственное число – высоту получившегося дерева.
Пример
Входные данные
| Выходные данные
| 7 3 2 1 9 5 4 6 8 0
|
| Пример соответствует следующему дереву:
![](https://konspekta.net/lektsiiimg/baza3/5161181704221.files/image001.gif)
- // Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
-
- using namespace std;
- struct node
- {
- int h,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- h=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x;
-
- int h(pnode t)
- {
- return t ? t->h : 0;
- }
-
- void update(pnode &t)
- {
- t->h=max(h(t->l),h(t->r))+1;
- }
-
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
-
- void add(pnode &t,int x)
- {
- if (t==0)
- t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
-
- int main()
- {
- freopen( "input.txt","r",stdin );
- freopen( "output.txt","w",stdout );
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- printf("%d",h(t));
- return 0;
- }
-
2) Подсчитайте количество элементов в получившемся дереве и выведите это количество.
Пример
Входные данные
| Выходные данные
| 1 2 3 1 0
|
|
- // Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
-
- using namespace std;
- struct node
- {
- int size,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- size=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x;
-
- int size(pnode t)
- {
- return t ? t->size : 0;
- }
-
- void update(pnode &t)
- {
- t->size=size(t->l)+size(t->r)+1;
- }
-
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
-
- void add(pnode &t,int x)
- {
- if (t==0) t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
-
- int main()
- {
- freopen( "input.txt","r",stdin );
- freopen( "output.txt","w",stdout );
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- printf("%d",size(t));
- return 0;
- }
-
3) Выведите второй по величине элемент в построенном дереве. Гарантируется, что такой найдется.
Пример
Входные данные
| Выходные данные
| 7 3 2 1 9 5 4 6 8 0
|
| 1 1 1 2 2 2 0
|
|
- // Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
-
- using namespace std;
- struct node
- {
- int size,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- size=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x,ans;
-
- int size(pnode t)
- {
- return t ? t->size : 0;
- }
-
- void update(pnode &t)
- {
- t->size=size(t->l)+size(t->r)+1;
- }
-
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
-
- void add(pnode &t,int x)
- {
- if (t==0) t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
-
- void del_max(pnode &t)
- {
- if(t->r)
- del_max(t->r);
- else
- t=t->l;
- }
-
- int max(pnode t)
- {
- return (t->r) ? max(t->r) : t->x;
- }
-
- int main()
- {
- freopen( "input.txt","r",stdin );
- freopen( "output.txt","w",stdout );
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- int k=2;
- for (int i=1;i<=k;i++)
- ans=max(t), del_max(t);
- printf("%d",ans);
- return 0;
- }
-
4) Выведите все элементы полученного дерева в порядке возрастания.
Пример
Входные данные
| Выходные данные
| 7 3 2 1 9 5 4 6 8 0
| 1 2 3 4 5 6 7 8 9
|
- // Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
-
- using namespace std;
- struct node
- {
- int size,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- size=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x,ans;
-
- int size(pnode t)
- {
- return t ? t->size : 0;
- }
-
- void update(pnode &t)
- {
- t->size=size(t->l)+size(t->r)+1;
- }
-
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
-
- void add(pnode &t,int x)
- {
- if (t==0) t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
-
- void dfs(pnode t)
- {
- if (t->l) dfs(t->l);
- printf("%d ",t->x);
- if (t->r) dfs(t->r);
- }
-
- int main()
- {
- freopen( "input.txt","r",stdin );
- freopen( "output.txt","w",stdout );
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- dfs(t);
- return 0;
- }
-
5) Для полученного дерева выведите список всех листьев (вершин, не имеющих потомков) в порядке возрастания.
Пример
Входные данные
| Выходные данные
| 7 3 2 1 9 5 4 6 8 0
| 1 4 6 8
| - // Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
-
- using namespace std;
- struct node
- {
- int size,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- size=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x,ans;
-
- int size(pnode t)
- {
- return t ? t->size : 0;
- }
-
- void update(pnode &t)
- {
- t->size=size(t->l)+size(t->r)+1;
- }
-
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
-
- void add(pnode &t,int x)
- {
- if (t==0) t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
-
- void dfs(pnode t)
- {
- if (t->l) dfs(t->l);
- if (t->r) dfs(t->r);
- if ((!(t->r)&&!(t->l)))
- printf("%d ",t->x);
- }
-
- int main()
- {
- freopen( "input.txt","r",stdin );
- freopen( "output.txt","w",stdout );
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- dfs(t);
- return 0;
- }
-
6) Для полученного дерева выведите список всех вершин, имеющих по два ребёнка, в порядке возрастания.
Пример
Входные данные
| Выходные данные
| 7 3 2 1 9 5 4 6 8 0
| 3 5 7
|
- // Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
-
- using namespace std;
- struct node
- {
- int size,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- size=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x,ans;
-
- int size(pnode t)
- {
- return t ? t->size : 0;
- }
-
- void update(pnode &t)
- {
- t->size=size(t->l)+size(t->r)+1;
- }
-
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
-
- void add(pnode &t,int x)
- {
- if (t==0) t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
-
- void dfs(pnode t)
- {
- if (t->l) dfs(t->l);
- if ((t->r)&&(t->l))
- printf("%d ",t->x);
- if (t->r) dfs(t->r);
- }
-
- int main()
- {
- freopen( "input.txt","r",stdin );
- freopen( "output.txt","w",stdout );
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- dfs(t);
- return 0;
- }
-
7) Для полученного дерева выведите список всех вершин, имеющих только одного ребёнка, в порядке возрастания.
Пример
Входные данные
| Выходные данные
| 7 3 2 1 9 5 4 6 8 0
| 2 9
| //Solution
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- #include <set>
- #include <map>
-
- using namespace std;
- struct node
- {
- int size,x;
- node *l, *r;
- node (int key)
- {
- x=key;
- size=1;
- l=r=0;
- }
- };
- typedef node* pnode;
- int x,ans;
-
- int size(pnode t)
- {
- return t ? t->size : 0;
- }
-
- void update(pnode &t)
- {
- t->size=size(t->l)+size(t->r)+1;
- }
-
- int find(pnode t, int x)
- {
- if (t==0) return 0;
- if (t->x == x) return 1;
- if (t->x > x) return find(t->l, x);
- return find(t->r, x);
- }
-
- void add(pnode &t,int x)
- {
- if (t==0) t=new node(x);
- else
- if (t->x > x) add(t->l, x);
- else
- add(t->r, x);
- update(t);
- }
-
- void dfs(pnode t)
- {
- if (t->l) dfs(t->l);
- if ((t->r!=0)^(t->l!=0))
- printf("%d ",t->x);
- if (t->r) dfs(t->r);
- }
-
- int main()
- {
- freopen( "input.txt","r",stdin );
- freopen( "output.txt","w",stdout );
- pnode t=0;
- while (1)
- {
- scanf("%d",&x);
- if (!x) break;
- if (! find(t, x))
- add(t, x);
- }
- dfs(t);
- return 0;
- }
-
Стеки, очереди, деки, списки, кольца
|