Проектирование систем искусственного интеллекта



         

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


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

Бинарное дерево.

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

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

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

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




Содержание    Вперед