Algorytmy i Struktury Danych - Prezentacja drzew binarnych

W rozdziale zaprojektujemy prosty sposób prezentacji drzew binarnych. Przedstawiamy go na poniższym rysunku

→

    ┌─L
  ┌─G
┌─C
│ │ ┌─K
│ └─F
A ┌─E
│ │ └─J
└─B
  │ ┌─I
  └─D
    └─H

Znaki pomocnicze
Kod ASCII	Znak
179 192 195 196 218	│ └ ├ ─ ┌

Każdy węzeł drzewa znajduje się w osobnym wierszu okna konsoli. Jeśli przyjrzymy się ich kolejności, to zauważymy, że są one w porządku odwrotnym do przejścia in-order. Taką kolejność przejścia węzłów uzyskamy przez odwrócenie w algorytmie in-order kolejności odwiedzania poddrzew:

zwykłe in-order

K01: Jeśli v = nil, to zakończ
K02: inorder(v→left)
K03: Odwiedź węzeł wskazany przez v
K04: inorder(v→right)
K05: Zakończ

odwrotne in-order

K01: Jeśli v = nil, to zakończ
K02: inorder(v→right)
K03: Odwiedź węzeł wskazany przez v
K04: inorder(v→left)
K05: Zakończ

Położenie węzła w wierszu zależy od jego poziomu. Korzeń znajduje się w kolumnie 0. Węzły pierwszego poziomu znajdują się w kolumnie 2, węzły drugiego poziomu w kolumnie 4, następne w kolumnie 6, itd.

Od kolumny węzła do kolumny poprzedzającej syna jest zawsze wypisywany tekst:

┌─ dla prawego syna

└─ dla lewego syna

Dodatkowo musimy umieszczać znaki "│" ponad i poniżej węzła, jeśli posiada on synów. Problem ten rozwiążemy łatwo zapamiętując w osobnej zmiennej sp tekst, który należy wyświetlić w wierszach pośrednich. Poniżej przedstawiamy odpowiedni algorytm wraz z opisem poszczególnych operacji.

Algorytm drukowania drzewa binarnego w oknie konsoli print_bt

Wejście:

sp : tekst do wyświetlenia w wierszu pośrednim.
sn : tekst do wyświetlenia przed węzłem.
v : wskazanie bieżącego węzła drzewa.

Wyjście:

Wydruk drzewa

Elementy pomocnicze:

s : tekst do wyświetlenia w wierszach pośrednich dla synów.

Lista kroków:

K01: Jeśli v = nil, ; otrzymaliśmy puste wskazanie, 
     to zakończ ; nic nie robimy
K02: s ← sp ; w s umieszczamy tekst
     ; dla wierszy pośrednich
K03: Jeśli sn = "┌─", ; dla prawego syna usuwamy
     to s[|s|-2] ← " " ; z sn ostatni znak |
K04: print_bt(s+"│ ", "┌─", v→right) ; wywołujemy algorytm
     ; rekurencyjnie dla prawego syna 
K05: s ← sp[0:|s|-2] ; w s umieszczamy sn bez ostatnich
     ; dwóch znaków, które zastąpi tekst przed węzłem
K06: Pisz s, sn, v→data ; wypisujemy wiersz węzła
K07: s ← sp ; powtarzamy operacje dla lewego syna 
K08: Jeśli sn = "└─", ; dla lewego syna usuwamy
     to s[|s|-2] ← " " ; z sn ostatni znak |
K09: print_bt(s+"│ ", "└─", v→left) ; wywołujemy algorytm
     ; rekurencyjnie dla lewego syna 
K10: Zakończ

Pierwsze wywołanie algorytmu powinno być z pustymi tekstami sp i sn oraz z v wskazującym korzeń drzewa.

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje ze standardowego wejścia definicję drzewa. Definicja składa się z liczby n określającej ilość węzłów oraz n trójek, które dla kolejnych węzłów oznaczają odpowiednio: zawartość węzła, numery lewego i prawego syna. Brak syna oznaczany jest liczbą 0. Na podstawie tej definicji program tworzy odpowiednie drzewo binarne, wyświetla je, a na koniec usuwa z pamięci.

Przykładowe dane
(przekopiuj do schowka i wklej do okna konsoli):

Pascal

// Prezentacja drzewa binarnego
// Data: 03.02.2013
// (C)2013 mgr Jerzy Wałaszek
//-----------------------------

