在 Java 中按级别打印 AVL 树

Question

我正在尝试获取 AVL 树并逐层显示它，但不知何故我失败了并且不知道在哪里。附件是显示我当前输出的图像。我实际上应该得到的是一个完整的二叉树，所以显然出了问题。在所附的图片中，有一张我的 "byLevel" 打印功能的照片，所以你可以看到我是如何尝试打印它们的，我会附上我的插入功能，因为这是唯一重要的两个功能这部分。我很感激任何帮助，我不明白我做错了什么，因为这是一种常用的算法。

private Node insert(Node newNode, String newWord){
    if(newNode == null){
        newNode = new Node(newWord);
    }
    else if (newWord.compareToIgnoreCase(newNode.getReservedWord()) < 0){
        newNode.setlChild(insert(newNode.getlChild(), newWord));

        if(depth(newNode.getlChild()) - depth(newNode.getrChild()) == 2){
            if(newWord.compareToIgnoreCase(newNode.getlChild().getReservedWord()) < 0){
                newNode = rotateWithLeftChild(newNode);
            }
            else{
                newNode = doubleWithLeftChild(newNode);
            }
        }
    }
    else if (newWord.compareToIgnoreCase(newNode.getReservedWord()) > 0){
        newNode.setrChild(insert(newNode.getrChild(), newWord));

        if(depth(newNode.getrChild()) - depth(newNode.getlChild()) == 2){
            if(newWord.compareToIgnoreCase(newNode.getrChild().getReservedWord()) > 0){
                newNode = rotateWithRightChild(newNode);
            }
            else{
                newNode = doubleWithRightChild(newNode);
            }
        }
    }
    else;

    newNode.setDepth(max(depth(newNode.getlChild()), depth(newNode.getrChild()) + 1));
    /*if(!this.getAllNodes().contains(newNode)){
        this.getAllNodes().add(newNode);
    }*/
    return newNode;
}

private Node rotateWithLeftChild(Node nodeToRotate){
    Node newNode = nodeToRotate.getlChild();
    nodeToRotate.setlChild(newNode.getrChild());
    newNode.setrChild(nodeToRotate);
    nodeToRotate.setDepth(max(depth(nodeToRotate.getlChild()), depth(nodeToRotate.getrChild()) + 1));
    newNode.setDepth(max(depth(newNode.getlChild()), nodeToRotate.getDepth() + 1));
    return newNode;
}

private Node rotateWithRightChild(Node nodeToRotate){
    Node newNode = nodeToRotate.getrChild();
    nodeToRotate.setrChild(newNode.getlChild());
    newNode.setlChild(nodeToRotate);
    nodeToRotate.setDepth(max(depth(nodeToRotate.getlChild()), depth(nodeToRotate.getrChild()) + 1));
    newNode.setDepth(max(depth(newNode.getrChild()), nodeToRotate.getDepth() + 1));
    return newNode;
}

private Node doubleWithLeftChild(Node nodeToRotate){
    nodeToRotate.setlChild(rotateWithRightChild(nodeToRotate.getlChild()));
    return rotateWithLeftChild(nodeToRotate);
}

private Node doubleWithRightChild(Node nodeToRotate){
    nodeToRotate.setrChild(rotateWithLeftChild(nodeToRotate.getrChild()));
    return rotateWithRightChild(nodeToRotate);
}

TestOutput

Answer 1

再次解决了我自己的问题，是的，提供的代码就足够了。问题很简单，我错误地计算了我的深度，将 +1 添加到 max 函数的第二个，而不是在 max 函数之后添加它。我认为这个问题本身就已经足够好了，因为 AVL 树是常见的编码。谢谢。

在 Java 中按级别打印 AVL 树

Printing an AVL Tree by level in Java

java

binary-tree

avl-tree

binary-search-tree