MODULE TyumsuAbsTree;
       TYPE
      Key* = ABSTRACT RECORD END;

      Tree* = POINTER TO Node;
      Node* = ABSTRACT RECORD END;

      OpNode* = PROCEDURE (t: Tree);

   PROCEDURE (t:Tree) New*(), NEW, ABSTRACT;
   PROCEDURE (t:Tree) Insert* (new: Tree), NEW, ABSTRACT;
   PROCEDURE (t:Tree) Delete* (rem: Tree), NEW, ABSTRACT;
        PROCEDURE (t:Tree) TraverseTree* (Op: OpNode), NEW, ABSTRACT;
   PROCEDURE (t:Tree) HeigthRec* (): INTEGER, NEW, ABSTRACT;
END TyumsuAbsTree.

   PROCEDURE (t:BTree) Insert*(new: TyumsuAbsTree.Tree);
   VAR st1, st: Stack;a: INTEGER; t1: BTree;
   BEGIN
      NEW(st);
      NEW(st1);
      st.StackInit();
      st1.StackInit();
      a:=0;
      WITH new: BTree DO
         (*Проход по дереву с сохранением узлов в стеке*)
         WHILE t # NIL DO
            st1.node :=t;
            IF new.key.id < t.key.id THEN
               st1.parent := 1;
               st.Push(st1(Stack));
               st1.StackInit();
               t := t.right;
            ELSE
               st1.parent := 0;
               st.Push(st1(Stack));
               st1.StackInit();
               t := t.left;
            END;
         END;   
         t := new;
         (*Раскручивание стека*)
         WHILE ~st.pEmpty() DO
            st1 := st.Pop()(Stack);
            t1 := st1.node;
            IF st1.parent = 0 THEN
               st1.StackInit();
               t1.left := t;
               t := t1;(*HALT(2);*)
            ELSIF st1.parent = 1 THEN
               st1.StackInit();
               INC(a);
               t1.right := t;
               t := t1;
            END;
         END;
      END;
   END Insert;

PROCEDURE (t: BTree)Insert(new: TyumsuAbsTree.Tree);
BEGIN
  WHILE t # NIL DO
    WITH new: BTree DO
      IF new.key < t.key THEN
        t.left.Insert(new);
.................................
      END;
    END;
  END;
END Insert;

PROCEDURE (t:BTree) Insert*(new: TyumsuAbsTree.Tree);
  BEGIN
    WITH new: BTree DO
      IF new.key.id < t.key.id THEN
        IF t.left # NIL THEN t.left.Insert(new); ELSE t.left := new END;
      ELSIF new.key.id > t.key.id THEN
        IF t.right # NIL THEN t.right.Insert(new); ELSE t.right := new END;
      END;
    END;
END Insert;