1

Мне нужна помощь в составлении алгоритма генерации последовательности чисел для составления бинарного дерева поиска. Дерево всегда четырехуровневое и полное. Все числа в последовательности не больше двух знаков.

Пока я дошел до такого кода, но из-за того что я не могу полностью продумать логику алгоритма, код выдает неверные значения:

  rand:=Random(100);
  rand1:=RandomRange(0, rand);
  rand2:=RandomRange(rand+1, 100);

  rand3:=RandomRange(0, rand1);
  rand4:=RandomRange(rand1+1, rand);

  rand5:=RandomRange(rand,rand2);
  rand6:=RandomRange(rand2+1, 100);

  rand7:=RandomRange(0, rand3);
  rand8:=RandomRange(rand3+1, rand1);

  rand9:=RandomRange(0, rand4);
  rand10:=RandomRange(rand4+1, rand);

  rand11:=RandomRange(rand2, rand5);
  rand12:=RandomRange(rand5+1, 100);

  rand13:=RandomRange(rand2, rand6);
  rand14:=RandomRange(rand6+1, 100); 

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

1 ответ 1

1

Получилось примерно следующее (Pascal ABC.net):

program bin_tree;

function LeftNode(root, step: integer): integer;
begin
  Result := Random(root - step, root - 1);
end;

function RightNode(root, step: integer): integer;
begin
  Result := Random(root, root + step);
end;

const
  LEVEL: integer = 4; // максимальный уровень дерева
  MAX_VALUE: integer = 99; // максимальное значение узла
var
  step: integer;
  root: integer;
  i: integer;
  level1: array[0..1] of integer;
  level2: array[0..3] of integer;
  level3: array[0..7] of integer;
begin
  step := Trunc(MAX_VALUE / ((LEVEL * 2) - 1)); // шаг формирования узлов

  root := step * LEVEL; // корневой узел

  Randomize;

  level1[0] := LeftNode(root, step);
  level1[1] := RightNode(root, step);

  level2[0] := LeftNode(level1[0], step);
  level2[1] := RightNode(level1[0], step);
  level2[2] := LeftNode(level1[1], step);
  level2[3] := RightNode(level1[1], step);

  level3[0] := LeftNode(level2[0], step);
  level3[1] := RightNode(level2[0], step);
  level3[2] := LeftNode(level2[1], step);
  level3[3] := RightNode(level2[1], step);
  level3[4] := LeftNode(level2[2], step);
  level3[5] := RightNode(level2[2], step);
  level3[6] := LeftNode(level2[3], step);
  level3[7] := RightNode(level2[3], step);

  WritelnFormat('{0,17:D}', root);
  Writeln();
  WritelnFormat('{0,8:D}  {1,16:D}', level1[0], level1[1]);
  Writeln();
  WritelnFormat('{0,4:D}{1,8:D}{2,10:D}{3,8:D}', level2[0], level2[1],     level2[2], level2[3]);
  Writeln();
  WritelnFormat('{0,2:D}{1,4:D}{2,4:D}{3,4:D}{4,6:D}{5,4:D}{6,4:D}{7,4:D}', level3[0], level3[1], level3[2], level3[3], level3[4], level3[5], level3[6], level3[7]);
end.

Вывод такой:

               56

      48                67

  37      51        56      78

32  48  50  64    42  61  73  81

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.