estruturas de dados eficientes otimizar o desempenho de um programa , tornando-o mais fácil para o programa para encontrar os dados de que necessita. Árvores binárias de pesquisa são uma das estruturas de dados mais eficientes para pesquisar através de um conjunto de dados ordenado. Se a sua estrutura de dados é uma árvore binária de busca organizada ou uma árvore binária padrão , você pode encontrar a altura da árvore em Java através de uma função recursiva simples. Estrutura de árvore
Uma árvore binária consiste em um conjunto de nós interconectados . Cada nó tem entre zero e dois nós filho. Cada nó com a excepção de o nó de raiz tem exactamente um nó pai . O nó raiz não tem nós pai . Java não tem uma classe de árvore built-in binário , mas você pode criar o seu próprio a partir do zero ou um download da Internet.
Árvore Altura
A altura uma árvore binária é o número máximo de nós , não incluindo o nó da raiz , ao longo de uma única passagem vertical através da árvore binária . Por exemplo , uma árvore binária com um único nó que tem uma altura igual a zero . Uma árvore binária com um nó raiz com dois nós filhos teriam uma altura de um. Se um desses nós filho tinha o seu próprio nó filho , a árvore teria uma altura de três.
Teoria
A maneira mais simples para determinar a altura de uma árvore binária em Java é com um método repetitivo . Este método aceita um único nó como um argumento e retorna a altura da árvore binária abaixo do nó argumento. O método chama -se novamente para cada um de nós filhos do nó argumento e armazena o resultado como uma variável inteira . Ele compara as duas variáveis , que representam a altura de cada um dos seus filhos , adiciona um para a maior das duas variáveis e devolve o resultado . Se o nó argumento passado para o método for nulo, o método retorna uma negativa.
Algoritmo
O seguinte método de Java irá calcular a altura de uma árvore binária . Ele aceita o nó raiz de uma árvore binária como argumento. Alternativamente, você pode passar um nó diferente da árvore binária para o método para encontrar a altura da árvore abaixo desse nó . O código a seguir pressupõe que cada nó da árvore binária é do tipo " BinaryTreeNode " e cada nó contém métodos que retornam os filhos esquerdo e direito do que nó chamado " getLeftChild " e " getRightChild ".
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 ); retornar greatestHeight ;}