Skew Binary Trees

Question

1) Qu'entend-on par le terme arbre binaire déséquilibré et comment on peut écrire un algorithme pour le tester?

2) J'ai un problème qui demande d'écrire une fonction pour tester la profondeur d'un arbre binaire. Je pense que cela fonctionnerait, mais pas sûr ....:

function getDepth(Node n){ 
    if(node == null){ 
     return 0; 
    } 
    return 1 + Math.max(getDepth(node.left), getDepth(node.right)); 
} 
getDepth(root); 

Quelqu'un peut-il me donner des pointeurs ...

Answer 1

1) arbre binaire obliquité est pas un terme commun largement 100% (même Google obtient confus). Recherchez vos notes de cours ou votre livre pour voir ce qu'elles signifient.

1. Pour tester est un arbre a autant de nœuds que leves, vous pouvez simplement utiliser la fonction que vous avez déjà que les niveaux de compte et une autre fonction pour compter le nombre de noeuds.

   Cependant, vous devriez être en train de faire un autre algorithme, plus efficace, qui se termine plus tôt si vous trouvez que le nombre de nœuds ne peut pas être le même que le nombre de niveaux.

2. La fonction de profondeur est correcte. Après tout, n'est-ce pas tiré directement de la définition de la profondeur de l'arbre?

   (le seul nitpick possible est la profondeur (null) = 1. Juste être sûr que vous ne avez pas besoin de profondeur (null) = 0 à la place)

Answer 2

Skewed arbre binaire est l'arbre qui a seulement un type de sous-arbres. Si un arbre a seulement quitté les sous-arbres, il est laissé à l'arbre incliné et vice versa.