Представление бинарных деревьев

Бинарное дерево определяется рекурсивно как имеющее левое поддерево, корень и правое поддерево. Левое и правое поддеревья са­ми являются бинарными деревьями. На Рис. 14 показан пример би­нарного дерева.

Рис. 14. Бинарное дерево.

Такие деревья можно представить термами вида

бд(Лд, К, Пд),

где Лд - левое поддерево, К - корень, а Пд - правое поддерево. Дл» обозначения пустого бинарного дерева будем использовать атом nil. Бинарное дерево на рис.5.2.1 имеет левое поддерево

бд(бд(nil, d, nil), b, бд(nil, е, nil))

правое поддерево

бд(nil,с, nil)

и записывается целиком как

бд(бд(бд(nil,d, nil), b, бд(nil,е, nil)), а, бд(nil, с, nil)).