0

これは宿題です。偶数のデータ値を含むツリー構造のノードの数を見つけようとしています。以下は、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;
}

これが私のメインクラスの一部です：

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 が返されます。助言がありますか？

4

1 に答える 1

3

条件を間違えました。

ノードが null の場合、答えは 0 です。

ノードが偶数の場合、1 + 左サブツリーの偶数ノード数 + 右サブツリーの偶数ノード数になります。

ノードが奇数の場合、0 + 左サブツリーの偶数ノード数 + 右サブツリーの偶数ノード数になります。

于 2012-12-02T18:03:31.353 に答える