n-арное двусвязное дерево. Добавление, поиск, удаление., Помогите найти ошибку в удалении. Опции

[kramolnic]

Помогите, пожалуйста, найти ошибку в моей программе.
Сделал добавление и рекурсивный вывод, однако удаление не работает как надо. Если создать дерево, а потом скомандовать удалить элемент, то стираются все его дочерние элементы (освобождается выделенная под них память), однако при распечатке он видит удаленные элементы!
Немного о программе. Дерево реализовано так, что в каждом узле (персона, TPerson) находится информация о человеке (PersonData), ссылка на его родителя (Parent: PPerson) и список (TList) ссылок на дочерние элементы (каждый из которых также TPerson). Добавление производится по номеру элемента в индексном списке (этот список хранится в структуре TTree под именем ItemList). Сначала программа выводит дерево. Для этого сначала очищается ItemList, затем в этот список процедурой IndexTree, производящей рекурсивный обход дерева, упорядоченно заносятся элементы дерева (сверху вниз, как на экране), после чего распечатывается уже список, в котором находится структура дерева. Список ItemList был добавлен для осуществления добавления дочерних элементов по номеру родителя, а также для поиска. Кстати, пытался сначала сделать удаление без рекурсии, используя этот ItemList - результат: Stack Overflow при попытке вывода (вылетает при обходе дерева рекурсией). Видимо, где-то не верно уничтожаются указатели.
В данном файле удаление сделано рекурсивно (процедура Kill), но она работает как я уже описал. Помогите разобраться наконец, а то я уже дня четыре пытаюсь понять, что тут не верно тремя способами удаление делал - два стэк переполняют ПРИ ВЫВОДЕ, а третий работает криво. Кстати, после удаления элементы как надо не добавляются...

Сообщение отредактировано: kramolnic - 16.05.2007 2:08

[volvo]

Что-то ты там перемудрил по-моему с отображением дерева... Вот, смотри, что я сделал:

{ Немного меняем Kill }
procedure Kill (var tree: TTree; Ref: PPerson);
var curEl: PListItem;
begin
  CurEl:= Ref^.ChildList.Head;
  While CurEl <> nil do begin
    Kill(Tree, CurEl^.Children);
    CurEl:= CurEl^.Next;
  end;
end;

{ и пишем "обертку" к нему для выполнения доп. действий }
procedure Killer (var tree: TTree; var Ref: PPerson);
var p: PListItem;
begin

  p := Ref^.parent^.ChildList.Head;
  while p^.next^.children <> Ref do begin
    p := p^.next;
  end;

  Kill(Tree, Ref);

  p^.next := p^.next^.next;
  dispose(Ref^.ChildList.head);
  dispose(Ref);
  Ref := nil;
end;

Вызываем все это дело так:

var pp: PPerson;

...
WriteLn('What Person do you want to delete? ');
Readln(n);

  pp := FindRef(Tree.ItemList, n); { var-параметр, нельзя напрямую подставлять вызов функции }
  Killer(tree, pp);

  PrintTree(tree);

Понимаешь, в чем идея? при удалении узла просто переходить на его предка, и в Детях предка искать предшествующий удаляемому узел, потом - удаление всех Детей узла твоей процедурой Kill, и то, зачем искали предшествующий удаляемому элемент - просто делаем так, чтобы указатель "перескакивал" его, не замечал, попутно возвращая память...

НО... (опять это вездесущее слово но ) Это срабатывает только тогда, когда удаляется последняя ветка (на приаттаченной картинке - узел №5)... При попытке удалить узел №3, например, возникает ошибка.

Попробуй разобраться, может я чего-то очевидного уже не замечаю, или ты где-то ошибся в указателях при создании дерева, поэтому некорректно это все обрабатывается сейчас, при удалении... Протрассируй программу с моим решением, ты все равно знаешь ее структуру лучше меня...