Деревья Опции

[Aleks]

Здраствуйте
Прошу помощи в решение задачи: Подсчитать число вершин на n-ом уровне непустого дерева Т (корень считать вершиной нулевого дерева)
я в этом плохо разбираюсь, но кое-что написал

Исходный код

uses crt;
type
pitem=^titem;
titem=record
data:string;
pred:pitem;
next:pitem;
end;

var
first,last:pitem;
ff:text;
ss:string;
i:integer;

procedure add(ss:string);
var
newitem:pitem;
d:string;
begin
for i:=1 to length(ss) do
begin
d:=ss[1+length(ss)-i];
new(newitem);
newitem^.data:=d;
newitem^.pred:=nil;
newitem^.next:=first;
first:=newitem;
if last=nil then last:=newitem;
end;
end;

procedure print;
begin

end;

procedure del;
var
delitem:pitem;
begin
delitem:=first;
if delitem<>nil then
begin
first:=delitem^.next;
delitem^.Pred^.Next:=delitem^.Next;
dispose(delitem);
end;
end;

begin
{ clrscr; }
writeln('--' , memavail);

assign(ff,'E:\derevo.txt');
reset(ff);
while not (eof(ff)) do
begin
readln(ff,ss);
writeln(ss);
end;
add(ss);
del;
close(ff);
writeln('--' , memavail);
readln;
end.

[Aleks]

проверьте правильно сделал или нет

Исходный код

uses crt;
type
ttype=record
n:integer;
count:integer;
end;

TTree=^TNode;
TNode=Record
data:TType;
Left, Right:TTree;
end;

var
t:TTree;
ff:text;
d,ss:string;
i:integer;

procedure add(var T: TTRee; i:Integer);

procedure CreateNode(var p:TTRee; n:integer);
begin
new(p);
p^.Data.n:=n;
p^.Data.Count:=1;
p^.Left:=nil;
p^.Right:=nil;
end;

begin
if t<>nil then
with t^ do
begin
if Data.n<i then Add(Right,i)
else
if Data.n>i then Add(Left,i)
else Inc(Data.Count)
end
else
CreateNode(T,i);
end;

procedure Delete(T: TTRee);
begin
if T=nil then Exit;

delete(T^.Right);
delete(T^.left);
dispose(t);
end;


begin
writeln('--' , memavail);

assign(ff,'E:\derevo.txt');
reset(ff);
while not (eof(ff)) do
begin
readln(ff,ss);
{writeln(ss);}
end;
for i:=1 to length(ss) do
begin
d:=ss[1+length(ss)-i];
add(T,1);
end;
delete(t);
close(ff);

writeln('--' , memavail);
readln;
end.

вопрос: по процедуре add, я хотел бы понять ее действие

Код

 if t<>nil then
 with t^ do
 begin
   if Data.n<i then Add(Right,i)
   else
     if Data.n>i then Add(Left,i)
       else Inc(Data.Count)
 end
 else
   CreateNode(T,i);

[volvo]

вопрос: по процедуре add, я хотел бы понять ее действие

Дело в том, что бинарные деревья так устроены, что

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

Отсюда и реализация Add:

Procedure Add(Var T: TTree; i: Integer);

  Procedure CreateNode(Var p: TTree; n: Integer);
  Begin { ... } End;

  Begin
    If T <> nil Then { если текущий корень не пустой, то ... }
      With T^ Do Begin
        { ... если элемент данных > корневого }
        If Data.n < i Then Add(Right, i) { то добавить его в правое поддерево }
        Else { ... если элемент данных < корневого }
           If Data.n > i Then Add(Left, i) { то добавить его в левое поддерево }

           {
             если добавляемый и корневой элемент равны, 
             то просто увеличить счетчик значений корневого элемента
           }
           Else Inc(Data.Count)
       End
   Else { текущий корень пуст, то есть элемент должен быть создан }
     CreateNode(T, i) { тогда создаем его ... }
 End;

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

Скорее всего, тебе надо добавлять НЕ целые числа, а символы или строки, так поменяй типы там где надо...