0

在@hyde 告诉我之后，这就是我所做的：

Node<E> current = root;
int count = 0;

public int getNumberOfInteriorNodes() {
    if (current == null || (current.left == null && current.right == null)) {
        return count;
    }
    else {
        if (current.right != null) {
            Node<E> tmp = current;
            current = current.right;
            count += getNumberOfInteriorNodes();
            current = tmp;
          }
          if (current.left != null) {
              Node<E> tmp = current;
              current = current.left;
              count += getNumberOfInteriorNodes();
              current = tmp;
          }
          return count + 1;
      }
}

下面是我的测试方法的样子：

public static void testGetNumberOfInteriorNodes() {
     BinarySearchTree<Integer> t;
     t = new BinarySearchTree<Integer>();
     Assert.assertEquals(0, t.getNumberOfInteriorNodes());
     t.add(2);
     Assert.assertEquals(0, t.getNumberOfInteriorNodes());
     t.add(1);
     Assert.assertEquals(1, t.getNumberOfInteriorNodes());
     t.add(5);
     Assert.assertEquals(1, t.getNumberOfInteriorNodes());
     t.add(4);
     Assert.assertEquals(2, t.getNumberOfInteriorNodes());
     t.add(3);
     Assert.assertEquals(3, t.getNumberOfInteriorNodes());
     t.add(6);
     Assert.assertEquals(3, t.getNumberOfInteriorNodes());
}

我的测试在第 3 个断言中失败并出现错误。计数永远不会超过零。这是我得到的错误：

Failure: junit.framework.AssertionFailedError: expected:<1> but was:<0>

任何进一步的帮助将不胜感激。

4

2 回答 2

1

current您的问题是，当您使用递归时，您只有一个共享变量。它将在递归调用中被覆盖。相反，您必须将其作为参数传递，因此您的递归函数需要：

public int getNumberOfInteriorNodes(Node<E> current)

在第一次调用时（代码中的其他地方），你传递root给它：

... = getNumberOfInteriorNodes(root);

然后你需要在递归调用中传递修改后的值，右侧：

count += getNumberOfInteriorNodes(current.right);

当然，左侧也是如此。不在return这里，否则它会返回而不计算对方！也没有+1，如果右侧和左侧都存在，那么它将是+2。相反，return count + 1;在方法结束时（是的，你确实需要它）。

此外，在您的第一个if测试中，没有意义的 if root == null，它没有做任何有用的事情（在这种情况下也没有任何害处，但它仍然是混乱的，这使得代码更难理解，并且如果您更改代码可能会成为问题）。

然后你似乎也有这个：int count==0;;

这甚至可以编译，还是复制粘贴错误？你应该使用赋值int count = 0;

如果您有方法没有参数的限制，您需要current在调用后恢复值。这是右侧的代码，对左侧执行相同的操作：

if (current.right!=null) {
    Node<E> tmp = current;
    current = current.right;
    count += getNumberOfInteriorNodes();
    current = tmp;
}

请注意，对于“真实”代码，这将是一种非常愚蠢的递归方式。

如果这个“无参数”只是 API 限制，那么解决这个问题的常用方法是使用私有辅助方法：

public int getNumberOfInteriorNodes() {
    return recNumberOfInteriorNodes(root) 
}

private int recNumberOfInteriorNodes(Node<E> current) {
    ...
}
于 2013-04-09T17:19:56.810 回答
0

这是一些可以解决问题的代码。顺便说一句：没有孩子的节点是leaves.

class Node {
    Node left;
    Node right;
}

class Main {
    void test() {
        Node root = new Node();
        Node leftleft = new Node();
        Node left = new Node();
        Node right = new Node();
        Node rightright = new Node();
        Node rightleft = new Node();
        root.left = left;
        root.right = right;
        left.left = leftleft;
        right.left = rightleft;
        right.right = rightright;
        int c = getLeaves(root);
    }

    int getLeaves(Node node) {
        if (node == null)
            return 0;
        if (node.left == null && node.right == null) 
            return 1;
        return getLeaves(node.left) + getLeaves(node.right);
    }
}
于 2013-04-09T17:39:52.217 回答