java - 查找树中包含偶数个数据值的节点数

Question

这是一项家庭作业。我尝试查找包含偶数数据值的树结构中的节点数。以下是我在名为 LinkedTree 的 Java 类中失败的尝试。

public int numEvenKeys() {
        return numEvenKeysTree(root);     
}

private static int numEvenKeysTree(Node root) {
        int num = 0;

        if (root == null)
            return 0;        
        else if (root.left != null || root.right != null)
            return num + numEvenKeysTree(root.left) 
                    + numEvenKeysTree(root.right);
        else if (root.key % 2 == 0)
            num = 1;

        return num;
}

这是我的主类(class)的一部分:

public static void main(String[] args) {
                Scanner in = new Scanner(System.in);

                LinkedTree tree = new LinkedTree();
                tree.insert(7, "root node");
                tree.insert(9, "7's right child");
                tree.insert(5, "7's left child");
                tree.insert(2, "5's left child");
                tree.insert(8, "9's left child");
                tree.insert(6, "5's right child");
                tree.insert(4, "2's right child");
                   ...
                *** remove a node of your choice ***
                   ...
                System.out.print("number of nodes with even keys in this tree: ");
                System.out.println(tree.numEvenKeys());
                   ...
    } 

作为引用，这里是内部类节点和类构造函数:

private class Node {
    private int key;         // the key field
    private LLList data;     // the data items associated with this key
    private Node left;       // reference to the left child/subtree
    private Node right;      // reference to the right child/subtree
    private Node parent;     // reference to the parent

    private Node(int key, Object data, Node left, Node right, Node parent){
        this.key = key;
        this.data = new LLList();
        this.data.addItem(data, 0);
        this.left = left;
        this.right = right;
        this.parent = parent;
    }

    private Node(int key, Object data) {
        this(key, data, null, null, null);
    }
}

// the root of the tree as a whole
private Node root;

public LinkedTree() {
    root = null;
}

树的结构为:

      7
     / \
    5   9
   / \ / 
  2  6 8
   \
    4

如果我选择删除节点 7，该方法应返回 4。但是，在我的实现中它返回 1。有什么建议吗？

Answer 1

你的条件有误。

如果节点为空，则答案为 0。

如果节点是偶数，则应该是1+左子树偶数节点数+右子树偶数节点数。

如果节点是奇数，则应为 0 + 左子树偶数节点数 + 右子树偶数节点数。