L'arbre de tri binaire est également appelé arbre de recherche binaire. C'est soit un arbre vide, soit un arbre binaire avec les propriétés suivantes:
① Si le sous-arbre gauche n'est pas vide, les valeurs de tous les nœuds du sous-arbre gauche sont plus petites que les valeurs de son nœud racine;
② Si le sous-arbre droit n'est pas vide, les valeurs de tous les nœuds du sous-arbre droit sont supérieures aux valeurs de son nœud racine;
③Les sous-arbres gauche et droit sont également respectivement des arbres de tri binaires.
Le code suivant implémente:
import java.util.linkedlist; import java.util.queue; nœud de classe {public int data; Node public laissé; Node public droit; public int LeftMaxDistance; public int reightmaxDistance; Node public (int data) {this.data = data; this.left = null; this.Right = null; }} / ** * @author ty * Implémentation d'un arbre de tri binaire, y compris l'insertion, la traversée dans l'ordre, la traversée précommande, la traversée post-commande et le calcul de la distance maximale de tous les nœuds * / classe publique Binarytree {Root nœud privé; public binaryTree () {root = null; } public void insert (int data) {node newNode = new node (data); if (root == null) root = newNode; else {nœud current = root; Node parent; while (true) {// trouver la position d'insertion parent = courant; if (data <current.data) {current = current.left; if (current == null) {parent.left = newNode; retour; }} else {current = current.Right; if (current == null) {parent.Right = newNode; retour; }}}}}}} // Valeurs numériques d'entrée pour créer un arbre binaire public void buildTree (int [] data) {for (int i = 0; i <data.length; i ++) {insert (data [i]); }}} // Méthode de traversée in-ordre Implémente récursivement public void inOrder (nœud localroot) {if (localroot! = Null) {inOrder (localroot.left); System.out.print (localroot.data + ""); inOrder (localroot.Right); }} public void inOrder () {this.inorder (this.root); } // La méthode de traversée de précommande implémente récursivement la précommande de public public (nœud localroot) {if (localroot! = Null) {System.out.print (localroot.data + ""); précommande (localroot.left); précommande (LocalRoot.Right); }} public void preorder () {this.preorder (this.root); } // La méthode de traversée post-ordre implémente récursivement public void postorder (nœud localRoot) {if (localroot! = Null) {postorder (localroot.left); Postorder (localroot.right); System.out.print (localroot.data + ""); }} public void postorder () {this.postorder (this.root); } / ** * Arbre binaire de traversée de couche-séquence: mettez maintenant le nœud racine dans la file d'attente, puis prenez un nœud de la file d'attente à chaque fois pour imprimer la valeur du nœud. * Si ce nœud a un nœud enfant, mettez son nœud enfant dans la queue de la file d'attente jusqu'à ce que la file d'attente soit vide * / public void couchetranverse () {if (this.root == null) return; File d'attente <Node> q = new LinkedList <Node> (); q.add (this.root); while (! q.isempty ()) {nœud n = q.poll (); System.out.print (n.data + ""); if (n.left! = null) q.add (n.left); if (n.right! = null) q.add (n.right); }} private int maxlen = 0; privé int max (int a, int b) {return a> b? a: b; } public void findMaxDistance (nœud root) {if (root == null) return; if (root.left == null) root.leftMaxDistance = 0; if (root.right == null) root.RightMaxDistance = 0; if (root.left! = null) findMaxDistance (root.left); if (root.Right! = null) findMaxDistance (root.Right); // Calculez la distance maximale du nœud racine dans l'arborescence de mot gauche if (root.left! = Null) root.leftMaxDistance = max (root.left.leftmaxDistance, root.left.RightMaxDistance) +1; // Calculez la distance maximale du nœud racine dans l'arbre de mot droit if (root.Right! = Null) root.RightMaxDistance = max (root.Right.leftmaxDistance, root.Right.RightMaxDistance) +1; // Obtenez la distance maximale de tous les nœuds de l'arbre binaire if (root.leftMaxDistance + root.RightMaxDistance> maxlen) {maxlen = root.leftmaxDistance + root.RightMaxDistance; }} public static void main (string [] args) {binarytree bitree = new binarytree (); int [] data = {2,8,7,4,9,3,1,6,7,5}; bitree.buildTree (données); System.out.print ("Traversion dans l'ordre de l'arbre binaire:"); bitree.inOrder (); System.out.println (); System.out.print ("Transfert de précommande de l'arbre binaire:"); bitree.preorder (); System.out.println (); System.out.println (); System.out.println (); System.out.print ("Traversion post-ordre de l'arbre binaire:"); bitree.postorder (); System.out.println (); System.out.print ("Traversion de l'ordre de couche de l'arbre binaire:"); bitree.layertranverse (); System.out.println (); bitree.findMaxDistance (bitree.root); System.out.println ("Distance maximale des nœuds dans l'arbre binaire:" + bitree.maxlen); }}Ce qui précède est tout le contenu de cet article. J'espère que le contenu de cet article sera d'une aide à l'étude ou au travail de chacun. J'espère également soutenir plus Wulin.com!