Представление бинарных деревьев
Бинарное дерево определяется рекурсивно как имеющее левое поддерево, корень и правое поддерево . Левое и правое поддеревья сами являются бинарными деревьями. На рис. 8.1 показан пример бинарного дерева.
Рис. 8.1. Бинарное дерево.
Такие деревья можно представить термами вида
бд(Лд, К, Пд),
где Лд — левое поддерево, К — корень, а Пд — правое поддерево. Для обозначения пустого бинарного дерева будем использовать атом nil. Бинарное дерево на рис.8.1 имеет левое поддерево бд(бд(nil, d, nil), b, бд(nil, е, nil)) правое поддерево бд(nil,с, nil) и записывается целиком как бд(бд(бд(nil,d, nil), b, бд(nil,е, nil)), а, бд(nil, с, nil)).
