Дерева (графи), Детальна інформація

Реферат на тему:

Дерева (графи)

Означення. Деревом називається граф без циклiв, в якому видiлено окрему вершину, яку називають коренем дерева.

Структурою типу дерева будемо називати або NIL (порожнє дерево), або структуру (Значення . (Лiвий син . Правий син)), де лiвий та правий сини є структурами типа дерево. Наприклад, дерево яке складається з єдиного елемента, буде мати вигляд: (Element . (NIL . NIL)).

Функцiя INSEL вставляє елемент n в дерево tree за наступним правилом: Якщо дерево порожнє, то створити дерево (n . (NIL . NIL)). Iнакше вставити елемент в лiве пiддерево якщо n менше за значення поточної вершини або в праве пiддерево, якщо бiльше. Функцiя INSL створює за списком сортуюче дерево, вершинами якого будуть всi елементи списка. Дерево називається сортуючим, оскiльки при обходi його злiва направо ми отримаємо вiдсортований список елементiв у зростаючому порядку.

 

(DEFUN insel (n tree)

((NULL tree) (CONS n (CONS NIL NIL)))

((> n (CAR tree)) (cons (car tree) (cons (cadr tree) (insel n (cddr tree)))))

(cons (car tree) (cons (insel n (cadr tree)) (cddr tree))) )

 

(DEFUN INSL (lst tree)

((NULL lst) tree)

(SETQ tree (insel (car lst) tree))

(INSL (CDR lst) tree) )

Наступнi двi функцiї виконують обхiд дерева: PUD (Print Up-Down) - обхiд згори вниз, PLR (Print Left-Right) - обхiд злiва направо.

 

(DEFUN PUD (tree) (DEFUN PLR (tree)

((NULL tree)) ((NULL tree))

(PRIN1 (CAR tree)) (SPACES 3) (PLR (CADR tree))

(PUD (CADR tree)) (PRIN1 (CAR tree)) (SPACES 3)

(PUD (CDDR tree)) ) (PLR (CDDR tree)) )

Функцiя REVT (Reverse Tree) обертає дерево: кожне праве пiддерево стає лiвим пiддеревом i навпаки.

 

(DEFUN REVT (tree)

((NULL tree) NIL)

(CONS (CAR tree) (CONS (REVT (CDDR tree)) (REVT (CADR tree)))) )

Приклади

 

$ (SETQ a (INSL '(5 1 7 3 9 2 4 8 10) NIL)) $ (SETQ b (REVT a))