Рассмотрим структуру данных которая называется двоичное дерево. Несмотря на то что бывает много различных типов деревьев двоичные играют особую роль, так как в отсортированном состоянии позволяют очень быстро выполнить вставку, удаление и поиск. Каждый элемент двоичного дерева состоит из информационной части и указателей на левый и правый элементы. Приведем схематичный пример двоичного дерева.
Первый элемент дерева называется корнем (root). Каждый элемент данных называется вершиной дерева (node), а любой фрагмент дерева называется поддеревом (subtree). Вершина к которой не подсоединены поддеревья называется заключительным узлом (terminal node) или листом (leaf). Высота (height) дерева равняеться максимальному количеству уровней от корня до листа. При работе с деревьями можно допустить, что в памяти они существуют в том же виде как на бумаге. Но необходимо помнить, что дерево – всего лишь способ логической организации в памяти, а память линейна. В некотором смысле Двоичное дерево является особым видом связанного списка. Элементы можно вставлять, удалять и извлекать в любом порядке. Кроме того, опера¬ция извлечения не является разрушающей. Несмотря на то, что деревья легко пред¬ставить в воображении, в теории программирования с ними связан ряд сложных за¬дач. Большинство функций, работающих с деревьями, рекурсивны, поскольку дерево по своей сути является рекурсивной структурой данных. Другими словами, каждое поддерево, в свою очередь, является деревом. Поэтому разрабатываемые здесь функ¬ции будут рекурсивными. Существуют и не рекурсивные версии этих функций, но их код понять намного сложнее. Способ упорядочивания дерева зависит от того, как к нему впоследствии будет осуществляться доступ. Процесс поочередного доступа к каждой вершине дерева на¬зывается обходом (вершин) дерева (tree traversal). Существует три порядка обхода дерева: обход симметричным способом, или симметричный обход (inorder), обход в прямом порядке, прямой обход, упорядоченный обход, обход сверху, или обход в ширину (preorder) и обход в обратном порядке, обход в глубину, об¬ратный обход, обход снизу (postorder). При симметричном обходе обрабатывается сна¬чала левое поддерево, затем корень, а затем правое поддерево. При прямом обходе обрабатывается сначала корень, затем левое поддерево, а потом правое. При обходе снизу сначала обрабатывается левое поддерево, затем правое и, наконец корень. Последовательность доступа при каждом методе обхода показана ниже: Симметричный обход a b с d e f g Прямой обход d b а с f e g Обход снизу а с b e g f d
Пример функции создающей двоичное дерево:
struct tree { char info; struct tree *left; struct tree *right; };
Описанный выше алгоритм просто следует по ссылкам дерева переходя к левой или правой ветви на основании содержимого поля info по достижении места вставки нового элемента.
