type
  PBTNode = ^BTNode;
  BTNode  = record
    left  : PBTNode;
    right : PBTNode;
    level : Integer;
    data  : typ_danych;
  end;

struct BTNode
{
  BTNode * left;
  BTNode * right;
  int level;
  typ_danych data;
};

Type BTNode
  left As BTNode Ptr
  right As BTNode Ptr
  level As Integer
  data As typ_danych
End Type

// Badanie drzewa binarnego
// Data: 24.01.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program explore_BT;

// Typ węzłów drzewa

type
  PBTNode = ^BTNode;   // wskazanie węzła

  BTNode  = record     // rekord węzła
    left  : PBTNode;   // lewy syn
    right : PBTNode;   // prawy syn
    level : integer;   // numer poziomu
    data  : integer;   // dane węzła
  end;

// Zmienne globalne

var
  maxpath       : integer;    // długość najdłuższej ścieżki / wysokość drzewa
  minpath       : integer;    // długość najkrótszej ścieżki
  levelcount    : array of Integer; // tablica liczników
  leafcount     : integer;    // liczba liści
  onechildcount : integer;    // liczba węzłów z jedynakiem
  nodesum       : integer;    // suma danych węzłów

  n             : integer;    // liczba węzłów
  root          : PBTNode;    // wskazanie korzenia drzewa

// Procedura inicjuje dane, odczytuje definicję drzewa
// ze standardowego wejścia i tworzy jego strukturę w
// pamięci. Na wyjściu w zmiennej root zostaje umieszczony
// adres korzenia drzewa
//--------------------------------------------------------
procedure readBT;
var
  vp : array of PBTNode; // tablica wskaźników
  i, d, l, r : integer;
begin
  read (n);               // odczytujemy liczbę węzłów drzewa binarnego

  SetLength (vp, n);      // tworzymy tablicę dynamiczną wskaźników

  for i := 0 to n - 1 do
    new (vp [i]);       // tworzymy dynamicznie węzeł

  for i := 0 to n - 1 do
  begin
    read (d, l, r);       // odczytujemy trójkę liczb

    vp [i]^.level := 0; // zerujemy poziom węzła

    vp [i]^.data  := d; // wprowadzamy do węzła dane

    if l > 0 then vp [i]^.left  := vp [l] // ustawiamy lewego syna
    else          vp [i]^.left  := nil;     // jeśli istnieje

    if r > 0 then vp [i]^.right := vp [r] // ustawiamy prawego syna
    else          vp [i]^.right := nil;     // jeśli istnieje
  end;

  root := vp [0];    // zapamiętujemy korzeń drzewa

  SetLength (vp, 0);    // usuwamy tablicę wskaźników

  maxpath := 0;        // ustawiamy zmienne globalne
  minpath := MAXINT;
  SetLength (levelcount, n);
  for i := 0 to n - 1 do levelcount [i] := 0;
  leafcount := 0;
  onechildcount := 0;
  nodesum := 0;
end;

// Procedura przechodzi drzewo algorytmem DFS:preorder
// i odpowiednio przetwarza węzły zapisując wyniki
// w zmiennych globalnych
//----------------------------------------------------
procedure DFS (v : PBTNode);
var
  children : integer;
begin
  if v <> nil then
  begin

    // przetwarzamy bieżący węzeł

    children := 0; // liczba dzieci, 0, 1 lub 2

    if v^.left <> nil then
    begin
      inc (children);
      v^.left^.level := v^.level + 1;
    end;

    if v^.right <> nil then
    begin
      inc (children);
      v^.right^.level := v^.level + 1;
    end;

    // test na najdłuższą ścieżkę

    if v^.level > maxpath then maxpath := v^.level;

    // test na najkrótszą ścieżkę do liścia i zliczanie liści

    if children = 0 then
    begin
      if v^.level < minpath then minpath := v^.level;
      inc (leafcount);
    end;

    // zliczanie węzłów na bieżącym poziomie poziomie

    inc (levelcount [v^.level]);

    // zliczanie węzłów z jednym synem

    if children = 1 then inc (onechildcount);

    // sumowanie zawartości węzłów

    inc (nodesum, v^.data);

    DFS (v^.left);  // przechodzimy lewe poddrzewo
    DFS (v^.right); // przechodzimy prawe poddrzewo
  end;
end;

// Procedura wyświetla wyniki końcowe
//-----------------------------------
procedure writeBT;
var
  i : integer;
begin
  writeln;
  writeln('maxpath       = ', maxpath);
  writeln('minpath       = ', minpath);
  writeln;
  for i := 0 to maxpath do
    writeln('level ', i, ' : number of nodes = ', levelcount [i]);
  writeln;
  writeln('leafcount     = ', leafcount);
  writeln('onechildcount = ', onechildcount);
  writeln('nodesum       = ', nodesum);
  writeln;
end;

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
procedure DFSRelease (v : PBTNode);
begin
  if v <> nil then
  begin
    DFSRelease (v^.left);   // usuwamy lewe poddrzewo
    DFSRelease (v^.right);  // usuwamy prawe poddrzewo
    dispose (v);            // usuwamy sam węzeł
  end;
