Форум программистов, компьютерный форум CyberForum.ru

Бинарные деревья: дописать код ,чтобы искать число массива в бинарном дереве и время выполнения поиска - C++

Восстановить пароль Регистрация
 
Андрей445232
0 / 0 / 0
Регистрация: 21.12.2012
Сообщений: 8
19.12.2013, 21:30     Бинарные деревья: дописать код ,чтобы искать число массива в бинарном дереве и время выполнения поиска #1
Код реализации:
C++
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
// Авл деревья 2.cpp: определяет точку входа для консольного приложения.
//бинарное дерево
 
#include "stdafx.h"
//Программа формирует дерево из массива целых чисел и выводит его на экран
//root - корень дерева
#include <iostream>
#include <conio.h>
#include <ctime>
using namespace std;
int const x = 50;
struct Node{
        int d;         //Данные элемента
        Node *left;    //Ссылка на левое поддерево
        Node *right;   //Ссылка на правое поддерево
};
Node *first(int d);                    //Формирование первого элемента
Node *search_insert(Node *root,int d); //Поиск с включением
void print_tree(Node *root,int l);     //Обход дерева
 
//-------------------------------------------
int main()
{
        int arr[100];
        srand(time (NULL));
        for (int i=0;i<100;i++)
            arr[i] = rand () %201;
        Node *root=first(arr[0]);    //Формируем корень дерева
      //Ищем место куда вставить и вставляем новые элементы
      for(int i=1;i<100;i++)search_insert(root,arr[i]); 
        print_tree(root,0);            //вывод дерева на экран
        getch();
        return 0;
}
 
//--------------------------------------------
//Формирование первого элемента
Node *first(int d){
Node *pv =new Node;   //Создаём элемент
pv->d=d;              //Присваиваем значение элементу поля
pv->left=0;           //Ссылка на левое поддерево равна NULL
pv->right=0;          //Ссылка на правое поддерево равна NULL
return pv;            //Возвращаем адрес элемента
}
 
//---------------------------------------------
 
//Поиск с включением
Node *search_insert(Node *root,int d){
Node*pv=root,*prev;
bool found = false;    //Переменная отвечающая за то что нашли ли элемент или нет
/*Ниже приведён алгоритм поиска короче если нашли такой же элемент то мы его не вставляем в дерево выходим из функции возвратив адрес совпавшего элемента*/
while(pv&&!found){
        prev=pv;                       //получаем адрес элемента от которого будем пускать корни
        if(d==pv->d)found=true;        //совпадение выходим из цикла
        else if(d<pv->d)pv=pv->left;   //Всовываемя в левое поддерево
        else pv=pv->right;             //Всовываемя в правое поддерево 
//Выход из цикла осуществляется, тогда когда нашли свободный адрес : ссылку у дерева : для вставки нового узла */
}
//---------------------------
/*Если совпало значение элемента со значением элемента который хотим вставить то выходим из функции возвращая адрес элемента
с которым совпало */
if(found)return pv;               
//Создание нового узла
Node *pnew =new Node;
pnew->d=d;
pnew->left=0;
pnew->right=0;
if(d<prev->d)
//Присоединение к левому поддереву предка
prev->left=pnew;
else 
//присоединяем к правому поддереву предка
prev->right=pnew;
return pnew;
}
//---------------------------------------
//Обход дерева
void print_tree(Node *p,int level){
        if(p){
               print_tree(p->right,level+1);          //Перемещение по правым поддеревьям     
                for(int i=0;i<level;i++)cout<<"   ";
                cout<<p->d<<'\n';                      //вывод значений дерева
                  print_tree(p->left,level+1);           //Перемещение по левым поддеревьям
                
     }
}[CPP]
[/CPP]
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.12.2013, 21:30     Бинарные деревья: дописать код ,чтобы искать число массива в бинарном дереве и время выполнения поиска
Посмотрите здесь:

C++ В бинарном дереве подсчитать число его листов
C++ Засечь время выполнения поиска
Поиск ключа в бинарном дереве поиска C++
C++ Шаблоны (упорядоченные бинарные деревья поиска вещественных чисел, линейных многочленов и двоичных строк)
C++ посчитать время выполнения поиска
Необычная функция в бинарном дереве поиска C++
В бинарном дереве определить число узлов у которых есть указатель только на одну ветвь. C++
Как в бинарном дереве у всех листьев вычесть введенное число? C++

Искать еще темы с ответами

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

Текущее время: 03:58. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru