VPF::[Pascal] двоичные деревья - Форум программистов

zavrrrrik

Дата 5.9.2007, 20:21 (ссылка)

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

Загрузка ...

Новичок

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

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

имеются двоичные деревья:
type
tree=^item;
item=record
data:real;
right,left:tree
end;
написать программу, которая меняет местами максимальный и минимальный элементы непустого дерева T, все элементы которого различны.

volvo877

Дата 5.9.2007, 20:28 (ссылка)

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

Загрузка ...

Эксперт

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

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

Небольшое уточнение: имеется в виду двоичное дерево поиска, или произвольное двоичное дерево?

zavrrrrik

Дата 5.9.2007, 21:04 (ссылка)

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

Загрузка ...

Новичок

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

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

кажется, произвольное двоичное дерево.) smile

volvo877

Дата 6.9.2007, 10:56 (ссылка)

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

Загрузка ...

Эксперт

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

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

zavrrrrik, почему же "не решить"? Все можно решить:

Код



type
  tree = ^item;
  item = record
    data: real;
    right, left: tree;
  end;


procedure Insert(var root: tree; X: real);

  procedure CreateNode(var p: tree; n: real);
  begin
    New(p);
    p^.data := n;
    p^.left := nil;
    p^.right := nil
  end;

begin
  if root = nil then CreateNode(Root, X)
  else
    with root^ do begin
      if data < X then Insert(Right, X)
      else
        if data > X Then Insert(Left, X);
  end;
end;

procedure print(level: integer; root: tree);
begin
  if root <> nil then begin
    print(level + 1, root^.left);
    writeln('':2*level, root^.data:5:2);
    print(level + 1, root^.right);
  end;
end;

function find_extreme(root: tree; var pt: tree; is_max: boolean): real;
var
  r_value, l_value: real;
  r_ptr, l_ptr: tree;
begin
  if (root = nil) or ((root^.left = nil) and (root^.right = nil)) then begin
    pt := root;

    if root = nil then find_extreme := (1 - 2*byte(is_max))*maxint
    else begin
      find_extreme := root^.data;
    end;
  end
  else begin
    r_value := find_extreme(root^.right, r_ptr, is_max);
    l_value := find_extreme(root^.left, l_ptr, is_max);

    if r_value > l_value = is_max then begin

      if root^.data > r_value = is_max then begin
        pt := root; find_extreme := root^.data
      end
      else begin
        pt := r_ptr; find_extreme := r_value;
      end;

    end
    else begin

      if root^.data > l_value = is_max then begin
        pt := root; find_extreme := root^.data
      end
      else begin
        pt := l_ptr; find_extreme := l_value;
      end;

    end;
  end;
end;

var
  root: tree;
  i: integer;
  max, min: tree;
  T: real;

begin
  root := nil;
  for i := 1 to 10 do Insert(root, 6*i);
  writeln('before');
  print(0, root); { это - исходное дерево }

  find_extreme(root, min, false);
  writeln('min = ', min^.data:5:2);
  find_extreme(root, max, true);
  writeln('max = ', max^.data:5:2);

  T := min^.data;
  min^.data := max^.data;
  max^.data := T;

  writeln('after:'); { Проверяем, поменялись ли местами min и max }
  print(0, root);
end.

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