end;

// Procedura sprząta pamięć
//-------------------------
procedure deleteBT;
begin
  SetLength (levelcount, 0);
  DFSRelease (root);   // wykorzystujemy DFS:postorder do usunięcia drzewa
end;

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************

begin
  readBT;      // odczytaj i utwórz drzewo
  DFS (root);   // przetwórz drzewo
  writeBT;     // wypisz wyniki
  deleteBT;    // posprzątaj pamięć
end.

// Badanie drzewa binarnego
// Data: 24.01.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

// Typ węzłów drzewa

struct BTNode
{
  BTNode * left;
  BTNode * right;
  int level;
  int data;
};

// Zmienne globalne

int maxpath = 0;           // długość najdłuższej ścieżki / wysokość drzewa
int minpath = 2147483647;  // długość najkrótszej ścieżki
int * levelcount;          // tablica liczników
int leafcount = 0;         // liczba liści
int onechildcount = 0;     // liczba węzłów z jedynakiem
int nodesum = 0;           // suma danych węzłów

int n;                     // liczba węzłów
BTNode * root;             // wskazanie korzenia drzewa

// Procedura inicjuje dane, odczytuje definicję drzewa
// ze standardowego wejścia i tworzy jego strukturę w
// pamięci. Na wyjściu w zmiennej root zostaje umieszczony
// adres korzenia drzewa
//--------------------------------------------------------
void readBT()
{
  BTNode ** vp;              // tablica wskaźników
  int i, d, l, r;

  cin >> n;                  // odczytujemy liczbę węzłów drzewa binarnego

  vp = new BTNode * [n];   // tworzymy tablicę dynamiczną wskaźników

  for(i = 0; i < n; i++)
    vp [i] = new BTNode;   // tworzymy dynamicznie węzeł

  for(i = 0; i < n; i++)
  {
    cin >> d >> l >> r;      // odczytujemy trójkę liczb

    vp [i] ->level = 0;    // zerujemy poziom węzła

    vp [i] ->data = d;     // wprowadzamy do węzła dane

    vp [i] ->left  = l ? vp [l] : NULL;  // ustawiamy lewego syna, jeśli istnieje

    vp [i] ->right = r ? vp [r] : NULL;  // ustawiamy prawego syna, jeśli istnieje
  }

  root = vp [0];           // zapamiętujemy korzeń drzewa

  delete [] vp;             // usuwamy tablicę wskaźników

  // tworzymy tablicę liczników elementów na poziomach

  levelcount = new int [n];
  for(i = 0; i < n; i++) levelcount [i] = 0;
}

// Procedura przechodzi drzewo algorytmem DFS:preorder
// i odpowiednio przetwarza węzły zapisując wyniki
// w zmiennych globalnych
//----------------------------------------------------
void DFS (BTNode * v)
{
  if(v)
  {
     // przetwarzamy bieżący węzeł

    int children = 0; // liczba dzieci, 0, 1 lub 2

    if(v->left)
    {
      children++;
      v->left->level = v->level + 1;
    }

    if(v->right)
    {
      children++;
      v->right->level = v->level + 1;
    }

    // test na najdłuższą ścieżkę

    if(v->level > maxpath) maxpath = v->level;

    // test na najkrótszą ścieżkę do liścia i zliczanie liści

    if(!children)
    {
      if(v->level < minpath) minpath = v->level;
      leafcount++;
    }

    // zliczanie węzłów na bieżącym poziomie poziomie

    levelcount [v->level] ++;

    // zliczanie węzłów z jednym synem

    if(children == 1) onechildcount++;

    // sumowanie zawartości węzłów

    nodesum += v->data;

    DFS (v->left);  // przechodzimy lewe poddrzewo
    DFS (v->right); // przechodzimy prawe poddrzewo
  }
}

// Procedura wyświetla wyniki końcowe
//-----------------------------------
void writeBT()
{
  cout << endl
       << "maxpath       = " << maxpath << endl
       << "minpath       = " << minpath << endl
       << endl;
  for(int i = 0; i <= maxpath; i++)
    cout << "level " << i << ": number of nodes = " << levelcount [i] << endl;
  cout << endl
       << "leafcount     = " << leafcount << endl
       << "onechildcount = " << onechildcount << endl
       << "nodesum       = " << nodesum << endl
       << endl;
}

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
void DFSRelease (BTNode * v)
{
  if(v)
  {
    DFSRelease (v->left);   // usuwamy lewe poddrzewo
    DFSRelease (v->right);  // usuwamy prawe poddrzewo
    delete v;              // usuwamy sam węzeł
  }
}

// Procedura sprząta pamięć
//-------------------------
void deleteBT()
{
  delete [] levelcount;
  DFSRelease (root);   // wykorzystujemy DFS:postorder do usunięcia drzewa
}

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************

int main()
{
  readBT();    // odczytaj i utwórz drzewo
  DFS (root);   // przetwórz drzewo
  writeBT();   // wypisz wyniki
  deleteBT();  // posprzątaj pamięć

  return 0;
}

' Badanie drzewa binarnego
' Data: 24.01.2013
' (C)2013 mgr Jerzy Wałaszek
'------------------------------

