IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Обход бинарного дерева, проблема с выводом
Rocket
сообщение 23.05.2009 8:45
Сообщение #1


Знаток
****

Группа: Пользователи
Сообщений: 306
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Использую реализацию, приведённую на сайте 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.




Проблема в том, что не выводятся сами обходы: бинарное дерево строится, а затем программа просто ждёт нажатия клавиши. Подскажите пожалуйста, как это исправить? Или сделать вообще, чтоб вообще выводились эти обходы...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
volvo
сообщение 23.05.2009 9:52
Сообщение #2


Гость






Цитата
бинарное дерево строится, а затем программа просто ждёт нажатия клавиши. Подскажите пожалуйста, как это исправить?
Посмотреть внимательно, и увидеть, что 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
сообщение 23.05.2009 22:14
Сообщение #3


Знаток
****

Группа: Пользователи
Сообщений: 306
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Цитата(volvo @ 23.05.2009 10:52) *

Посмотреть внимательно, и увидеть, что 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, а как всё-таки это более наглядно сделать? Например, чтобы возле каждой вершины выводился номер, согласно которому данная вершина была посещена?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
Rocket   Обход бинарного дерева   23.05.2009 8:45
volvo   Посмотреть внимательно, и увидеть, что PrintTreeGr...   23.05.2009 9:52
Rocket   Посмотреть внимательно, и увидеть, что PrintTreeG...   23.05.2009 22:14
volvo   Оно тебе надо, делать это? Как ты форматировать эт...   24.05.2009 0:08
Rocket   Оно тебе надо, делать это? Как ты форматировать э...   24.05.2009 10:46
volvo   А я уже поправил процедуры обходов, теперь они по ...   24.05.2009 11:44
Rocket   Теперь насчет графики. Можно попробовать добавля...   24.05.2009 13:50
volvo   Вот такой вариант: procedure PrintTreeGraph(Root: ...   24.05.2009 14:08
Rocket   Вот такой вариант:Идеальна!!! Супер по...   24.05.2009 17:10
volvo   На скриншоте - концевой обход дерева. Ну, почти. В...   24.05.2009 20:42
Rocket   На скриншоте - концевой обход дерева. Ну, почти. ...   24.05.2009 21:15
volvo   Угу... Причем это обязательно должен быть концевой...   24.05.2009 22:05
Rocket   Угу... Причем это обязательно должен быть концево...   24.05.2009 22:50
volvo   Угу.. Ветку if Root^.Left <> nil перенести в...   24.05.2009 22:57


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

- Текстовая версия 30.07.2025 22:18
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"