Обход бинарного дерева, проблема с выводом Опции

[Rocket]

Использую реализацию, приведённую на сайте http://volvo71.narod.ru/faq_folder/bin_tree.htm.
Добавил случайную генерацию бинарного дерева (size вводим, а вершины - случайные числа). Вывожу графически, с помощью процедуры PrintTreeGraph.

uses Graph,crt;

type
	T = Integer;

	TTree = ^TNode;
	TNode = record
		value: T;
		Left, Right: TTree;
	end;

procedure PrintTreeGraph(Root: TTree);

	
function Convert(X: T): string;
  var st:string;
	begin
   str(X,st);
   Convert:= st;
    end;

var
	start_x, start_y: integer;
const
	delx = 30;
	dely = 20;
	circle_r = 10;
	btw = circle_r div 2;

	procedure print_node(Root: TTree; Level: Integer; L, C, R: Integer);
		function min(a, b: Integer): Integer;
		begin
			min := a;
			if b < a then min := b
		end;

		function Center(a, b: Integer): Integer;
		begin
			Center := min( a, B ) + abs( a - B ) div 2;
		end;

	var pos_y: integer;
	begin
		pos_y := start_y + pred(level) * dely;

		if Root^.Right <> nil then begin
			Line(C, pos_y, Center(C, R), pos_y + dely);
			print_node(root^.right, Level + 1, C+btw, Center(C+btw, R-btw), R-btw);
		end;

		if Root^.Left <> nil then begin
			Line(C, pos_y, Center(L, C), pos_y + dely);
			print_node(Root^.Left, Level + 1, L+btw, Center(L+btw, C-btw), C-btw);
		end;

		SetColor(Black);
		SetFillStyle(SolidFill, Black);
		PieSlice(C, pos_y, 0, 359, circle_r);
		SetColor(White);
		Circle(C, pos_y, circle_r);
		SetTextJustify(CenterText, CenterText);
		OutTextXY(C, pos_y, Convert(Root^.value));
	end;

begin
	start_x := GetMaxX div 2;
	start_y := 10;
	print_node(Root, 1, 0, GetMaxX div 2, GetMaxX);
end;


procedure Insert(var Root: TTree; X: T);

	procedure CreateNode(var p: TTree; n: T);
	begin
		New(p);
		p^.value := n;
		p^.Left := nil;
		p^.Right := nil
	end;

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

		
procedure PrintDown(Root: TTree);
begin
	if Root = nil then exit;
	with Root^ do begin
		Writeln(value, '':2);
		PrintDown(Left);
		PrintDown(Right)
	end
end;

procedure PrintLex(Root: TTree);
begin
	if Root = nil then exit;
	with Root^ do begin
		PrintLex(Left);
		Writeln(value, '':2);
		PrintLex(Right)
	end
end;

procedure PrintUp(Root: TTree);
begin
	if Root = nil then exit;
	with Root^ do begin
		PrintUp(Left);
		PrintUp(Right);
		Writeln(value, '':2);
	end
end;


var
    grDriver: integer;
    grMode: integer;
    ErrCode: Integer;

	i, size: Integer;
	myTree, wasfound: TTree;

	iV: array[1 .. 100] of Integer;


begin

  Randomize;
  grDriver := Detect;
  InitGraph(grDriver, grMode,'');
  ErrCode := GraphResult;
  if ErrCode <> grOk then begin
    Writeln('Graphics error:', GraphErrorMsg(ErrCode)); Halt(100);
  end;

	read(size);
	for i:=1 to size do
	iV[i]:=random(100);


	myTree := nil;
	for i := 1 to size do begin
		Insert(myTree, iv[i]);
   end;

	 PrintTreeGraph(myTree);
  
   PrintDown(myTree); WriteLn;
   writeLn;
    PrintLex(myTree); WriteLn;
    writeLn;
    PrintUp(myTree);  WriteLn;
    
readkey;
end.

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

[volvo]

бинарное дерево строится, а затем программа просто ждёт нажатия клавиши. Подскажите пожалуйста, как это исправить?

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

{ ... }
begin
  Randomize;

  { Еще в текстовом режиме вводим кол-во узлов }
  write('size = '); readln(size); { <--- Никогда не пользуйся Read, только ReadLn !!! }
  for i:=1 to size do
    iV[i]:=random(100);

  { Только теперь инициализируем графику }
  grDriver := Detect;
  InitGraph(grDriver, grMode,'');
  ErrCode := GraphResult;
  if ErrCode <> grOk then begin
    Writeln('Graphics error:', GraphErrorMsg(ErrCode)); Halt(100);
  end;

  { Это тоже можно было сделать ДО перехода в граф. режим, но ладно, можно и тут }
  myTree := nil;
  for i := 1 to size do begin
    Insert(myTree, iv[i]);
  end;

  { Теперь - самое главное: Рисуем дерево: }
  PrintTreeGraph(myTree);
  ReadLn; { <--- Посмотрел? Нажми Enter }

  CloseGraph; { <--- Вернемся в текстовый режим }
  PrintDown(myTree); Readln; { После каждого обхода - опять Enter, иначе первые затрутся последними }
  writeLn;
  PrintLex(myTree); ReadLn;
  writeLn;
  PrintUp(myTree);
  readkey;