' Typ węzłów drzewa

Type BTNode
  left As BTNode Ptr
  right As BTNode Ptr
  level As Integer
  data As Integer
End Type

' Zmienne globalne

Dim Shared As Integer maxpath = 0          ' długość najdłuższej ścieżki / wysokość drzewa
Dim Shared As Integer minpath = 2147483647 ' długość najkrótszej ścieżki
Dim Shared As Integer Ptr levelcount       ' tablica liczników
Dim Shared As Integer leafcount = 0        ' liczba liści
Dim Shared As Integer onechildcount = 0    ' liczba węzłów z jedynakiem
Dim Shared As Integer nodesum = 0          ' suma danych węzłów

Dim Shared As Integer n                    ' liczba węzłów
Dim Shared As BTNode Ptr root           ' wskazanie korzenia drzewa

' Procedura inicjuje dane, odczytuje definicję drzewa
' ze standardowego wejścia i tworzy jego strukturę w
' pamięci. Na wyjściu w zmiennej root zostaje umieszczony
' adres korzenia drzewa
'--------------------------------------------------------
Sub readBT()
  Dim As BTNode Ptr Ptr vp     ' tablica wskaźników
  Dim As Integer i, d, l, r

  Open Cons For Input As #1
 
  Input #1, n                 ' odczytujemy liczbę węzłów drzewa binarnego

  vp = new BTNode Ptr [n]   ' tworzymy tablicę dynamiczną wskaźników

  For i = 0 To n-1
    vp [i] = new BTNode     ' tworzymy dynamicznie węzeł
  Next

  For i = 0 To n-1
    Input #1, d, l, r         ' odczytujemy trójkę liczb

    vp [i] ->level = 0      ' zerujemy poziom węzła

    vp [i] ->data = d       ' wprowadzamy do węzła dane

    ' ustawiamy lewego syna, jeśli istnieje
   
    If l > 0 Then
    	vp [i] ->left = vp [l]
    Else
    	vp [i] ->Left = 0
    End If

    ' ustawiamy prawego syna, jeśli istnieje
   
    If r > 0 Then
    	vp [i] ->right = vp [r]
    Else
    	vp [i] ->Right = 0
    End If
  Next
 
  Close #1

  root = vp [0]         ' zapamiętujemy korzeń drzewa

  delete [] vp           ' usuwamy tablicę wskaźników

  ' tworzymy tablicę liczników elementów na poziomach

  levelcount = new Integer [n]
  For i = 0 To n-1
  	levelcount [i] = 0
  Next
End Sub

' Procedura przechodzi drzewo algorytmem DFS:preorder
' i odpowiednio przetwarza węzły zapisując wyniki
' w zmiennych globalnych
'----------------------------------------------------
Sub DFS (v As BTNode Ptr)

  Dim As Integer children = 0
  
  If v Then
    ' przetwarzamy bieżący węzeł

    If v->Left Then
      children += 1
      v->left->level = v->level + 1
    End If

    If v->Right Then
      children += 1
      v->right->level = v->level + 1
    End If

    ' test na najdłuższą ścieżkę

    If v->level > maxpath Then maxpath = v->level

    ' test na najkrótszą ścieżkę do liścia i zliczanie liści

    If children = 0 Then
      If v->level < minpath Then minpath = v->level
      leafcount += 1
    End If

    ' zliczanie węzłów na bieżącym poziomie poziomie

    levelcount [v->level] += 1

    ' zliczanie węzłów z jednym synem

    If children = 1 then onechildcount += 1

    ' sumowanie zawartości węzłów

    nodesum += v->Data

    DFS (v->left)  ' przechodzimy lewe poddrzewo
    DFS (v->right) ' przechodzimy prawe poddrzewo
  End If
End Sub

' Procedura wyświetla wyniki końcowe
'-----------------------------------
Sub writeBT()
  Dim As Integer i
  Print
  Print "maxpath       = ";maxpath
  Print "minpath       = ";minpath
  Print
  For i = 0 To maxpath
    Print "level ";i;": number of nodes = ";levelcount [i]
  Next
  Print
  Print "leafcount     = ";leafcount
  Print "onechildcount = ";onechildcount
  Print "nodesum       = ";nodesum
  Print
End Sub

' Procedura DFS:postorder usuwająca drzewo
'-----------------------------------------
sub DFSRelease (v As BTNode Ptr)
  If v Then
    DFSRelease (v->left)   ' usuwamy lewe poddrzewo
    DFSRelease (v->right)  ' usuwamy prawe poddrzewo
    delete v              ' usuwamy sam węzeł
  End If
End Sub

' Procedura sprząta pamięć
'-------------------------
Sub deleteBT()
  delete [] levelcount
  DFSRelease (root)        ' wykorzystujemy DFS:postorder do usunięcia drzewa
End Sub

'**********************
'*** PROGRAM GŁÓWNY ***
'**********************

readBT()    ' odczytaj i utwórz drzewo
DFS (root)   ' przetwórz drzewo
writeBT()   ' wypisz wyniki
deleteBT()  ' posprzątaj pamięć

End