// 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 
    Data: integer; // dane węzła
  end;

// Zmienne globalne

var
  // liczba węzłów
  n : integer;
  // wskazanie korzenia drzewa
  root : PBTnode;
  // łańcuchy do znaków ramek
  cr, cl, cp : string;

// 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
  // tablica wskaźników
  vp : array of PBTnode;
  i, d, l, r : integer;
begin
  // odczytujemy liczbę węzłów
  // drzewa binarnego
  readln(n);
  // tworzymy tablicę dynamiczną
  // wskaźników
  SetLength(vp, n);

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

  for i := 0 to n-1 do
  begin
    // odczytujemy dane węzła
    // i numery synów
    readln(d, l, r);
    // wprowadzamy do węzła dane
    vp [i]^.Data:= d;

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

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

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

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

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

// Procedura wypisuje drzewo
//--------------------------
procedure print_bt(sp, sn : string;
                  v : PBTnode);
var
  s : string;
  i : integer;
begin
  if v <> nil then
  begin
    s := sp;
    if sn = cr then
      s[length(s)-1] := ' ';
    print_bt(s+cp, cr, v^.right);

    s := Copy(sp, 1, length(sp)-2);
    for i := 1 to length(s) do
      write(char(ord(s[i])));
    for i := 1 to length(sn) do
      write(char(ord(sn[i])));
    writeln(v^.data);

    s := sp;
    if sn = cl then
      s[length(s)-1] := ' ';
    print_bt(s+cp, cl, v^.left);
  end;
end;

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

begin

  // ustawiamy łańcuchy znakowe, 
  // ponieważ nie wszystkie edytory
  // pozwalają wstawiać znaki konsoli
  // do tworzenia ramek.
  // cr = /--
  //      |

  // cl = |
  //      \--

  // cp = |
  //      |

  cr := '  ';
  cl := '  ';
  cp := '  ';
  cr[1] := char(218);
  cr[2] := char(196);
  cl[1] := char(192);
  cl[2] := char(196);
  cp[1] := char(179);

  // odczytujemy drzewo
  read_bt;
  // wyświetlamy drzewo
  print_bt ('', '', root);
  // usuwamy drzewo z pamięci
  dfs_release (root);
end.

C++

// Prezentacja drzewa binarnego
// Data: 03.02.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <string>

using namespace std;

// Typ węzłów drzewa
struct BTnode
{
  BTnode * left; // lewy syn 
  BTnode * right; // prawy syn 
  int data; // dane węzła
};

// Zmienne globalne

// liczba węzłów
int n;
// wskazanie korzenia drzewa
BTnode * root;
// łańcuchy do ramek
string cr, cl, cp;

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

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

  // tworzymy tablicę dynamiczną
  // wskaźników węzłó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 dane węzła
    // i numery synów
    cin >> d >> l >> r;

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

    // ustawiamy lewego syna, 
    // jeśli istnieje
    if(l)
      vp[i]->left = vp[l];
    else
      vp[i]->left = NULL;

    // ustawiamy prawego syna, 
    // jeśli istnieje
    if(r)
      vp[i]->right = vp[r];
    else
      vp[i]->right = NULL;
  }

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

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

// 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);
    // usuwamy sam węzeł
    delete v;
  }
}

// Procedura wypisuje drzewo
//--------------------------
void print_bt (string sp, 
              string sn, 
              BTnode * v)
{
  string s;

  if(v)
  {
    s = sp;
    if(sn == cr)
      s[s.length()-2] = ' ';
    print_bt(s+cp, cr, v->right);

    s = s.substr(0, sp.length()-2);
    cout << s << sn << v->data
         << endl;

    s = sp;
    if(sn == cl)
      s[s.length()-2] = ' ';
    print_bt(s+cp, cl, v->left);
  }
}

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

int main()
{
  // ustawiamy łańcuchy znakowe, 
  // ponieważ nie wszystkie edytory
  // pozwalają wstawiać znaki konsoli
  // do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr = cl = cp = "  ";
  cr[0] = 218; cr[1] = 196;
  cl[0] = 192; cl[1] = 196;
  cp[0] = 179;

  // odczytujemy drzewo
  read_bt();
  // wyświetlamy drzewo
  print_bt("", "", root);
  // usuwamy drzewo z pamięci
  dfs_release(root);
  return 0;
}

Basic

