VPF::Обход бинарного дерева - Форум программистов

Vandalko

Дата 18.5.2009, 13:20 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 7.5.2007

Репутация: нет
Всего: нет

Цитата

....элемент из самого левого листа непустого дерева Т (лист—вершина, из которой не выходит ни одной ветви);

Вот и вопрос - как найти этот самый левый лист ?

Уже есть некоторое решение:

Код


procedure PrintByLevel(level: integer;
          var items: array of TTree; count: integer);
var i, new_count: integer;
begin
  if count <> 0 then begin

    writeln('level = ', level);
    new_count := 0;
    for i := 0 to pred(count) do begin
      write(items[i]^.value:4);
      if items[i]^.left <> nil then begin
        inc(new_count); items[count + new_count - 1] := items[i]^.left;
      end;
      if items[i]^.right <> nil then begin
        inc(new_count); items[count + new_count - 1] := items[i]^.right;
      end;
    end;
    writeln;
    move(items[count], items[0], new_count*sizeof(TTree));
    PrintByLevel(level + 1, items, new_count);

  end;
end;

И вызивается она так:

Код


var
  arr: array[0 .. pred(size)] of TTree; { <--- Здесь должно быть достаточно места для хранения }

begin
  { Заполнение дерева }
  ...
  arr[0] := root;
  PrintByLevel(0, arr, 1);
  ...
end.

Но что это за pred() и sizeof() ? smile

Взято с http://volvo71.narod.ru/faq_folder/bin_tree.htm

Это сообщение отредактировал(а) Vandalko - 18.5.2009, 13:30

cemick

Дата 18.5.2009, 15:59 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 416
Регистрация: 6.7.2006
Где: Санкт-Петербург

Репутация: нет
Всего: 6

Дак тогда же можно просто перебором в цикле:

Код


Node: TNode;

Node := tree.Top;
while Node^.Left <> nil do
  Node  := Node^.Left;

В конце перебора он дойдет до самого левого узла..

volvo877

Дата 19.5.2009, 09:43 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

Цитата(Vandalko @ 18.5.2009, 13:20

)

Но что это за pred() и sizeof()

У тебя хелп отключен что-ли в Паскале? Подведи курсор к интересующему тебя слову, и нажми на Ctrl+F1...

И при чем тут вообще моя процедура к твоему заданию? Никакой связи не вижу... Процедура по уровням печатает дерево, а не находит какой-то там левый лист...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »