{$mode objfpc}
unit treeunit;
interface
type PNode=^TNode;
	 TNode=record
		key:integer;
		pleft,pright:pnode;
	 end;
	 TTreeAction=procedure(key:integer; deep:integer);
	 TWalkType=(RAB,RBA, ARB,BRA, ABR,BAR);

procedure TreeAction(proot:pnode; proc:TTreeAction; wtype:TWalkType=RAB); 
procedure insertNode_sort(var x:pnode;k:integer);
function locateNode_sort(proot:pnode; key:integer):pnode;
function CreateNode(key:integer):Pnode;

implementation
{
X Xп Xл K
1 X=nil, K, end
2 K>X, Xп, 1
3 K<X, Xл, 1
4 K=X, K между X и Xп, Xп->Kп
}
function CreateNode(key:integer):Pnode;
begin
 new(result); //fillbyte(result^,0,sizeof(TNode)); ? ? ?
 result^.pleft:=nil;
 result^.pright:=nil;
 Result^.key:=key;
end;

procedure insertnode_sort(var x:pnode;k:integer);
var n1:pnode;
begin
//writeln('--------', ptruint(x));
if x=nil then begin x:=createnode(k); exit; end;
if k>x^.key then begin insertnode_sort(x^.pright,k); exit; end;
if k<x^.key then begin 
// writeln('begin ',k,' ', ptruint(x^.pleft));
 insertnode_sort(x^.pleft,k); 
// writeln('begin ',k);
 exit; 
end;
n1:=createnode(k);
n1^.pright:=x^.pright;
x^.pright:=n1;
end;

function locateNode_sort(proot:pnode; key:integer):pnode;
 var c:integer;
begin
 c:=0;
 while (proot<>nil) do begin
  inc(c);
  if proot^.key=key then break;
  if proot^.key>key then proot:=proot^.pleft else proot:=proot^.pright; 
 end;
 result:=proot;
 writeln (stderr,'Iterations: ',c);
end;

procedure TreeAction(proot:pnode; proc:TTreeAction; wtype:TWalkType=RAB);

procedure InWalk(pr:pnode;deep:integer);
begin
If pr=nil then exit;
case wtype of

 RAB: begin
	with pr^ do begin
		proc(key,deep);
		InWalk(pleft,deep+1);
		InWalk(pright,deep+1);
	end;
 end;
 
 RBA: begin
	with pr^ do begin
		proc(key,deep);
		InWalk(pright,deep+1);
		InWalk(pleft,deep+1);
	end;
 end;
 
 ARB: begin
	with pr^ do begin
		InWalk(pleft,deep+1);
		proc(key,deep);
		InWalk(pright,deep+1);
	end;
 end;
 
 BRA:begin
	with pr^ do begin
		InWalk(pright,deep+1);
		proc(key,deep);
		InWalk(pleft,deep+1);
	end;
 end;
 
 ABR:begin
	with pr^ do begin
		InWalk(pleft,deep+1);
		InWalk(pright,deep+1);
		proc(key,deep);
	end;
 end;
 
 BAR:begin
	with pr^ do begin
		InWalk(pright,deep+1);
		InWalk(pleft,deep+1);
		proc(key,deep);
	end;
 end;
 
 end;
end;
 
 begin  
  InWalk(proot,0);
 end;




end.