---
title: "Вывод элементов бинарного дерева поиска в определенном интервале"
description: "Задача: Дано бинарное дерево поиска и два значения. Вывести все элементы бинарного дерева поиска, на..."
author: "codekrolik"
published: "2014-07-28T00:39:26+00:00"
modified: "2014-07-28T00:39:26+00:00"
locale: "ru"
canonical_url: "https://yvision.kz/post/vyvod-elementov-binarnogo-dereva-poiska-v-opredelennom-intervale-423004"
markdown_url: "https://yvision.kz/post/vyvod-elementov-binarnogo-dereva-poiska-v-opredelennom-intervale-423004/markdown"
site_name: "Yvision.kz"
---

# Вывод элементов бинарного дерева поиска в определенном интервале

> Задача: Дано бинарное дерево поиска и два значения. Вывести все элементы бинарного дерева поиска, на...

Задача:

Дано бинарное дерево поиска и два значения. Вывести все элементы бинарного дерева поиска, находящиеся в заданном значениями интервале.

 

Решение:

Решением будет модифицированный вариант обхода дерева, в котором мы исключим из обхода/проигнорируем значения некоторых нод.

Для примера, рассмотрим следующее дерево:

![](http://storage.yvision.kz/images/user/codekrolik/nXqbwSKUuB3a87B1LPBt8MFw4593k5.png)

Предположим, нас интересуют ноды в диапазоне 3 - 7. В этом случае, мы исключаем из обхода ноды 1, 9 и 10.

Ноды 2 и 8, несмотря на то, что они не принадлежат искомому диапазону, исключать из обхода нельзя, т.к. ноды 3 и 7 являются потомками нод 2 и 8, соответственно. Мы просто проигнорируем их значения, т.к. они не входят в диапазон.

В качестве алгоритма обхода я выбрал inorder, т.к. для бинарного дерева поиска данный алгоритм выведет значения в возрастающем порядке.

Обход можно написать рекурсивно либо интеративно. Больше информации об итеративных обходах можно найте с посвященному этому [посте](http://codekrolik.yvision.kz/post/422553).

 

Решение (рекурсивное и итеративное): [https://gist.github.com/codekrolik/d886c4395d475298d0be](https://gist.github.com/codekrolik/d886c4395d475298d0be)

Тесты: [https://gist.github.com/codekrolik/a6f7a9aeb3a925c6fe64](https://gist.github.com/codekrolik/a6f7a9aeb3a925c6fe64)

---

Source: [https://yvision.kz/post/vyvod-elementov-binarnogo-dereva-poiska-v-opredelennom-intervale-423004](https://yvision.kz/post/vyvod-elementov-binarnogo-dereva-poiska-v-opredelennom-intervale-423004)