(* tra04.h4.21-24.pohja.p SJ *)
program binpuutehtavat;

uses tra;

(* tehtävä 21 *)
(*  Kirjoita algoritmi, joka lisää sisäjärjestyksessä olevaan
    binääripuuhun uuden solmun siten, että puu säilyy
    sisäjärjestyksessä.  Jos samannimiöinen solmu oli jo puussa, niin
    solmua ei lisätä puuhun.  Parametrina puu ja ELEMENT, algoritmi luo
    uuden solmun jos lisäys tehdään. Aikavaativuus? Tilavaativuus? *)
procedure inorder_btree_insert(T : BTREE; x : ELEMENT);
begin
end; (* inorder_btree_insert *)



(* tehtävä 22) *)
(*  Kirjoita algoritmi joka etsii binääripuun matalimman (vähiten syvän)
    lehtisolmun. Aikavaativuus? Tilavaativuus? *)

function matalin_lehti(T : BTREE) : BTREE_NODE;
begin
end; (* matalin_lehti() *)
		

(* tehtävä 23 *)
(*  Kirjoita algoritmi joka palauttaa binääripuun annetun solmun
    edeltäjäsolmun sisäjärjestyksessä. Otsikko siis
    BTREE_INORDER_PREV(T : BTREE; N : BTREE_NODE) : BTREE_NODE;
    Aikavaativuus? Mikä on kokonaisaikavaativuus kun tätä algoritmia
    kutsutaan koko puun läpi, ts.  aloittaen sisäjärjestyksessä
    viimeisestä alkiosta ja toistaen aina edelliseen alkioon n kertaa
    (missä n on puun alkioiden lukumäärä)?  Huomaa, ettei puun alkioiden
    tarvitse olla sisäjärjestyksessä.  Itseasiassa et edes tarvitse
    alkioita lainkaan, puun rakenne riittää. *)
function inorder_btree_prev(T : BTREE; n : BTREE_NODE) : BTREE_NODE;
begin
end; (* inorder_btree_prev() *)
			

(* tehtävä 24 *)
(*  Kirjoita algoritmi, joka vertaa kahta binääripuuta ja palauttaa
    toden jos puut ovat samat, muuten epätoden. Puut ovat samat, jos
    juuren molemmat alipuut ovat keskenään samanlaiset. Nimiöitä (puun
    sisältämiä elementtejä) ei vertailla, vain puun rakennetta.
    Aikavaativuus?  Tilavaativuus? *)
function btree_same_structure(T1, T2 : BTREE) : boolean;
begin
end;


(* esimerkki: onko sisäjärjestetyssä puussa samat alkiot *)
(* voivat olla eri järjestyksessä *)
function inorder_btree_samat_alkiot(T1, T2 : BTREE) : boolean;
	var n1, n2 : BTREE_NODE;
		samat : boolean;
begin
  samat := true;

  n1 := inorder_btree_prev(T1, BTREE_NIL);
  n2 := inorder_btree_prev(T2, BTREE_NIL);

  while ((n1 <> BTREE_NIL) and (n2 <> BTREE_NIL) and samat) do begin
	  if (not BTREE_SAME(T1, BTREE_RETRIEVE(T1, n1),
	  					 BTREE_RETRIEVE(T2, n2))) then
		  samat := false;
	  n1 := inorder_btree_prev(T1, n1);
	  n2 := inorder_btree_prev(T2, n2);
  end;

  if ((n1 <> BTREE_NIL) or (n2 <> BTREE_NIL)) then
	  samat := false;

  inorder_btree_samat_alkiot := samat;

end; (* inorder_btree_samat_alkiot() *)


(* tulostus sisäjärjestyksessä, oksa *)
procedure inorder_print_branch(T : BTREE; n : BTREE_NODE);
begin
	if (n <> BTREE_NIL) then begin
		inorder_print_branch(T, BTREE_LEFTCHILD(T, n));
		TREE_PRINT_NODE(T, n);		(* tms hyödyllistä *)
		write(' ');
		inorder_print_branch(T, BTREE_RIGHTCHILD(T, n));
	end;
end;

(* tulostus sisäjärjestyksessä, koko puu *)
procedure inorder_print(T : BTREE);
begin
	inorder_print_branch(T, BTREE_ROOT(T));
