Левопрошитое дерево, проблемы Опции

[Jill]

Основной принцип: левый - потомок, правый - брат.
Описание дерева:

 type
    PTree=^TTree;
    TTree=record
      LL:PTree;    {левый указатель - на потомка если True, на предка если False}
      RL:PTree;    {правый указатель - на братьев}
      Key:string;  {ключ}
      Sign:boolean; {признак существования потомков}
    end; 

Если вершины нет, то создаем ее:

 if root=NIL then begin
    new(root);
    root^.LL:=root;   {сам на себя - предков нет}
    root^.RL:=NIL;    {нет братьев}
    root^.Key:='root';
    root^.Sign:=false; {нет потомков}

Добавление... Вроде существует два варианта - либо это первый потомок, либо нет. Не выходит реализовать это условие

 procedure AddElem(chto:string; kuda:PTree);
begin
    new(node);
    if kuda^.Sign=false then begin
      kuda^.LL:=node;    {на сына }
      kuda^.Sign:=true;  {у kuda появился потомок}
      node^.RL:=NIL;     {у node нет братьев}
      node^.LL:=kuda;    {на отца}
      node^.Key:=chto;
      node^.Sign:=false;  {у node нет потомков}
      end
    else begin  
      node:=kuda^.LL;    {находим первого сына}
      while node^.RL<>NIL do
        begin node:=node^.RL; end;  {продвигаемся по правой ветви}
        node^.RL:=NIL;
        node^.LL:=kuda;
        node^.Key:=chto;
        node^.Sign:=false;  
      end;
end;

.
Подскажите, плз, как с этим разобраться...

Сообщение отредактировано: volvo - 3.11.2006 19:49

[volvo]

Jill, с удалением одного элемента у тебя проблема - дело в том, что если у узла есть потомок (Sign = True), то НИГДЕ не хранится адрес предка этого узла. Смотри сама: в RL хранится указатель на "братьев", а в LL - указатель на потомка. Как найти предка?

Единственное решение, которое будет работать и для Sign = True и для Sign = False: Проходить еще раз по всему дереву, и искать узел, содержимое RL (или LL при Sign=True) которого равняется адресу элемента, который ты нашла здесь:

  pp:=FindNode(T, ToDel);

только так ты можешь гарантированно найти предка PP.