{==============================}
{ DEFINICAO DOS TIPOS DE DADOS }
{==============================}

Const
  SEM_PAI=-1;
Type
  TArvGen_Dado     =  Integer;
  Ptr_ArvGen_Nodo  =  ^ArvGen_Nodo;
  ArvGen_Nodo      =  Record
                         Dado: TArvGen_Dado;
			 Pai, Filho, Irmao:  Ptr_ArvGen_Nodo;
		       End;

{=======================}
{ DEFINICAO DAS ROTINAS }
{=======================}

{ Inicializa a arvore generica – Prepara para inserir dados }
Procedure ArvGen_Inicializa (Var Raiz: Ptr_ArvGen_Nodo);   
Begin
     Raiz := NIL;
End;


{ Insere um dado na arvore generica – Insere como filho do nodo indicado }
Procedure ArvGen_Insere_Filho (Var Pai: Ptr_ArvGen_Nodo; Dado: TArvGen_Dado);
Var
  novo:Ptr_ArvGen_Nodo;
Begin
  new(novo);
  novo^.dado:=dado;
  novo^.filho:=NIL;
  novo^.irmao:=NIL;
  if Pai = NIL
  then begin                   { Insere como Raiz da Arvore }
         Pai:=novo;
         novo^.pai:=NIL;
       end
  else if pai^.filho = NIL     { Insere o primeiro filho deste nodo }
       then begin
              Pai^.filho:=novo;
              novo^.pai:=Pai;
            end
       else begin              { Insere mais um filho deste nodo }
              novo^.irmao:=Pai^.filho;
              Pai^.filho:=novo;
              novo^.pai:=Pai;
            end;
End;


{ Insere um dado na arvore generica – Insere como irmao do nodo indicado }
{ Nao permite a insercao de nodos irmaos em relacao ao nodo raiz         }
Function ArvGen_Insere_Irmao (Var Filho: Ptr_ArvGen_Nodo; Dado: TArvGen_Dado): Boolean;
Var
  novo:Ptr_ArvGen_Nodo;
Begin
  if Filho = NIL
  then begin                { Insere como Raiz da Arvore }
	 new(novo);
  	 novo^.dado:=dado;
  	 novo^.filho:=NIL;
  	 novo^.irmao:=NIL;
         Filho:=novo;
         novo^.pai:=NIL;
         ArvGen_Insere_Irmao:=true;
       end
  else if Filho^.pai = NIL  { Erro: Tentativa de inserir um irmao no Raiz }
       then ArvGen_Insere_Irmao:=false
       else begin           { Insere mais um irmao deste nodo }
              arvgen_insere_filho(Filho^.pai,Dado);
	      ArvGen_Insere_Irmao:=true;
            end;
End;


{ Insere um dado na arvore generica – Insere como pai do nodo indicado    }
{ So permite a insercao de nodos pais para quem nao tem ainda pai => Raiz }
Function ArvGen_Insere_Pai (Var Filho: Ptr_ArvGen_Nodo; Dado: TArvGen_Dado): Boolean;
Var 
  novo:Ptr_ArvGen_Nodo;
Begin
  if Filho^.pai = NIL              { Insere pai do raiz }
  then begin
	 new(novo);
  	 novo^.dado:=dado;
  	 novo^.filho:=filho;
  	 novo^.irmao:=NIL;
         novo^.pai:=NIL;  
         Filho^.pai:=novo;
         ArvGen_Insere_Pai:=true;
       end
  else ArvGen_Insere_Pai:=false;   { Nao pode inserir: ja tem pai }
End;


{ Exibe o conteudo (dados) da arvore generica – em modo pre-fixado }
Procedure ArvGen_Exibe_Prefixado (Raiz: Ptr_ArvGen_Nodo); 
Begin
  if Raiz <> Nil
  then begin
         write('Nodo: ',Raiz^.dado:4,' - Pai: ');
         if (Raiz^.pai <> NIL)
         then writeln(Raiz^.pai^.dado)
         else writeln('(NIL - Este eh o nodo Raiz)');
         ArvGen_Exibe_Prefixado(Raiz^.irmao);
         ArvGen_Exibe_Prefixado(Raiz^.filho);
       end;
End;


{ Procura um dado na arvore e retorna um ponteiro para a primeira 
  ocorrencia deste dado, ou retorna NIL se nao achar }
Function  ArvGen_Pesquisa_Nodo (Raiz: Ptr_ArvGen_Nodo; Dado: TArvGen_Dado): Ptr_ArvGen_Nodo;  
Var
  Retorno:Ptr_ArvGen_Nodo;
