java - 在java中计算子树WAVL中有多少内部叶子在O(1)中

Question

我正在实现 WAVL 树和 WAVL 节点类。在 WAVL 节点类中，我应该创建一个方法来计算节点子树中存在多少内部节点。我应该以 O(1) 的时间复杂度做到这一点。有什么建议吗？

我写的类是:

package coding_ex1;

public class WAVLNode
    {
    WAVLNode left;
    WAVLNode right;
    WAVLNode parent;
    int rank;
    int key;
    String value;

    public WAVLNode() //*constructor
    {
        this.left=null;
        this.right=null;
        this.parent=null;
        this.rank=0;
        this.key=0;
        this.value=null;
    }

    public int getKey() //*gets WAVLNode. if external leaf, return -1. else, return key

    {
        if (this.rank==-1)
        {
            return -1;
        }
        return key;
    }

    public String getValue()//*gets WAVLNode. if external leaf, returns null. else, returns value
    {
        if (this.rank==-1)
        {
            return null;
        }
        return value;
    }

    public WAVLNode getLeft()//* get WAVLNode. returns left (if there is no left, the value of left is null)
    {
        return left;
    }

    public WAVLNode getReft()//* get WAVLNode. returns right (if there is no right, the value of right is null)
    {
        return right;
    }

    public boolean isInnerNode()//*gets WAVLNode. returns true for internal leaf. else, returns false
    {
        if(this.right!=null || this.left!=null)
        {
            return true;
        }
        return false;
    }

}

Answer 1

您应该添加一个字段和方法。

private int internalNodeCount = 0; // initially count as leaf

public int internalNodeCount() {
    return internalNodeCount;
}

public void setLeft(WAVLNode node) {
    this.left = node;
    setInternalNodeCount();
}

public void setRight(WAVLNode node) {
    this.right = node;
    setInternalNodeCount();
}

void setInternalNodeCount() {
    if (isInnerNode()) {
        internalNodeCount = 1; // count for self
        if (left != null)
            internalNodeCount += left.internalNodeCount;
        if (right != null)
            internalNodeCount += right.internalNodeCount;
    } else
        internalNodeCount = 0;
}