program binaryTree;
// класс описывающий узел дерева
type
Node = class
public
  key:integer; // ключ, по которому производится поиск
  data:double; // данные в узле дерева
  left,right,parent: Node; // 3 указателя - на левого и правого ребенка узла
  // а также указатель на родителя узла
end;

// класс двоичное дерево
type
BinaryTreeClass = class
public
  root, currentElement : Node; // 2 указателя - на корень дерева и на текущий элемент
  size : integer; // размер дерева - суммарное кол-во всех узлов

// процедура добавления нового узла в дерево
// если такое значение уже хранится в дереве, то алгоритм
// вставит его как правого потомка этого узла
procedure add(_key:integer ; _data:double);

  var rightFlag : boolean; // флаг направления последнего перехода
  newElement, current, previous : Node; // узлы : новый элемент, текущий элемент и предыдущий
  begin
  rightFlag := true;
  // увеличиваем размер дерева на единицу
  size := size + 1;
  // создаем новый узел
  newElement := new Node();
  // иницилизиуем его данными из входных параметров
  newElement.data := _data;
  newElement.key := _key;
  // текущий узел это корень
  current := root;
  previous := nil;
  // далее будем искать нужное место для вставки, алгоритм похож на тот, что
  // используется в алгоритме поиска узла

  if(root = nil) then // отдельный случай если у нас еще нет корня
  begin
    root := newElement;  // новый элемент становится корнем
    currentElement := root; // текущий элемент корень
  end
  else
  begin
  // в этом цикле мы ищем нужное место для вставки
  while(current <> nil) do
  begin
    // предыдущий элемент становится равен текущему
    previous := current;
    if(_key > current.key) then
    begin
      current := current.right;
      rightFlag := true;
    end
    else begin
      current := current.left;
      rightFlag := false;
    end;
  end;
  // предыдущий элемент становится родителем
  newElement.parent := previous;

  // вставляем новый элемент в нужное место либо вправо либо влево
  if(rightFlag) then previous.right := newElement
  else  previous.left := newElement;
  current := newElement;
  end;
end;

// процедура, которая переходит от текущего узла дерева к его левому ребенку
// , если он существует
procedure goLeft();
begin
  if(currentElement.left <> nil) then
		currentElement := currentElement.left;
end;
// процедура, которая переходит от текущего узла дерева к его правому ребенку
// , если он существует
procedure goRight();
begin
  if(currentElement.right <> nil) then
		currentElement := currentElement.right;
end;

// процедура, которая переходит от текущего узла дерева к его родителю
// если мы находимся в корне, то у корня нет родителя
// и переход не осуществляется
procedure goBack();
begin
  if(currentElement.right <> root) then
		currentElement := currentElement.parent;
end;
// процедура возвращающее значение текущего узла
function getCurrentValue():double;
begin
  getCurrentValue := currentElement.data;
end;
// процедура переходящая от текущего узла к корню
procedure goToRoot();
begin
		currentElement := root;
end;

// функция поиска значения по ключу в дереве
// результат - обьект найденного узла, а также
// значение текущего узла устанавливается в найденный узел
function search(_key : integer):Node;
var current : Node;
begin
  // устанавлниваем стартовое текущего узла в корень
  current:= root;
  // до тех пор пока значение текущего узла не нул
  while(current <> nil) do
  begin
    // если наше искомое значение совпадает со значением узла
    if(current.key = _key) then
    begin
      // значение текущего узла устанавливается в найденный узел
      currentElement := current;
      // возвращаем обьект найденного узла
      search := current;
      // выходим из функции
      Exit;
    end
    // если наше поисковое значение меньше, чем значение узла
    // то идем налево
    else if (current.key > _key) then
    current := current.left
    // иначе идем направо
    else current := current.right;
  end;
  // возвращаем нул, как символ того,что ничего не найдено
  search := nil;
end;

end;
var tree:BinaryTreeClass;



begin

// создаем обьект - дерево и добавляем в него несколько элементов
tree := new BinaryTreeClass();
tree.add(10, 2.5);
tree.add(16, 3.5);
tree.add(20, 4.5);
tree.add(8, 5.5);
tree.add(17, 6.5);
// пример поиска в дереве
writeln(tree.search(17).data);
writeln(tree.search(20).data);
writeln(tree.search(55));

end.