L'arbre binari significa que el node pot tenir com a màxim dos fills. Aquí, el propi nom binari suggereix que 'dos'; per tant, cada node pot tenir 0, 1 o 2 fills.

Entenem l'arbre binari a través d'un exemple.

L'arbre anterior és un arbre binari perquè cada node conté el màxim de dos fills. La representació lògica de l'arbre anterior es dóna a continuació:

A l'arbre anterior, el node 1 conté dos punters, és a dir, un punter esquerre i un punter dret que apunten al node esquerre i dret respectivament. El node 2 conté els dos nodes (node ​​esquerre i dret); per tant, té dos punters (esquerra i dreta). Els nodes 3, 5 i 6 són els nodes fulla, de manera que tots aquests nodes contenen NUL punter a les parts esquerra i dreta.

Propietats de l'arbre binari

• A cada nivell de i, el nombre màxim de nodes és 2ⁱ.
• L'alçada de l'arbre es defineix com el camí més llarg des del node arrel fins al node fulla. L'arbre que es mostra a dalt té una alçada igual a 3. Per tant, el nombre màxim de nodes a l'alçada 3 és igual a (1+2+4+8) = 15. En general, el nombre màxim de nodes possible a l'alçada h és (2⁰+ 2¹+ 2²+….2^h) = 2^h+1-1.
• El nombre mínim de nodes possible a l'alçada h és igual a h+1 .
• Si el nombre de nodes és mínim, llavors l'alçada de l'arbre seria màxima. Per contra, si el nombre de nodes és màxim, llavors l'alçada de l'arbre seria mínima.

Si hi ha 'n' nombre de nodes a l'arbre binari.

L'alçada mínima es pot calcular com:

Com ho sabem,

n = 2^h+1-1

n+1 = 2^h+1

Prenent registre pels dos costats,

registre₂(n+1) = log2(2^h+1)

registre₂(n+1) = h+1

h = log₂(n+1) - 1

La cadena de Java està buida

L'alçada màxima es pot calcular com:

Com ho sabem,

n = h+1

h= n-1

Tipus d'arbre binari

Hi ha quatre tipus d'arbre binari:

Arbre binari complet/propiat/estricte Arbre binari complet Arbre binari perfecte Arbre binari degenerat Arbre binari equilibrat

1. Arbre binari complet/propiat/estricte

instal·lar maven

L'arbre binari complet també es coneix com a arbre binari estricte. L'arbre només es pot considerar com l'arbre binari complet si cada node ha de contenir 0 o 2 fills. L'arbre binari complet també es pot definir com l'arbre en el qual cada node ha de contenir 2 fills excepte els nodes fulla.

Vegem l'exemple senzill de l'arbre binari complet.

A l'arbre anterior, podem observar que cada node conté zero o dos fills; per tant, és un arbre binari complet.

Propietats de l'arbre binari complet

• El nombre de nodes de fulla és igual al nombre de nodes interns més 1. A l'exemple anterior, el nombre de nodes interns és 5; per tant, el nombre de nodes de fulla és igual a 6.
• El nombre màxim de nodes és el mateix que el nombre de nodes de l'arbre binari, és a dir, 2^h+1-1.
• El nombre mínim de nodes a l'arbre binari complet és 2*h-1.
• L'alçada mínima de l'arbre binari complet és registre₂(n+1) - 1.
• L'alçada màxima de l'arbre binari complet es pot calcular com:

n= 2*h - 1

n+1 = 2*h

h = n+1/2

Arbre binari complet

L'arbre binari complet és un arbre en què tots els nodes s'omplen completament excepte l'últim nivell. A l'últim nivell, tots els nodes han d'estar el més a l'esquerra possible. En un arbre binari complet, els nodes s'han d'afegir des de l'esquerra.

Creem un arbre binari complet.

L'arbre anterior és un arbre binari complet perquè tots els nodes estan completament omplerts i tots els nodes de l'últim nivell s'afegeixen primer a l'esquerra.

Propietats de l'arbre binari complet

• El nombre màxim de nodes a l'arbre binari complet és 2^h+1- 1.
• El nombre mínim de nodes en un arbre binari complet és 2^h.
• L'alçada mínima d'un arbre binari complet és registre₂(n+1) - 1.
• L'alçada màxima d'un arbre binari complet és

Arbre binari perfecte

Un arbre és un arbre binari perfecte si tots els nodes interns tenen 2 fills i tots els nodes fulla estan al mateix nivell.

Vegem un exemple senzill d'arbre binari perfecte.

L'arbre de sota no és un arbre binari perfecte perquè tots els nodes de fulla no estan al mateix nivell.

Nota: Tots els arbres binaris perfectes són els arbres binaris complets així com l'arbre binari complet, però a l'inrevés no és cert, és a dir, tots els arbres binaris complets i els arbres binaris complets són els arbres binaris perfectes.

Arbre binari degenerat

L'arbre binari degenerat és un arbre en què tots els nodes interns només tenen un fill.

Entendrem l'arbre binari degenerat a través d'exemples.

L'arbre anterior és un arbre binari degenerat perquè tots els nodes només tenen un fill. També es coneix com un arbre inclinat a la dreta, ja que tots els nodes només tenen un fill correcte.

L'arbre anterior també és un arbre binari degenerat perquè tots els nodes només tenen un fill. També es coneix com un arbre inclinat a l'esquerra, ja que tots els nodes només tenen un fill esquerre.

Arbre binari equilibrat

L'arbre binari equilibrat és un arbre en el qual tant els arbres esquerre com dret difereixen en com a mínim 1. Per exemple, AVL i Arbres vermell-negres són arbre binari equilibrat.

Entendrem l'arbre binari equilibrat mitjançant exemples.

L'arbre anterior és un arbre binari equilibrat perquè la diferència entre el subarbre esquerre i el subarbre dret és zero.

L'arbre anterior no és un arbre binari equilibrat perquè la diferència entre el subarbre esquerre i el subarbre dret és més gran que 1.

cadena adjunta java

Implementació de l'arbre binari

Un arbre binari s'implementa amb l'ajuda de punters. El primer node de l'arbre es representa amb el punter arrel. Cada node de l'arbre consta de tres parts, és a dir, dades, punter esquerre i punter dret. Per crear un arbre binari, primer hem de crear el node. Crearem el node definit per l'usuari tal com es mostra a continuació:

 struct node { int data, struct node *left, *right; } 

En l'estructura anterior, dades és el valor, punter esquerre conté l'adreça del node esquerre i punter dret conté l'adreça del node dret.

Programa d'arbre binari en C

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

El codi anterior crida recursivament a la funció create() i crea un nou node a cada trucada recursiva. Quan es creen tots els nodes, es forma una estructura d'arbre binari. El procés de visitar els nodes es coneix com a travessa d'arbres. Hi ha tres tipus de recorreguts utilitzats per visitar un node:

• Travessa en ordre
• Travessa de comanda prèvia
• Travessa postal