Программа для реализации упорядоченного двоичного дерева

Двоичное (бинарное) дерево – это дерево, у каждой вершины которого может быть только два потомка.

Двоичное дерево является самым простым видом дерева. В упорядоченном дереве большее значение располагается справа от вершины, а меньшие значения слева от вершины.

Задача. Построить двоичное упорядоченное дерево из чисел 5, 7, 3, 1, 4.

Первый элемент (5) помещается в корень дерева:

Берем следующий элемент (7). Так как 7 больше 5, помещаем его в правую ветвь от 5:

Берем следующий элемент (3). Так как 3 меньше 5, помещаем его в левую ветвь от 5:

Берем следующий элемент (1). Так как 1 меньше 5 и левая ветвь уже существует (элемент 3), будем сравнивать 1 и 3. 1 меньше 3, поэтому помещаем 1 в левую ветвь от 3.

Берем следующий элемент (4). Так как 4 меньше 5 и левая ветвь уже существует (элемент 3), будем сравнивать 4 и 3. 4 больше 3, поэтому помещаем 4 в правую ветвь от 3. В результате получаем бинарное дерево: