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

[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

[Jill]

Написала функцию поиска предыдущего элемента. Что-то длинноватая получилась, но работает:

 function FindPreceding(T,pp:PTree):PTree;   {pp - найденный узел}
var p:PTree;
begin
  FindPreceding:=nil;
  if T=nil then exit;
  if T^.RL=pp then
    begin
      FindPreceding:=T; exit;
    end;
  if (T^.Sign) and (T^.LL=pp) then
    begin
      FindPreceding:=T; exit;
    end;
  if T^.Sign then
    begin
      p:=FindPreceding(T^.LL,pp);
      FindPreceding:=p;
        if p<>NIL then exit;
    end;
  if T^.RL<>NIL then
    begin p:=FindPreceding(T^.RL,pp);
      FindPreceding:=p;
        if p<>NIL then exit;
    end;
end;  

Теперь удаление:

 procedure DeleteNode(T:PTree;ToDel:string);
var pred,posl,p:PTree;
begin
     p:=FindNode(T,ToDel);      {p указывает на выбранный узел}
      if p<>NIL then begin      {если узел найден, то...}

       if p^.LL=NIL then
          begin
            DeleteTree(p); {найденный узел - корень дерева}
            exit;
          end;

       pred:=FindPreceding(root,p);
       if p^.Sign then         {удаление поддерева без выбранного узла}
        begin
          posl:=p^.LL;         {?как быть с левым указателем?}
          DeleteTree(posl);
       end;

       if p^.RL=NIL then   {если узел не имеет "младших" братьев}
          begin
            pred^.RL:=NIL;
            dispose(p)
          end
       else
        if p^.RL<>NIL then  {если узел имеет "младшего" брата}
          begin
             if pred^.RL=p then    {если предыдуший узел - "старший" брат}
                begin
                  posl:=p^.RL;
                  pred^.RL:=posl;
                  dispose(p);
                end;
             if (pred^.Sign)and(pred^.LL=p) then   {если предыдуший узел - отец}
                begin
                  posl:=p^.RL;
                  pred^.LL:=posl;
                  dispose(p);
                end;
           end;
       end;
end;

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