Теперь мы перейдем от линейных структур к структурам, обеспечивающим быстрый поиск и вставку элементов. На рис. 13.2 показано двоичное дерево поиска, содержащее элементы 31, 41, 59 и 26 (последовательно добавлявшиеся именно в этом порядке).
root:
Рис. 13.2. Двоичное дерево
В классе IntSetBST мы определяем узлы дерева и его корень.
Листинг 13.13. Внутренняя структура класса IntSetBST
pri vate
int n . *v. vn; struct node { int va1,
node *left. *nght.
node(int i) { val = i: left = right =* 0. }}:
node *root;
Дерево инициализируется пустым корнем. Действия с деревом осуществляются с помощью рекурсивных функций.
I nt Set BST(int maxelements, int maxval) { root = 0; n = 0; }
void insert(int t) { root = rinsert(root, t): }
void report(int *x) { v = x; vn = 0. traverse(root); }
Функция вставки спускается вниз по дереву до тех пор, пока не будет найдено значение, равное данному (поиск в этом случае завершается), либо дерево закончится (тогда к нему добавляется новый узел).
node *rmsert(p. t) if р == О р = new node(t) n++
el se if t < p->val
p->1 eft = rinsert(p->left. t) else if t > p->val
p->right - ri nsert (p->n ght. t)
// Если p->vaT =- t ничего делать не нужно return р
Поскольку в нашем приложении элементы вставляются в случайном порядке, нам не нужно беспокоиться о балансировке дерева, которая достаточно сложна. В задаче 1 показывается, что в других алгоритмах со случайными наборами дерево может получиться сильно разбалансированным.
При симметричном обходе1 вершин дерева сначала обрабатывается левое поддерево, затем возвращается значение в узле, а потом обрабатывается правое поддерево.
Опубликовал vovan666
April 17 2013 00:03:28 ·
0 Комментариев ·
5170 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
