Copac N-ari
Această intrare sau secțiune despre programare nu citează sursele necesare sau cei prezenți sunt insuficienți . |
În informatică, un copac n-ari este un copac ale cărui noduri au, cel mult, gradul n ; prin arbore ne referim la un grafic nedirectat , conectat și aciclic. Este o structură de date utilizată pe scară largă în domeniul IT.
Conform caracterelor comune ale copacului, are un nod numit rădăcină (sau rădăcină ), care poate avea un număr de copii egal sau mai mic decât aritatea copacului. Nodurile fără copii se numesc frunze și toate celelalte sunt numite noduri interne. Cele n noduri copil ale aceluiași părinte se numesc frați .
O secvență de noduri și ramuri astfel încât fiecare nod (cu excepția ultimului) este părintele următorului se numește cale . Numărul de arce (sau ramuri ) implicate într-o cale se numește lungimea căii . În general, o cale cu noduri K are margini K-1 , adică are lungime K-1 . Lungimea celui mai lung traseu de la un nod la o frunză se numește înălțimea nodului ; toate frunzele au o înălțime de 0, iar părinții frunzelor, o înălțime de 1.
Dacă T este un copac și X este un nod al acestuia, setul de noduri ale lui T care conține X și toți descendenții săi se numește subarborele lui T. X este numit rădăcina subarborelui .
Implementarea copacilor n-ari
Prin utilizarea structurilor de programare generice, este posibil să se dea diferite implementări copacilor n-ari. Una dintre cele mai frecvente pentru această structură de date, care poate fi implementată utilizând unul dintre multele limbaje de programare , este prima implementare dinamică copil-frate , convenabilă, deoarece nu ține cont de numărul de copii pe care îi poate avea un nod.
În această implementare, fiecare nod are întotdeauna și doar două referințe:
- la primul copil (stânga)
- către primul frate (dreapta)
Mai jos, câteva exemple ale acestor implementări.
Prima implementare frate-copil
Iată codul sursă Java al unei implementări cu vizite de pre-comandă și post-comandă :
clasa NTreeNode < E > // implementare nod arbore cu tip E generic
{
NTreeNode protejat firstChild ; //primul fiu
frate protejat NTreeNode ; //frate
element E protejat ; // elementul nodului
public NTreeNode () // constructor
{
aceasta ( nul , nul , nul );
}
NTreeNode public ( element E , NTreeNode firstChild )
{
this ( element , firstChild , nul );
}
NTreeNode public ( element E , NTreeNode firstChild , NTreeNode frate )
{
aceasta . element = element ;
aceasta . firstSon = firstChild ;
aceasta . frate = frate ;
}
public String toString () {
element return ( String ) ;
}
}
public class NTree // public class tree
{
rădăcină NTreeNode protejată ; // rădăcina arborelui
dimensiunea int protejată ; // variabilă pentru dimensiunea arborelui
public NTree () // constructor
{
rădăcină = nul ;
dimensiune = 0 ;
}
insert boolean public ( părinte NTreeNode , NTreeNode [] copii ) // metodă pentru inserare
{
if ( this . search ( parent ) && children . length ! = 0 )
{
NTreeNode temp = aceasta . searchNode ( părinte );
temp . firstChild = children [ 0 ] ;
for ( int i = 1 ; i < children . length ; i ++ )
temp = temp . frate = copii [ i ] ;
întoarce-te adevărat ;
}
altceva
Sistem . afară . println ( "Eroare, nodul nu există. Nu se pot introduce noduri copil" );
// eroare de imprimare
returnează fals ;
}
căutare publică booleană ( nod NTreeNode ) // metodă de căutare a unui nod
{
NTreeNode p = aceasta . rădăcină;
if ( p ! = nul ) {
if ( p == nod ) returnează true ;
altceva
{
NTreeNode t = p . firstChild ;
while ( t ! = nul )
{
căutare ( t );
t = t . frate ;
}
}
}
returnează fals ;
}
publice TNodeList searchNode (TNodeList nod)
{
TNodeList p = aceasta . rădăcină;
if ( p ! = nul ) {
if ( p == nod ) returnează p ;
altceva
{
TNodeList t = p . copii . cap ;
while ( t ! = nul )
{
căutare ( t );
t = t . următor ;
}
}
}
returnare nulă ;
}
public void preorder () {
preordonare ( rădăcină );
}
precomandă de vid public ( NTreeNode p ) {
if ( p ! = nul ) {
Sistem . afară . println ( p . toString ());
NTreeNode t = p . firstChild ;
while ( t ! = nul ) {
precomandă ( t );
t = t . frate ;
}
}
}
public void postorder () {
postorder ( rădăcină );
}
public postorder nul ( NTreeNode p ) {
if ( p ! = nul ) {
NTreeNode t = p . firstChild ;
while ( t ! = nul ) {
postorder ( t );
t = t . frate ;
}
Sistem . afară . println ( p . toString ());
}
}
}
Implementarea listei legate
Mai jos, o altă implementare foarte populară a copacilor n-ari, de data aceasta folosind liste legate . Limbajul de programare ales pentru această implementare este Java.
clasa TNodeList < E >
{
element E public ;
public TNodeList următor ;
copii publici LinkedList ;
TNodeList public ( element E )
{
children = new LinkedList ();
aceasta . element = element ;
}
public String toString ()
{
returnează ( String ) acest lucru . element ;
}
}
clasă LinkedList
{
TNodeList cap , coadă ;
dimensiunea int ;
public LinkedList () {
cap = coadă = nul ;
dimensiune = 0 ;
}
public void addFirst ( nodul TNodeList )
{
if ( head == nul ) {
cap = coadă = nod ;
}
altceva
{
nod . next = cap ;
cap = nod ;
}
dimensiune ++ ;
}
public void addLast ( nodul TNodeList )
{
if ( tail == nul )
{
cap = coadă = nod ;
}
altceva
{
coada . next = nod ;
coada = nod ;
}
dimensiune ++ ;
}
}
clasă publică NTL
{
rădăcină publică TNodeList ;
dimensiunea publică int;
NTL public ( rădăcină TNodeList )
{
aceasta . rădăcină = rădăcină ;
dimensiune = 0 ;
}
insert boolean public ( TNodeList [] copii , părinte TNodeList )
{
if ( this . search ( parent ))
{
TNodeList tmp = aceasta . searchNode ( părinte );
if ( copii . lungime ! = 0 )
{
for ( int i = 0 ; i < children . length ; i ++ )
{
părinte . copii . addLast ( copii [ i ] );
}
întoarce-te adevărat ;
}
altceva
{
Sistem . afară . println ( „Fără copii de inserat” );
returnează fals ;
}
}
Sistem . afară . println ( "Nodul părinte nu există" );
returnează fals ;
}
căutare booleană publică ( nod TNodeList )
{
dacă ( dimensiune ! = 0 )
{
TNodeList p = aceasta . rădăcină;
if ( p ! = nul )
{
if ( p == nod ) returnează true ;
altceva
{
TNodeList t = p . copii . cap ;
while ( t ! = nul )
{
căutare ( t );
t = t . următor ;
}
}
}
}
returnează fals ;
}
publice TNodeList searchNode (TNodeList nod)
{
TNodeList p = aceasta . rădăcină;
if ( p ! = nul ) {
if ( p == nod ) returnează p ;
altceva
{
TNodeList t = p . copii . cap ;
while ( t ! = nul )
{
căutare ( t );
t = t . următor ;
}
}
}
returnare nulă ;
}
public void preorder () {
preordonare ( rădăcină );
}
precomandă de vid public ( TNodeList p ) {
if ( p ! = nul ) {
Sistem . afară . println ( p . toString ());
TNodeList t = p . copii . cap ;
while ( t ! = nul ) {
precomandă ( t );
t = t . următor ;
}
}
}
public void postorder () {
postorder ( rădăcină );
}
void postordine publice (TNodeList p) {
if ( p ! = nul ) {
TNodeList t = p . copii . cap ;
while ( t ! = nul ) {
postorder ( t );
t = t . următor ;
}
Sistem . afară . println ( p . toString ());
}
}
