Технический форум

Технический форум (http://www.tehnari.ru/)
-   Помощь студентам (http://www.tehnari.ru/f41/)
-   -   Уточнение: является ли деревом сортировки (http://www.tehnari.ru/f41/t103949/)

Asya_inter 25.08.2015 17:03
Уточнение: является ли деревом сортировки
 
Здравствуйте, проверьте пожалуйста. Верно ли сделано? Дано такое задание: Построить двоичное дерево сортировки.

Вот решение:
Код:
program trees;

type
  pTree = ^Tree;
  Tree = record
      name: integer;
      left: pTree;
      right: pTree
  end;

var
  s: integer;
  t: pTree;
  n, i: integer;

procedure insert(var T: pTree; x: integer);
begin
  if T = nil then begin
      new(T);
      T^.name := x;
      T^.left := nil;
      T^.right := nil;
  end
  else  if T^.name >= x then
      insert(t^.left, x) 
  else insert(t^.right, x);
end;

procedure obhod(t: Ptree);
begin
  if T <> nil then begin
      obhod(T^.left);
      write(t^.name,',');
      obhod(t^.right);
  end;
end;

begin
  write('kol-vo chisel: ');
  read(n);
  t := nil;
  for i := 1 to n do
  begin
      read(s);
      insert(t, s);
  end;
  write('result. sortirovki: ');
  obhod(t);
  readln;
end.

MagentaTiger 25.08.2015 17:22
На первый взгляд все верно, единственное по уму надо бы дерево в конце программы "разрушить", т.е. освободить память, но для данного примера это не критично, ну и концептуально, я бы в основной программе не стал вводить количество вводимых цифр, а заканчивал бы ввод спецсимволом, т.е. если например введен "!" (естественно тогда переменная s должна быть char и после проверки на ! ее надо преобразовывать в integer) - то закончить ввод и вывести дерево ...

Asya_inter 25.08.2015 17:48
MagentaTiger, спасибо!
Я переделала, но наверное неправильно... Поясните, не совсем поняла - если тип char, то воспринимаются только цифры. А ещё будьте добры, расскажите как освободить память?
Код:
program trees;

type
  pTree = ^Tree;
  Tree = record
      name: char;
      left: pTree;
      right: pTree
  end;

var
  s: char;
  t: pTree;
  n, i: integer;

procedure insert(var T: pTree; x: char);
begin
  if T = nil then begin
      new(T);
      T^.name := x;
      T^.left := nil;
      T^.right := nil;
  end
  else  if T^.name >= x then
      insert(t^.left, x) 
  else insert(t^.right, x);
end;

procedure obhod(t: Ptree);
begin
  if T <> nil then begin
      obhod(T^.left);
      write(t^.name,',');
      obhod(t^.right);
  end;
end;

begin
  write('vvedi chisla: ');
  repeat
 
      read(s);
      insert(t, s);
  until s='!';
  write('result. sortirovki: ');
  obhod(t);
  readln;
end.

Asya_inter 25.08.2015 18:37
А ещё, такой вот вопрос: можно ли относительно данной задачи, решить ещё одну: Посчитать разность для каждой вершины полученного дерева между количеством левых и правых поддеревьев. . Как я поняла, там требуется посчитать количество левых и правых у каждой. Ну это ещё понятно вроде как сделать, но как ответ оформить?? Что на выходе должно быть?


Часовой пояс GMT +4, время: 23:27.

Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.