' Prezentacja drzewa binarnego
' Data: 03.02.2013
' (C)2013 mgr Jerzy Wałaszek
'------------------------------

' Typ węzłów drzewa

Type BTnode
  left As BTnode Ptr
  right As BTnode Ptr
  data As Integer
End Type

' Zmienne globalne

' liczba węzłów
Dim Shared As Integer n 
' wskazanie korzenia drzewa
Dim Shared As BTnode Ptr root
' łańcuchy do ramek
Dim Shared As String * 2 cr, cl, cp

' 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 węzłó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
    ' 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
 
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 wypisuje drzewo
'--------------------------
Sub print_bt (sp As String, _
             sn As String, _
             v As BTnode Ptr)
  Dim As String s

  If v Then
    s = sp
    If sn = cr Then _
      Mid(s, Len(s)-1, 1) = " "
    print_bt(s+cp, cr, v->right)

    s = Mid(s, 1, Len(sp)-2)
    Print Using "&&&";s;sn;v->Data

    s = sp
    If sn = cl Then _
      Mid(s, Len(s)-1, 1) = " "
    print_bt(s+cp, cl, v->Left)
  End If
End Sub

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

' ustawiamy łańcuchy znakowe, 
' ponieważ nie wszystkie edytory
' pozwalają wstawiać znaki konsoli
' do tworzenia ramek.
' cr = +--
'      |

' cl = |
'      +--

' cp = |
'      |

cr = Chr(218)+Chr (196)
cl = Chr(192)+Chr (196)
cp = Chr(179)+" "

' odczytujemy drzewo
read_bt()
' wyświetlamy drzewo
print_bt("", "", root)
' usuwamy drzewo z pamięci
dfs_release(root)
End

Python (dodatek)

# Prezentacja drzewa binarnego
# Data: 08.07.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------


# klasa węzłów drzewa
class BTnode:


    def __init__(self):
        self.left  = None
        self.right = None
        self.data  = 0


# zmienne globalne
#-----------------

# liczba węzłów
n = 0
# wskazanie korzenia drzewa
root = None
# łańcuchy do ramek
cr = "┌─"
cl = "└─"
cp = "│ "


# 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
#-----------------------------------
def read_bt():
    global n, root

    # odczytujemy liczbę węzłów drzewa
    n = int(input())
    # tworzymy tablicę dynamiczną wskaźników
    vp = []
    for i in range(n):
        vp.append(BTnode())
    for i in range(n):
        # odczytujemy trójkę liczb
        x = input().split()
        d = int(x[0])
        l = int(x[1])
        r = int(x[2])
        # tworzymy odwołania
        if l:
            l = vp[l]
        else:
            l = None
        if r:
            r = vp[r]
        else:
            r = None
        # tworzymy węzeł
        vp[i].left  = l
        vp[i].right = r
        vp[i].data  = d
    # zapamiętujemy korzeń drzewa
    root = vp[0]


# procedura DFS:postorder usuwająca drzewo
#-----------------------------------------
def dfs_release(v):
    if v:
        # usuwamy lewe poddrzewo
        dfs_release(v.left)
        # usuwamy prawe poddrzewo
        dfs_release(v.right)
        # usuwamy odwołania
        v.left = None
        v.right = None


# procedura wypisuje drzewo
#--------------------------
def print_bt(sp, sn, v):
    global cr, cl, cp
    s = ""
    if v:
        s = sp
        if sn == cr:
            s = s[:-2]+' '+s[-1]
        print_bt(s+cp, cr, v.right)
        s = s[:-2]
        print(s, sn, v.data, sep="")
        s = sp
        if sn == cl:
            s = s[:-2]+' '+s[-1]
        print_bt(s+cp, cl, v.left)


#**********************
#*** PROGRAM GŁÓWNY ***
#**********************

# odczytujemy drzewo
read_bt()
# wyświetlamy drzewo
print_bt("", "", root)
# usuwamy drzewo z pamięci
dfs_release(root)

Wynik:
12 5 1 2 2 3 4 7 5 6 3 7 8 8 9 0 9 0 10 1 0 11 6 0 0 5 0 0 3 0 0 0 0 0 2 0 0 ┌─2 ┌─1 ┌─7 │ │ ┌─0 │ └─9 5 │ ┌─8 │ │ └─3 └─2 │ ┌─5 └─3 └─6

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Prezentacja drzew binarnych