expliquer:
La profondeur de l'arbre binaire: un chemin vers l'arbre est formé du nœud racine au nœud (y compris le nœud racine et feuille) qui passe par le nœud feuille à son tour. La longueur du chemin le plus long est la profondeur de l'arbre.
Largeur d'un arbre binaire: chaque couche d'un arbre binaire a un certain nombre de nœuds. Le nombre de nœuds dans la couche avec le plus grand nombre de nœuds est appelé la largeur de l'arbre binaire.
Idée: implémentation récursive.
1. Chaque nœud peut être considéré comme un nœud racine
2. La profondeur du nœud racine (tout nœud) est égal à sa profondeur de sous-arbre gauche ou droite +1
3. Commencez à traverser le nœud racine. Si vous traversez le nœud feuille, la profondeur est 0
// la profondeur de l'arbre binaire public statique intatique intripte (nœud root) {if (root == null) {return 0; } int dl = profondeur (root.leftchild); int dr = profondeur (root.RightChild); retourner dl> dr? DL + 1: DR + 1; }2. La largeur de l'arbre binaire
Idée: ajoutez un compteur pendant la traversée de séquence de couche pour enregistrer le nombre de nœuds dans chaque couche
1. Lorsque chaque couche est hors de la file d'attente, le nombre de nœuds dans la couche suivante est en fait la taille () de la file d'attente.
2. À la fin de chaque traversée de couche, comparez la largeur maximale avec le nombre actuel de nœuds et enregistrez la valeur maximale.
public static int static width (nœud root) {if (root == null) return 0; file d'attente <Node> q = new LinkedList <Node> (); q.add (root); int width = 1; // maximum width int len = 1; // le nombre actuel de nœuds sur le caler while (q.size ()> 0) {while (len -> 0) {node = q.poll (); if (node.leftchild! = null) {q.add (node.leftchild);} if (node.RightChild! = null) {q.add (node.RightChild);}} len = q.size (); // Après chaque couche de la couche, l'enregistrement du nombre de nœuds dans la couche suivante dans la couche suivante? largeur: q.size ();} largeur de retour;}Résumer
Ce qui précède concerne la description de la langue java de la profondeur et de la largeur de l'arbre binaire. J'espère que ce sera utile à tout le monde. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!