java - 需要帮助计算任何二叉树的左右子分支的深度

Question

我必须为我的数据结构类(class)编写一个 AVL 树，并且一直致力于计算子树​​的平衡因子，以便我知道在哪里以及如何旋转树。

谢谢，埃里克

编辑:

我知道必须计算二叉树中的节点数。

private int countTotalNodes(AVLNode<T> start){

    AVLNode<T> current = start;

    if(current.getLeft() != null){
        return countTotalNodes(current.getLeft());
    }
    if(current.getRight() != null){
        return countTotalNodes(current.getRight());
    }
    return 1;

} 

Answer 1

我认为 AVL 树的通常实现将节点的高度存储在节点本身中，并在插入、剪切和链接操作中得到更新。在这些操作之后，我们必须检查较高节点的高度是否仍然正确，如下所示:

/**
 * Recursively updates heights starting with given node. 
 * If height of given node is already correct we know 
 * that we can stop.
 */
private void updateHeights(AvlNode<T> node){
    if(node == null) return;
    int heightLeft = node.left != null ? node.left.height : -1;
    int heightRight = node.right != null ? node.right.height : -1;
    int height = heightLeft > heightRight ? heightLeft + 1 : heightRight + 1;
    if(node.height != height){
        node.height = height;
        updateHeights(node.parent);
    }
}

可以说，这总是在最高更改节点的父节点上调用。美好的旧时光 - 实现 AVL 树是一个有趣的小项目 - 祝你好运......并彻底测试它!