end;


(* tulostus tasoittain *)
procedure tulosta_tasoittain(T : BTREE);
	var Q : QUEUE;
		n : BTREE_NODE;
begin
	VOIDPTR_QUEUE_CREATE(Q);

	VOIDPTR_QUEUE_ENQUEUE(Q, BTREE_ROOT(T));
	while (not QUEUE_EMPTY(Q)) do begin
	
		n := VOIDPTR_QUEUE_FRONT(Q);
		QUEUE_DEQUEUE(Q);

		BTREE_PRINT_NODE(T, n);
		write(' ');

		if (BTREE_LEFTCHILD(T, n) <> BTREE_NIL) then
			VOIDPTR_QUEUE_ENQUEUE(Q, BTREE_LEFTCHILD(T, n));
		
		if (BTREE_RIGHTCHILD(T, n) <> BTREE_NIL) then
			VOIDPTR_QUEUE_ENQUEUE(Q, BTREE_RIGHTCHILD(T, n));

	end; (* while() *)

	QUEUE_FREE(Q);

end; (* tulosta_tasoittain() *)
		

(* kokeellinen osa *)
const	N = 10;		(* lisättävät alkiot *)
		M = 100;	(* maksimi alkio *)

var puu1, puu2 : BTREE;
	L : LIST;
	p : LIST_POSITION;

begin

  (* luodaan syöte listaan *)
  INT_LIST_CREATE(L);
  LIST_CONSTRUCT_RANDOM(L, N, 1, M);
  LIST_PRINT(L); writeln;

  (* puu1:een alkiot alusta loppuun *)
  BTREE_CREATE(puu1, LIST_TYPE(L));
  p := LIST_FIRST(L);
  while (p <> LIST_EOL(L)) do begin
	  inorder_btree_insert(puu1, LIST_RETRIEVE(L, p));
	  write(INT_LIST_RETRIEVE(L, p), ' ');
	  p := LIST_NEXT(L, p);
  end;
  writeln;

  (* puu2:een alkiot lopusta alkuun *)
  BTREE_CREATE(puu2, LIST_TYPE(L));
  p := LIST_LAST(L);
  while (p <> LIST_FIRST(L)) do begin
	  inorder_btree_insert(puu2, LIST_RETRIEVE(L, p));
	  p := LIST_PREVIOUS(L, p);
  end;
  (* silmukka jätti ekan alkion lisäämättä ! *)

  write('puu1 tas : '); tulosta_tasoittain(puu1); writeln;
  write('puu1 sis : '); inorder_print(puu1); writeln;
  write('puu2 sis : '); inorder_print(puu2); writeln;

  writeln('Vertailu_alkiot: ', inorder_btree_samat_alkiot(puu1, puu2));

  (* lisätään vielä eka alkio *)
  inorder_btree_insert(puu2, LIST_RETRIEVE(L, LIST_FIRST(L)));
  write('puu2 sis : '); inorder_print(puu2); writeln;

  writeln('Vertailu_alkiot: ', inorder_btree_samat_alkiot(puu1, puu2));
  writeln('Vertailu_rakenne: ', btree_same_structure(puu1, puu2));

  (* rakennetaan puu2 uudestaan *)
  BTREE_FREE(puu2);
  BTREE_CREATE(puu2, LIST_TYPE(L));
  p := LIST_FIRST(L);
  (* samat alkiot, mutta kerrottuna kahdella *)
  (* järjestys (ja siis puun rakenne) pitäisi säilyä samana *)
  while (p <> LIST_EOL(L)) do begin
  	inorder_btree_insert(puu2, INT_ELEMENT(2*INT_LIST_RETRIEVE(L, p)));
	p := LIST_NEXT(L, p);
  end;

  write('puu2 sis : '); inorder_print(puu2); writeln;
  writeln('Vertailu_alkiot: ', inorder_btree_samat_alkiot(puu1, puu2));
  writeln('Vertailu_rakenne: ', btree_same_structure(puu1, puu2));


  write('Matalin puu1 lehti on ');
  BTREE_PRINT_NODE(puu1, matalin_lehti(puu1));
  writeln;

  LIST_FREE(L);

  BTREE_FREE(puu1);
  BTREE_FREE(puu2);

end.