Бинарное (двоичное) дерево - Linga Ion

Extras din document

Структуры, которые мы прежде обсуждали были одномерные: в них один элемент следует за другим. Сегодня мы сосредоточим наше внимание на двухмерных связанных структурах называемых деревьями, на которых основаны многие из наиболее важных алгоритмов. Полное описание деревьев могло бы занять не одну книгу, потому что они возникают во многих задачах, даже вне информатики, и довольно интенсивно изучаются как математический объект. Сегодня мы рассмотрим основные опр Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла. Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева. Узел дерева, не имеющий потомков, называется листом.