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; // liczniki
  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 read_bt;
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
    readln(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 synów, 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
    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 write_bt;
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 dfs_release (v : PBTnode);
begin
  if v <> nil then
  begin
    dfs_release(v^.left); // usuwamy lewe
                           // poddrzewo
    dfs_release(v^.right); // usuwamy prawe
                           // poddrzewo
    dispose(v); // usuwamy sam węzeł
  end;
end;

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

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

begin
  read_bt; // odczytaj i utwórz drzewo
  dfs(root); // przetwórz drzewo
  write_bt; // wypisz wyniki
  delete_bt; // 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
// długość najkrótszej ścieżki
int minpath = 2147483647;
// tablica liczników
int * levelcount;
// liczba liści
int leafcount = 0;
// liczba węzłów z jedynakiem
int onechildcount = 0;
// suma danych w węzłach
int nodesum = 0;
// liczba węzłów
int n;
// wskazanie korzenia drzewa
BTnode * root;

// 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 read_bt(void)
{
  BTnode ** vp; // tablica wskaźników
  int i, d, l, r;

  // odczytujemy liczbę węzłów
  // drzewa binarnego
  cin >> n;
  // tworzymy tablicę dynamiczną wskaźników
  vp = new BTnode * [n];

  for(i = 0; i < n; i++)
    // tworzymy dynamicznie węzeł
    vp[i] = new BTnode;
  for(i = 0; i < n; i++)
  {
    // odczytujemy trójkę liczb
    cin >> d >> l >> r;
    // zerujemy poziom węzła
    vp[i]->level = 0;
    // wprowadzamy do węzła dane
    vp[i]->data = d;

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

    // ustawiamy prawego syna, 
    // jeśli istnieje
    vp[i]->right = r ? vp[r] : NULL; 
  }
  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ł
    //---------------------------

    // liczba synów, 0, 1 lub 2
    int children = 0; 
    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
    levelcount [v->level] ++;

    // zliczanie węzłów z jednym synem 
    if(children == 1) onechildcount++;

    // sumowanie zawartości węzłów
    nodesum += v->data;

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

// Procedura wyświetla wyniki końcowe
//-----------------------------------
void write_bt()
{
  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 dfs_release(BTnode * v)
{
  if(v)
  {
    // usuwamy lewe poddrzewo
    dfs_release(v->left);
    // usuwamy prawe poddrzewo
    dfs_release(v->right);
    delete v; // usuwamy sam węzeł
  }
}

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

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

int main()
{
  read_bt(); // odczytaj i utwórz drzewo
  dfs(root); // przetwórz drzewo
  write_bt(); // wypisz wyniki
  delete_bt(); // 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
'-----------------

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

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

' 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 read_bt()
  
  ' tablica wskaźników
  Dim As BTnode Ptr Ptr vp
  
  Dim As Integer i, d, l, r

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

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

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

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

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

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

    ' 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

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

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

  ' 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
    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

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

' Procedura wyświetla wyniki końcowe
'-----------------------------------
Sub write_bt()
  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 dfs_release(v As BTnode Ptr)
  If v Then
    ' usuwamy lewe poddrzewo
    dfs_release (v->left)
    
    ' usuwamy prawe poddrzewo
    dfs_release (v->right)
    
    ' usuwamy sam węzeł
    delete v
  End If
End Sub

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

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

read_bt()   ' odczytaj i utwórz drzewo
dfs(root)  ' przetwórz drzewo
write_bt()  ' wypisz wyniki
delete_bt() ' posprzątaj pamięć
End