L'entier 
est appelé la profondeur du sommet 
dans
l'arborescence. On montre facilement que dans une arborescence la
racine 
n'admet pas de prédécesseur et que tout sommet 
différent de admet un prédécesseur et un seul, ceci
implique:
La différence entre une arborescence et un arbre (voir
chapitre 4) est mineure. Dans un arbre, les fils d'un sommet sont
ordonnés (on distingue le fils gauche du fils droit), tel n'est pas
le cas dans une arborescence. On se sert depuis fort longtemps des
arborescences pour représenter des arbres généalogiques aussi le
vocabulaire utilisé pour les arborescences emprunte beaucoup de
termes relevant des relations familiales.
L'unique prédécesseur d'un sommet (différent de ) est
appelé son père, l'ensemble 
,
où 
, formant le chemin de à 
est appelé
ensemble des ancêtres de , les successeurs de sont
aussi appelés ses fils. L'ensemble des sommets extrémités
d'un chemin d'origine est l'ensemble des descendants de
; il constitue une arborescence de racine , celle-ci est l'union
de 
et des arborescences formées des descendants des fils de
. Pour des raisons de commodité d'écriture qui
apparaîtront dans la suite, nous adoptons la convention que tout
sommet est à la fois ancêtre et descendant de lui-même.
Une arborescence est avantageusement représentée par le vecteur
pere qui à chaque sommet différent de la racine associe son
père. Il est souvent commode dans la programmation des algorithmes
sur les arborescences de considérer que la racine de l'arborescence
est elle-même son père, c'est la convention que nous adopterons
dans la suite.
Figure: Une arborescence et son vecteur 
La transformation des listes de successeurs décrivant une arborescence en le vecteur pere s'exprime très simplement en Pascal on obtient:
type
Arbo = array[IntSom] of Sommet;
procedure SuccEnPere (succ: GrapheSuc; n: integer; r: Sommet;
var pere: Arbo);
var
k: integer;
i, j: Sommet;
begin
pere[r] := r;
for i := 1 to n do
begin
k := 1;
j := succ[i, k];
while (j <> Omega) do
begin
pere[j] := i;
k := k + 1;
j := succ[i, k];
end;
end;
end;
Dans la suite, on suppose que l'ensemble des sommets 
est l'ensemble
des entiers compris entre 
et 
, une arborescence est dite préfixe si, pour tout sommet 
, l'ensemble des descendants de
est un intervalle de l'ensemble des entiers dont le plus petit
élément est .
Figure: Une arborescence préfixe
Figure: Emboitement des descendants dans une arborescence préfixe
Dans une arborescence préfixe, les intervalles de descendants
s'emboîtent les uns dans les autres comme des systèmes de
parenthèses; ainsi, si n'est pas un descendant de , ni un
descendant de , les descendants de et de forment des
intervalles disjoints. En revanche, si est un ancêtre de ,
l'intervalle des descendants de est inclus dans celui des
descendants de .
Preuve Pour trouver cette numérotation on applique l'algorithme récursif suivant:
.
de la racine est numéroté 
.
est numérotée par
appels récursifs de l'algorithme on obtient ainsi des sommets
numérotés de à 
.
; les
descendants de ce fils sont numérotés récursivement de
à 
.
La preuve de ce que la numérotation obtenue est préfixe se fait
par récurrence sur le nombre de sommets de l'arborescence et utilise le
caractère récursif de l'algorithme. 
L'algorithme qui est décrit dans la preuve ci-dessus peut s'écrire simplement en Pascal, on suppose que l'arborescence est représentée par une matrice Succ de successeurs la re-numérotation se fait par un vecteur numero et r est la racine de l'arborescence.
var
numero: SomVect;
succ: GrapheSuc;
procedure Numprefixe (x: Sommet; var num: integer);
var
i: integer;
y: IntSom;
begin
numero[x] := num;
num := num + 1;
i := 1;
y := succ[x, i];
while (y <> Omega) do
begin
Numprefixe(y, num);
i := i + 1;
y := succ[x, i];
end;
end;
num := 1;
Numprefixe(r,num);