Здравствуйте. Я начинаю изучать программирование и Компонентный Паскаль показался мне очень интересным языком. Но есть трудности организационного характера.
Например, я хочу сделать модуль, реализующий Бинарные деревья. Пишу интерфейс:
Код:
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;
потому, что не получалось сделать t.left.Insert(new), когда t.left = NIL.
Я понимаю, что наступаю на грабли, но можно ли все-таки сделать здесь рекурсию?