end.

(процедуры обхода я поправлю на сайте, чтобы они выводили дерево в более наглядном виде, не так как сейчас...)

[Rocket]

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

{ ... }
begin
  Randomize;

  { Еще в текстовом режиме вводим кол-во узлов }
  write('size = '); readln(size); { <--- Никогда не пользуйся Read, только ReadLn !!! }
  for i:=1 to size do
    iV[i]:=random(100);

  { Только теперь инициализируем графику }
  grDriver := Detect;
  InitGraph(grDriver, grMode,'');
  ErrCode := GraphResult;
  if ErrCode <> grOk then begin
    Writeln('Graphics error:', GraphErrorMsg(ErrCode)); Halt(100);
  end;

  { Это тоже можно было сделать ДО перехода в граф. режим, но ладно, можно и тут }
  myTree := nil;
  for i := 1 to size do begin
    Insert(myTree, iv[i]);
  end;

  { Теперь - самое главное: Рисуем дерево: }
  PrintTreeGraph(myTree);
  ReadLn; { <--- Посмотрел? Нажми Enter }

  CloseGraph; { <--- Вернемся в текстовый режим }
  PrintDown(myTree); Readln; { После каждого обхода - опять Enter, иначе первые затрутся последними }
  writeLn;
  PrintLex(myTree); ReadLn;
  writeLn;
  PrintUp(myTree);
  readkey;
end.

(процедуры обхода я поправлю на сайте, чтобы они выводили дерево в более наглядном виде, не так как сейчас...)

volvo, а как всё-таки это более наглядно сделать? Например, чтобы возле каждой вершины выводился номер, согласно которому данная вершина была посещена?

[volvo]

а как всё-таки это более наглядно сделать?

Оно тебе надо, делать это? Как ты форматировать это все будешь, ты не подумал? Куда будешь номер выводить? Тут с самими вершинами столько мороки было, ты себе не представляешь, пока получилось что-то приличное. А ты хочешь еще один номер впихать куда-то... Или ты не о графическом, а о текстовом выводе, о процедурах PrintDown/Lex/Up ?

[Rocket]

Оно тебе надо, делать это? Как ты форматировать это все будешь, ты не подумал? Куда будешь номер выводить? Тут с самими вершинами столько мороки было, ты себе не представляешь, пока получилось что-то приличное. А ты хочешь еще один номер впихать куда-то... Или ты не о графическом, а о текстовом выводе, о процедурах PrintDown/Lex/Up ?

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

(процедуры обхода я поправлю на сайте, чтобы они выводили дерево в более наглядном виде, не так как сейчас...)

volvo, а Вы как представляете более "наглядный вид"?

[volvo]

А я уже поправил процедуры обходов, теперь они по крайней мере дают представление о структуре дерева, какой элемент находится на каком уровне (от этого зависит смещение):

; это вывод PrintDown
size = 10
71
  13
    5
    45
      33
        17
      52
        70
  82
    90

; PrintLex
    5
  13
        17
      33
    45
      52
        70
71
  82
    90

; PrintUp
    5
        17
      33
        70
      52
    45
  13
    90
  82
71

И порядок обхода сразу становится понятен: ведь значения элементов выводятся именно в порядке обхода, следовательно - просто сверху вниз, именно в таком порядке...

Теперь насчет графики. Можно попробовать добавлять к значению каждого элемента в скобках номер, под которым он "обходился", но дело-то все в том, что это может привести к нечитабельному отображению, один лист может налазить на другой, может вообще перекрываться... Если это действительно нужно, вот такое тебя не устроит:

? То есть, дерево выводится, как и выводилось, но внизу печатается список вершин в порядке прохождения?

[Rocket]

Теперь насчет графики. Можно попробовать добавлять к значению каждого элемента в скобках номер, под которым он "обходился", но дело-то все в том, что это может привести к нечитабельному отображению, один лист может налазить на другой, может вообще перекрываться... Если это действительно нужно, вот такое тебя не устроит:

? То есть, дерево выводится, как и выводилось, но внизу печатается список вершин в порядке прохождения?

