A árvore de classificação binária também é chamada de árvore de pesquisa binária. É uma árvore vazia ou uma árvore binária com as seguintes propriedades:
① Se a subárvore esquerda não estiver vazia, os valores de todos os nós na subárvore esquerda são menores que os valores de seu nó raiz;
②Se a subárvore direita não estiver vazia, os valores de todos os nós na subárvore direita são maiores que os valores de seu nó raiz;
③ As subárvores esquerda e direita também são árvores de classificação binárias, respectivamente.
Os seguintes implementos de código:
importar java.util.LinkedList; importar java.util.queue; nó de classe {public int data; nó público esquerdo; nó público à direita; public int leftmaxDistance; public int RightMaxDistance; public node (int dados) {this.data = data; this.left = null; this.right = null; }}/*** @author ty* Implementando uma árvore de classificação binária, incluindo inserção, travessia em ordem, travessia de pré-encomenda, travessia de pós-ordem e calcula a distância máxima de todos os nós*/classe pública Bininartree {private node root; public binarytree () {root = null; } public void insert (int dados) {node newNode = new Node (dados); if (root == null) root = newNode; else {nó corrente = root; Pai pai; while (true) {// Encontre a posição inserir pai = atual; if (data <current.data) {current = current.left; if (current == null) {parent.left = newNode; retornar; }} else {current = current.right; if (current == null) {parent.right = newNode; retornar; }}}}}}} // Os valores numéricos de entrada para criar uma árvore binária public void BuildTree (int [] dados) {for (int i = 0; i <data.length; i ++) {insert (dados [i]); }}} // O método de travessia na ordem implementa recursivamente INOrder public void (nó Localroot) {if (localroot! = Null) {inOrder (localroot.left); System.out.print (localroot.data+""); inOrder (localroot.right); }} public void inOrder () {this.inOrder (this.root); } // O método de travessia de pré -encomenda implementa recursivamente a pré -encomenda public void (node localroot) {if (localroot! = Null) {System.out.print (localroot.data+""); pré -encomenda (localroot.left); pré -encomenda (localroot.right); }} public void preordes () {this.preorder (this.root); } // O método Traversal do PostRandimal implementa recursivamente o Postorder public void (nó localroot) {if (localroot! = Null) {Postorder (localroot.left); PROTORMA (LOCALROOT.RIGHT); System.out.print (localroot.data+""); }} public void postorder () {this.PostOrder (this.root); } /*** Árvore binária de travessia de sequência de camadas: agora coloque o nó raiz na fila e pegue um nó da fila sempre para imprimir o valor do nó. * Se este nó tiver um nó filho, coloque seu nó filho na cauda da fila até que a fila esteja vazia*/ public void layerTranverse () {if (this.root == null) retornar; Fila <Node> q = new LinkedList <Node> (); q.add (this.root); while (! q.isEmpty ()) {nó 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; private int max (int a, int b) {return a> b? a: b; } public void findMaxDistance (nó 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); // Calcule a distância máxima do nó raiz na árvore da palavra esquerda if (root.left! = Null) root.leftmaxDistance = max (root.left.leftmaxDistance, root.left.rightmaxDistance) +1; // Calcule a distância máxima do nó raiz na árvore da palavra certa if (root.right! = Null) root.rightmaxDistance = max (root.right.leftmaxDistance, root.right.rightmaxDistance) +1; // Obtenha a distância máxima de todos os nós da árvore binária if (root.leftmaxDistance+root.rightmaxDistance> maxlen) {maxlen = root.leftmaxDistance+root.rightmaxDistance; }} public static void main (string [] args) {binarytree bitree = new BinaryTree (); int [] dados = {2,8,7,4,9,3,1,6,7,5}; bitree.buildtree (dados); System.out.print ("Travessal na ordem da árvore binária:"); bitree.inOrder (); System.out.println (); System.out.print ("Travessal de pré-encomenda da árvore binária:"); bitree.preorder (); System.out.println (); System.out.println (); System.out.println (); System.out.print ("Travessal de pós-ordem da árvore binária:"); bitree.PostOrder (); System.out.println (); System.out.print ("Travessal de ordem de camada da árvore binária:"); bitree.layertranverse (); System.out.println (); bitree.findmaxDistance (bitree.root); System.out.println ("Distância máxima dos nós na árvore binária:"+bitree.maxlen); }}O exposto acima é todo o conteúdo deste artigo. Espero que o conteúdo deste artigo seja de ajuda para estudar ou trabalhar de todos. Eu também espero apoiar mais wulin.com!