Sé que podría ver algunos ejemplos, pero pasé mucho tiempo tratando de obtener esto yo mismo y me gustaría saber si tuve éxito. Pasa las pruebas que le hice, pero ¿puedo obtener una verificación de cordura en el código?
Cada nodo es una clase de javascript con una propiedad izquierda y derecha que es igual a otro nodo o indefinido. También escribí un método .hasChildren() para la clase Node que hace lo que parece.
Esta función es un método de mi clase BinaryTree, que tiene otro método .height() que toma cualquier nodo y determina la altura del árbol a partir de ese nodo. Aquí está el método .isBalanced() , que también toma un nodo para comenzar:
BinaryTree.prototype.isBalanced = function (node = this.root) { const rBalanced = (node) => { // a node with no children is balanced if (!node.hasChildren()) { return true } // get the difference in heights between the branches, using -1 for a missing child const left = node.left ? this.height(node.left) : -1 const right = node.right ? this.height(node.right) : -1 // if the difference is 1 or less, this node is balanced const balanced = Math.abs(left - right) <= 1 // ensure that every child tree, if it exists, is also balanced if (node.left && !node.right) { return balanced && rBalanced(node.left) } if (!node.left && node.right) { return balanced && rBalanced(node.right) } return balanced && rBalanced(node.left) && rBalanced(node.right) } // a nonexistent tree is balanced (???) return node ? rBalanced(node) : true } Y aquí está el método .height() por si acaso:
BinaryTree.prototype.height = function (node = this.root) { const rHeight = (node, count) => { return Math.max( count, node.left ? rHeight(node.left, count + 1) : null, node.right ? rHeight(node.right, count + 1) : null ) } return node ? rHeight(node, 1) : 0 }EDITAR: Aquí hay un jsfiddle con el código de trabajo https://jsfiddle.net/jonahsaltzman/u2jrosLm/
La función isBalanced es correcta, pero hay una inconsistencia en la función de height , lo que hace que isBalanced devuelva un resultado incorrecto. Por ejemplo, para este árbol, devuelve false , pero se espera true :
2 / 1 El problema de height es que devuelve 0 cuando no hay ningún nodo. Pero en isBalanced usas -1 en ese caso. Compara estas dos expresiones tomadas de cada una de estas funciones:
node ? rHeight(node, 1) : 0y:
node.left ? this.height(node.left) : -1 Esto no es consistente. O un nodo inexistente tiene altura -1 o tiene altura 0, pero aquí ha mezclado los dos. Dado que la norma es considerar que un árbol vacío tiene una altura -1, cambie el código en height :
node ? rHeight(node, 0) : -1 // ^^ ^^