До сих пор мы рассматривали структуры данных, данные в которых располагаются линейно. В связном списке — от первого узла к единственному последнему. В динамическом массиве — в виде непрерывного блока.
В этой части мы рассмотрим совершенно новую структуру данных — дерево. А точнее, двоичное (бинарное) дерево поиска (binary search tree). Бинарное дерево поиска имеет структуру дерева, но элементы в нем расположены по определенным правилам.
Также смотрите другие материалы этой серии: стеки и очереди, динамический массив, связный список, оценка сложности алгоритма, сортировка и множества.
Для начала мы рассмотрим обычное дерево.
Деревья
Дерево — это структура, в которой у каждого узла может быть ноль или более подузлов — «детей». Например, дерево может выглядеть так:

Структура организации
Это дерево показывает структуру компании. Узлы представляют людей или подразделения, линии — связи и отношения. Дерево — это самый эффективный представления и хранения такой информации.
1.Открыть правой рукой хлебницу; __2.Взять булку хлеба правой рукой; __3.Положить хлеб на разделочную доску; (предположим, что доска уже лежала на столе) __4.Открыть правой рукой верхний ящик стола; __5.Найти блестящий нож, длиной 20 см, с черной ручкой; __6.Взять нож в правую руку; __7.Поднести нож к хлебу; __8.Зафиксировать хлеб левой рукой, взявшись за левый край булки; __9.Расположить нож строго над правым ребром булки хлеба; __10.Повторять следующие действия 5 раз: 10.1.Отступить влево на сантиметр; 10.2.Повторять следующие действия, пока лезвие ножа не не коснется доски: 10.2.1.Прижать нож к хлебу; 10.2.2.Совершить ножом возвратно поступательное движение вперед-назад; 10.3.Поднять нож вверх; __11.Положить нож в ящик; __12.Отпустить левой рукой хлеб.
Объяснение:
Запускаем программу и смотрим, как она работает: Ой... вместе с пятым куском и палец отрезал... чёрт! остановить программу! Я же не написал как именно нужно зафиксировать хлеб левой рукой, схватился как попало и большой палец торчал в сторону... Возвращаемся к строчке "Зафиксировать хлеб левой рукой, взявшись за левый край булки;" После нее пишем: "Поджать большой палец левой руки влево, к ладони;" Запускаем программу Ой... на строчке "Положить нож в ящик;" нож упал на пол... Проклятье! оказывается, стол стоит немного под наклоном и ящик сам закрылся... Возвращаемся к коду и перед строчкой "Положить нож в ящик;" пишем "Открыть правой рукой верхний ящик стола;" Заметили ошибку? Нет?! Как мы можем открыть ящик правой рукой, если в этой руке нож? Значит, сначала нужно положить нож на стол, потом открыть ящик, снова взять нож и т.д. И делаем мы это до тех пор, пока хлеб не будет нарезан как следует, без повреждения мебели и пальцев. Вот, примерно так происходит отладка С опытом начинаешь писать программы, которые работают с первого раза, допуская минимум ошибок, а проверка "открыт ли ящик", перед складыванием в него чего-то, входит в привычку. Когда какие-то операции совершаются постоянно, такие как нарезка хлеба, мойка посуды и т.д., то программисты их описывают в виде процедур. Процедура - набор определенных действий, спрятанный под одной командой. Таким образом, текст программы, который я приводил выше, можно поместить в процедуру под названием НарезатьХлеба(параметр), где в качестве параметра будем указывать количество кусков