|
structures de données efficaces d'optimiser la performance d'un programme en le rendant plus facile pour le programme pour trouver les données dont il a besoin . Arbres binaires de recherche sont l'une des structures de données les plus efficaces pour la recherche par le biais d'un ensemble de données ordonnées . Si votre structure de données est un arbre binaire de recherche organisé ou un arbre binaire standard , vous pouvez trouver la hauteur de l' arbre dans Java via une fonction récursive simple. Arbre Structure
Un arbre binaire constitué d'un ensemble de noeuds interconnectés . Chaque noeud possède entre zéro et deux nœuds enfants. Chaque noeud à l'exception du noeud racine a exactement un nœud parent. Le noeud racine n'a pas de nœuds parents. Java n'a pas de classe intégrée de l'arbre binaire , mais vous pouvez créer vos propres à partir de zéro ou de le télécharger à partir d'Internet.
Arbre Hauteur
La hauteur de un arbre binaire est le nombre maximum de noeuds , non compris le noeud de racine , le long d' une seule traversée verticale de l'arbre binaire . Par exemple , un arbre binaire à un seul noeud aurait une hauteur égale à zéro . Un arbre binaire avec un noeud racine de deux noeuds fils aurait une hauteur de un. Si l'un de ces nœuds enfants avait son propre nœud enfant , l'arbre aurait une hauteur de trois.
Théorie
La façon la plus simple pour déterminer la hauteur d'un arbre binaire en Java est une méthode récursive . Cette méthode accepte un seul noeud comme argument et retourne la hauteur de l'arbre binaire en dessous du noeud d'argument . La méthode elle-même appelle une nouvelle fois pour chacun des enfants les nœuds et les magasins de l' argument node le résultat comme une variable entière . Il compare les deux variables qui représentent la hauteur de chacun de ses enfants , ajoute une de la plus grande des deux variables et renvoie le résultat . Si le nœud de l'argument passé à la méthode est nulle , la méthode renvoie négative.
Algorithme
La méthode Java qui suit va calculer la hauteur d'un arbre binaire. Il accepte le nœud racine d'un arbre binaire comme argument. Sinon, vous pouvez passer à un autre nœud de l'arbre binaire dans la méthode pour trouver la hauteur de l'arbre ci-dessous ce nœud. Le code suivant suppose que chaque nœud de l'arbre binaire est de type " BinaryTreeNode " et chaque noeud contient des méthodes permettant de renvoyer les enfants à gauche et à droite de ce nœud appelé " getLeftChild " et " getRightChild . "
< p> private int findHeight ( BinaryTreeNode currentNode ) {if ( currentNode.equals ( null) ) {return -1 ;} int leftHeight = findHeight ( currentNode.getLeftChild ()); int Rightheight = findHeight ( currentNode.getRightChild ()); int greatestHeight = Math.max ( leftHeight , Rightheight ) ; greatestHeight de retour; }
|