Всё-таки это опять просто вывод, тоже самое только в графическом режиме...
Идея с добавлением в скобках довольно интересна и наглядна (пожалуй, лучшая альтернатива нумерации вершин). Но вот как оно отображаться-то будет, это камень преткновения. А если ограничить количество вершин, скажем до 15, и расчитать как дерево будет выводится, чтобы без накладок?

Вот ещё один вариант: по очереди отмечать вершину другим цветом?

[volvo]

Вот такой вариант:

procedure PrintTreeGraph(Root: TTree);
var
  count: integer;

  function Convert(X: T): string;
  var st:string;
  begin
    str(X,st);
    Convert:= st;
  end;

var
  start_x, start_y: integer;

const
  delx = 30;
  dely = 30;
  circle_r = 12;
  btw = circle_r div 2;

  procedure print_node(Root: TTree; Level: Integer; L, C, R: Integer);
    function min(a, b: Integer): Integer;
    begin
      min := a;
      if b < a then min := b
    end;
    function Center(a, b: Integer): Integer;
    begin
      Center := min( a, B ) + abs( a - B ) div 2;
    end;

    var
      pos_y: integer;
    begin
      pos_y := start_y + pred(level) * dely;

      if Root^.Right <> nil then begin
        Line(C, pos_y, Center(C, R), pos_y + dely);
        print_node(root^.right, Level + 1, C+btw, Center(C+btw, R-btw), R-btw);
      end;
      if Root^.Left <> nil then begin
        Line(C, pos_y, Center(L, C), pos_y + dely);
        print_node(Root^.Left, Level + 1, L+btw, Center(L+btw, C-btw), C-btw);
      end;

      SetColor(Black);
      SetFillStyle(SolidFill, Black);
      PieSlice(C, pos_y, 0, 359, circle_r);
      SetColor(White);
      Circle(C, pos_y, circle_r);
      SetTextJustify(CenterText, CenterText);

      inc(count);
      OutTextXY(C, pos_y - (textheight('w') div 2), Convert(Root^.value));
      setcolor(lightred);
      OutTextXY(C, pos_y + (textheight('w') div 2 + 1), Convert(count));
      setcolor(white);
    end;

var
  sub_s: string;
  p: integer;

begin
  count := 0;

  start_x := GetMaxX div 2;
  start_y := 10;
  print_node(Root, 1, 0, GetMaxX div 2, GetMaxX);
end;

выдает вот что:


Если

по очереди отмечать вершину другим цветом?

, то ты будешь ограничен 15-ю цветами, не очень подходяще для дерева...

[Rocket]

Вот такой вариант:

Идеальна!!! Супер получилось! Спасибо большое А как теперь непосредственно результаты обходов отобразить? И, на скриншоте,который Вы привели, какой-то обход изображён?

[volvo]

На скриншоте - концевой обход дерева. Ну, почти. Вообще-то при концевом обходе сначала проходится левое поддерево, потом - правое, и только потом - корень. У меня чуть-чуть не так: правое-левое-корень... Если поменять ветки if Root^.Right и if Root^.Left местами - то будет "классический" концевой обход. В этом можно будет убедиться, если сравнить результаты с текстовой процедурой PrintUp, вершины будут указаны в том же порядке (исправленные версии PrintDown/PrintLex/PrintUp можешь взять в файле TreeUnit.pas у меня на сайте. Он тоже был обновлен).

[Rocket]

На скриншоте - концевой обход дерева. Ну, почти. Вообще-то при концевом обходе сначала проходится левое поддерево, потом - правое, и только потом - корень. У меня чуть-чуть не так: правое-левое-корень... Если поменять ветки if Root^.Right и if Root^.Left местами - то будет "классический" концевой обход. В этом можно будет убедиться, если сравнить результаты с текстовой процедурой PrintUp, вершины будут указаны в том же порядке (исправленные версии PrintDown/PrintLex/PrintUp можешь взять в файле TreeUnit.pas у меня на сайте. Он тоже был обновлен).

Угу, с обходом на скриншоте понятно - так и предполагал, что это концевой(обратный) только "наоборот".
Одно понять не могу: в этой процедуре PrintTreeGraph уже сразу заложен алгоритм обхода?
Как под одной крышей собрать эти три обхода?

[volvo]

в этой процедуре PrintTreeGraph уже сразу заложен алгоритм обхода?

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