Begin
  if Raiz <> NIL
  then begin
         if Raiz^.dado = dado
         then Retorno:=Raiz
         else begin
                Retorno:=ArvGen_Pesquisa_Nodo(Raiz^.irmao,Dado);
                if Retorno = NIL
                then Retorno:=ArvGen_Pesquisa_Nodo(Raiz^.filho,Dado);
              end;
       end
  else Retorno:=NIL;
  ArvGen_Pesquisa_Nodo:=Retorno;
End;


{ Salva em disco o conteúdo (dados) da árvore genérica }
Procedure ArvGen_Salva (Raiz: Ptr_ArvGen_Nodo); 
var
  ArqTxt:text;

   Procedure Salva_Recursiva(var Arq:Text; Raiz:Ptr_ArvGen_Nodo);
   Begin
     if Raiz <> NIL
     then begin
            if (Raiz^.pai <> NIL)
            then writeln(Arq,Raiz^.pai^.dado)
            else writeln(Arq,SEM_PAI);
            writeln(Arq,Raiz^.dado);
            Salva_Recursiva(Arq,Raiz^.irmao);
            Salva_Recursiva(Arq,Raiz^.filho);
          end;
   End;

Begin
  writeln('Salvando arquivo em disco...');
  assign(ArqTxt,'arvgen.txt');
  rewrite(ArqTxt);
  Salva_Recursiva(ArqTxt,Raiz);
  close(ArqTxt);
End;
{ -- Fim ArvGen Salva --}

{ Recupera do disco o conteudo (dados) da arvore generica }
Function  ArvGen_Le (Var Raiz: Ptr_ArvGen_Nodo): Boolean; 
var
  ArqTxt:Text;
  Pai,Filho:TArvGen_Dado;
  Ptr:Ptr_ArvGen_Nodo;
Begin
  if Raiz <> NIL
  then ArvGen_Le:=false      { Arvore deve estar vazia }
  else begin
         writeln('Lendo arquivo do disco...');
         arvgen_inicializa(Raiz);
         assign(ArqTxt,'arvgen.txt');
         reset(ArqTxt);
         while not eof(ArqTxt)
         do begin
              readln(ArqTxt,Pai);
              readln(ArqTxt,Filho);
              Ptr:=arvgen_pesquisa_nodo(Raiz,Pai);
              arvgen_insere_filho(Ptr,Filho);
              if Raiz=NIL
              then Raiz:=Ptr;
            end;
         close(ArqTxt);
       end;
End;


{ Apaga toda a arvore generica, liberando a memoria ocupada }
Procedure ArvGen_Apaga (Var Raiz: Ptr_ArvGen_Nodo);   
Begin
  if Raiz <> NIL
  then begin
         ArvGen_Apaga(Raiz^.irmao);
         ArvGen_Apaga(Raiz^.filho);
         Dispose(Raiz);
       end;
  Raiz:=NIL;
End;


{ Remove o nodo cujo ponteiro foi passado como parametro }
Function ArvGen_Remove_Nodo (Var Nodo: Ptr_ArvGen_Nodo):boolean;
Var
  aux:Ptr_ArvGen_Nodo;
Begin

  if Nodo = NIL  { Nao tem nodos para remover }
  then ArvGen_Remove_Nodo:= false
  else begin

  if Nodo^.filho <> NIL   { Se tem filhos, entao apaga toda a sub-arvore }
  then ArvGen_Apaga(Nodo^.filho);
  if Nodo^.pai = nil      { Se nao tem pai... eh o raiz }
  then begin
         dispose(Nodo);
         Nodo:=nil;
       end
  else begin              { Se tem pai... pode ter irmao anterior }
         if Nodo^.pai^.filho = Nodo   { Primeiro Filho }
         then begin
                Nodo^.pai^.filho:=Nodo^.irmao;
                dispose(Nodo);
              end
         else begin       { Tem um irmao antes dele, acha! }
                aux:=Nodo^.pai^.filho; { 1o. filho }
                while aux^.irmao <> Nodo
                do aux:=aux^.irmao;
                aux^.irmao:=Nodo^.irmao;
                dispose(Nodo);
              end;
       end;
  ArvGen_Remove_Nodo:=true;
 end;
End;

{ Remove o nodo que contem o valor indicado como parametro,
  indicando se conseguiu remover }
Function ArvGen_Remove_Dado (Var Raiz: Ptr_ArvGen_Nodo; Dado: TArvGen_Dado): Boolean;
var
  nodo:Ptr_ArvGen_Nodo;
Begin
  nodo:=arvgen_pesquisa_nodo(Raiz,Dado);
  if nodo = nil
  then begin
         writeln('ERRO: Nodo nao encontrado para remocao!');
         ArvGen_Remove_Dado:=False;
       end
  else begin
         if nodo=Raiz
         then Raiz:=nil;
         if ArvGen_Remove_Nodo(nodo)
         then ArvGen_Remove_Dado:=True
         else ArvGen_Remove_Dado:=False;
       end;
End;