Search this site
Содержание‎ > ‎Школа‎ > ‎Pascal‎ > ‎

Двоичные деревья

Внимание! За два урока 16.04.2009 Вы получите две оценки!
  1. [0] function node(data : TData; left, right : PTreeNode) : PTreeNode;
    1. создает новую вершину дерева со значениями data, left и right
  2. [0] procedure print(n : PTreeNode);
    1. распечатывает дерево в виде скобочной последовательности
  3. [0.5] function sum(n : PTreeNode) : Integer;
    1. возвращает сумму значений во всех вершинах дерева
  4. [0.5] function countX(n : PTreeNode; x : TData) : Integer;
    1. возвращает количество вершин в дереве со значением x
  5. [0.5] procedure clear(var n : PTreeNode);
    1. удаляет из дерева все вершины (очищает память)
  6. [1] function sumPath(n : PTreeNode; path : String) : Integer;
    1. path -- строка, состоящая из символов 'L' и 'R', например 'LLRRL'
    2. эта строка означает путь в дереве (L -- перейти к левому сыну, R -- к правому)
      1. пустая строка -- путь состоит из одной вершины (n)
      2. 'L' -- путь (n, n^.left)
      3. 'RL' -- путь (n, n^.right, n^.right^.left)
    3. функция возвращает сумму значений всех вершин в данном пути
  7. [0.5] procedure replace(n : PTreeNode; x, y : TData);
    1. во все вершины со значением x записывает y
  8. [1] function countLeaves(n : PTreeNode) : Integer;
    1. возвращает количество листьев в дереве (то есть веришн, у которых нет детей)
  9. [1] function min(n : PTreeNode) : TData;
    1. возвращает минимальное значение в дереве
  10. [0.5] function size(n : PTreeNode) : Integer;
    1. возвращает количество вершин в дереве
  11. [1] function countLevel(n : PTreeNode; d : Integer) : Integer;
    1. возвращает количество вершин на глубине d (n находится на глубине 0, ее дети -- на глубине 1 и т. д.)
  12. [1.5] function isFull(n : PTreeNode) : Boolean;
    1. возвращает true, если и только если дерево является полным, то есть в нем все уровни заполнены целиком
    2. пустое дерево не считается является полным :)
  13. [1] function height(n : PTreeNode) : Integer;
    1. возвращает высоту дерева
      1. высота пустого дерева равна нулю
      2. высота непустого дерева -- это количество вершин в самом длинном пути от корня до листа,
        то есть количество уровней в дереве
  14. [1] procedure printInfix(n : PTreeNode);
    1. Распечатать дерево в инфиксной форме:
      1. пустое дерево: nil
      2. непустое: (left data right)
    2. Пример: ((nil 5 nil) 9 ((nil 3 nil) 0 nil))
  15. [2] procedure printNodes(n : PTreeNode, <можно придумать свои дополнительные параметры>);
    1. распечатать дерево в виде вызова функции node (c отступами)
    2. Пример:
      node(9,
          node(6,
              node(1, nil, nil),
              nil
          ),
          node(5, nil,
              node(3, nil, nil)
          )
      )
  16. [1] procedure printLevel(n : PTreeNode; level : Integer);
    1. Распечатать уровень дерева номер level (считая с нуля), то есть вывести значения вершин этого уровня слева направо в строчку
  17. [1] function checkOrder(n : PTreeNode) : Boolean
    1. возвращает true тогда и только тогда, когда для всех вершин в дереве выполняется следующее условие:
      1. значение каждой вершины в левом поддереве (если они есть) меньше либо равно значению самой вершины,
        а значение каждой вершины в правом поддереве (если они есть) -- больше значения самой вершины
    2. в частности, для пустого дерева функция возвращает true
  18. [1] procedure addOrdered(var n : PTreeNode; x : TData);
    1. гарантируется, что дерево n упорядочено (checkOrder(n) = true), в частности, оно может быть пусто
    2. добавить x в дерево так, чтобы оно осталось упорядоченным
  19. [1] procedure printSorted(n : PTreeNode);
    1. гарантируется, что дерево n упорядочено (checkOrder(n) = true)
    2. вывести все его элементы в строчку, в порядке убывания
  20. [3] procedure sort(var a : TArray);
    1. a -- одномерный массив элементов типа TData
    2. отсортировать массив, используя упорядоченные деревья
      1. никакие ранее изучавшиеся алгоритмы сортировки применять нельзя