В принципе, можно сделать так:

    var
      pos_y: integer;
    begin
      pos_y := start_y + pred(level) * dely;

      SetColor(Black);
      SetFillStyle(SolidFill, Black);
      PieSlice(C, pos_y, 0, 359, circle_r);
      SetColor(White);
      Circle(C, pos_y, circle_r);
      SetTextJustify(CenterText, CenterText);

      inc(count);
      OutTextXY(C, pos_y - (textheight('w') div 2), Convert(Root^.value));
      setcolor(lightred);
      OutTextXY(C, pos_y + (textheight('w') div 2 + 1), Convert(count));
      setcolor(white);

      if Root^.Left <> nil then begin
        Line(C, pos_y, Center(L, C), pos_y + dely);
        print_node(Root^.Left, Level + 1, L+btw, Center(L+btw, C-btw), C-btw);
      end;
      if Root^.Right <> nil then begin
        Line(C, pos_y, Center(C, R), pos_y + dely);
        print_node(root^.right, Level + 1, C+btw, Center(C+btw, R-btw), R-btw);
      end;
    end;

(перенести рекурсивные вызовы в конец процедуры), и получить прямой обход. Можно и симметричный при желании получить, кстати. Тоже очень просто. Вот только тогда опять появляются проблемы при отображении: когда дерево отрисовывается концевым обходом, то сначала рисуются связи между узлами, и только потом - сами узлы. А при других обходах связи могут накладываться на уже отрисованные узлы, в результате - подпорченное изображение. Запусти то, что я привел в этом посте, поймешь о чем речь... Чтобы этого избежать, надо будет опять усложнять процедуру. А очень не хочется...

Хотя с другой стороны, какая тебе разница, каким обходом что отрисовано? ведь картинка-то получается всегда одна и та же, разница - только в порядке обхода (красные числа будут разными, больше - ничего). Хочешь - можешь чуть-чуть "пошаманить": Добавь в структуру TNode кроме поля Value еще 3 целочисленных поля (одно - для прямого, второе - для симметричного, третье - для обратного обхода), и запусти аналоги процедур обхода, но только не печатающие ничего на экран, а просто заполняющие соответствующее поле. А потом, при вызове PrintTreeGraph, просто указывать, какое из этих полей печатать красным цветом...

[Rocket]

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

В принципе, можно сделать так:

    var
      pos_y: integer;
    begin
      pos_y := start_y + pred(level) * dely;

      SetColor(Black);
      SetFillStyle(SolidFill, Black);
      PieSlice(C, pos_y, 0, 359, circle_r);
      SetColor(White);
      Circle(C, pos_y, circle_r);
      SetTextJustify(CenterText, CenterText);

      inc(count);
      OutTextXY(C, pos_y - (textheight('w') div 2), Convert(Root^.value));
      setcolor(lightred);
      OutTextXY(C, pos_y + (textheight('w') div 2 + 1), Convert(count));
      setcolor(white);

      if Root^.Left <> nil then begin
        Line(C, pos_y, Center(L, C), pos_y + dely);
        print_node(Root^.Left, Level + 1, L+btw, Center(L+btw, C-btw), C-btw);
      end;
      if Root^.Right <> nil then begin
        Line(C, pos_y, Center(C, R), pos_y + dely);
        print_node(root^.right, Level + 1, C+btw, Center(C+btw, R-btw), R-btw);
      end;
    end;

(перенести рекурсивные вызовы в конец процедуры), и получить прямой обход. Можно и симметричный при желании получить, кстати. Тоже очень просто. Вот только тогда опять появляются проблемы при отображении: когда дерево отрисовывается концевым обходом, то сначала рисуются связи между узлами, и только потом - сами узлы. А при других обходах связи могут накладываться на уже отрисованные узлы, в результате - подпорченное изображение. Запусти то, что я привел в этом посте, поймешь о чем речь... Чтобы этого избежать, надо будет опять усложнять процедуру. А очень не хочется...

Хотя с другой стороны, какая тебе разница, каким обходом что отрисовано? ведь картинка-то получается всегда одна и та же, разница - только в порядке обхода (красные числа будут разными, больше - ничего). Хочешь - можешь чуть-чуть "пошаманить": Добавь в структуру TNode кроме поля Value еще 3 целочисленных поля (одно - для прямого, второе - для симметричного, третье - для обратного обхода), и запусти аналоги процедур обхода, но только не печатающие ничего на экран, а просто заполняющие соответствующее поле. А потом, при вызове PrintTreeGraph, просто указывать, какое из этих полей печатать красным цветом...

В принципе, несмотря на небольшой косяк в отрисовке, всё равно выглядит очень прилично. Даже и не представляю как исправить-то можно, видно трудоёмкая работа...
Как теперь симметричный обход получить-то? Опять как-то хитро рекурсивные процедуры переставить))

[volvo]

Как теперь симметричный обход получить-то? Опять как-то хитро рекурсивные процедуры переставить))

Угу.. Ветку if Root^.Left <> nil перенести в начало процедуры (там, где она и была в сообщении №8), а ветку if Root^.Right <> nil оставить в самом конце. Тогда будет симметрично: Left-Root-Right