Основы проектирования систем искусственного интеллекта

       

ПРЕДСТАВЛЕНИЕ БИНАРНЫХ ДЕРЕВЬЕВ


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

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

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

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

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

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

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

бд(nil,с, nil)

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

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



Содержание раздела