getNumberOfInteriorNodes二叉樹的Java

Question

以後有什麼@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()); 
} 

我的測試失敗，在第三斷言與錯誤。計數永遠不會超過零。以下是錯誤我得到：

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

任何進一步的幫助，將不勝感激。

Answer 1

你的問題是，你只有一個共享current變量，當您使用遞歸。它將在遞歸調用中被覆蓋。相反，你必須把它作爲參數，所以你的遞歸函數必須是：

public int getNumberOfInteriorNodes(Node<E> current) 

而且在第一調用（代碼中的其他地方），你傳遞root它：

... = getNumberOfInteriorNodes(root); 

然後你需要在遞歸調用中通過修改後的值，對於右側：

count += getNumberOfInteriorNodes(current.right); 

對於左側，自然也是如此。否return在這裏，否則它會返回並不計算對方！也沒有+1，如果存在右側和左側，那麼它將是+2。相反，return count + 1;在方法的結尾（是的，你確實需要它）。

---

而且，在你第一次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) { 
    ... 
} 

Answer 2

下面是一些代碼，做的伎倆。順便說一句：沒有孩子的節點是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); 
    } 
}