0 / 0 / 0
Регистрация: 07.06.2015
Сообщений: 4
1

Алгоритм поиска числа всех вершин высоты N в двоичном дереве

07.06.2015, 18:23. Показов 1587. Ответов 1
Метки нет (Все метки)

Добрый день. Нужно придумать эффективуюю программу(алгоритм) поиска числа всех вершин высоты N в двоичном дереве (какое именно дерево: АвЛ, поиска и т.д. не говорится). Первое, что приходит в голову это просто обход дерева вглубь на число N, но это получается неэффективно (наверное, просто я не придумал ничего, с чем можно сравнить). Наверное надо как-то использовать особенность дерева, что каждый узел имеет не более 2 потомков.
То есть в зависимости от N мы получаем 2^(n-1) вершин. Для
n=1, k=1 (всего одна вершина высоты 1, это корень дерева)
n=2, k=2 (первые два потомка)
n=3, k=4 и т.д.
Получается тупо смотрим дерево вглубь (n-1) раз, если один из узлов не имеет сыновей до n-1 глубины, то поиск для этой ветви заканчивается.
И просьба помочь написать этот алгоритм на псевдокоде или java (думаю там нужна будет рекурсия, а я с ней не очень дружу). Ведь как-то надо зафиксировать на какой глубине мы сейчас находимся, а как это с рекурсией сделать я не пойму.

Добавлено через 1 час 0 минут
Получилось как-то так:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int find(int n, Node root) {
        int result = 0;
        if (n == 1) if (root != null) return 1;
        if (n == 2) {
            if (root.left != null) result++;
            if (root.right != null) result++;
        } else if ((root.left != null) && (root.right != null)) {
            n--;
            result = find(n, root.left) + find(n, root.right);
        } else if ((root.left != null) && (root.right == null)) {
            n--;
            result = find(n, root.left);
        } else if ((root.left == null) && (root.right != null)) {
            n--;
            result = find(n, root.right);
        }
        return result;
    }
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.06.2015, 18:23
Ответы с готовыми решениями:

Количество вершин в двоичном дереве
Верно ли, что количество вершин в двоичном дереве однозначно определяется количеством висящих...

Написать функцию поиска элемента X в двоичном дереве поиска
Написать функцию поиска элемента X в двоичном дереве поиска.

Необъявленный идентификатор в двоичном дереве поиска
Добрый вечер! у меня возникла проблема по программе, составленной по данному условию: ...

Реализация словаря в двоичном дереве поиска
Помогите,пожалуйста, создать программу на С++! Тема: Релизация словаря в двоичном дереве...

1
Модератор
2832 / 1997 / 431
Регистрация: 26.03.2015
Сообщений: 7,674
08.06.2015, 08:58 2
Лучший ответ Сообщение было отмечено v1212186 как решение

Решение

Обход в ширину на очередном шаге даст список всех вершин глубины N. Только нужно будет запоминать информацию о глубине.

1. Положили в очередь корень с глубиной (root, 0)
2. Достаём из очереди первый элемент (node, h).
3. Если его глубина h == N, то все элементы в очереди имеют нужную глубину. Переходим к пункту 6.
4. Кладём в очередь всех его детей (child, h+1)
5. Переходим к пункту 2.
6. Ура!
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.06.2015, 08:58

Подсчет уровней в двоичном дереве поиска
каков алгоритм подсчета уровней в двоичном дереве поиска. спасибо.

Реализация словаря в двоичном дереве поиска
Ребят очень нужно, хотя бы реализацию словаря в C++ ,никак не могу найти

Найти второй максимум в двоичном дереве поиска
Собственно, в задаче не проходит один тест. Условие: Выведите второй по величине элемент в...

Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение?
Вот примерная рекурсивная функция, но я не знаю, как выйти из нее в нужный момент. void range(Node...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.