爲樹中的樹葉指定不同的值

我正在嘗試爲樹中的每個樹葉指定數字。爲樹中的樹葉指定不同的值

例如，如果我們有一個具有6個葉一棵樹，我想葉有從0號到5

我不知道爲什麼我的代碼無法正常工作，我一直嘗試很多次，即使在遞歸的方式，但它似乎我失去了一些東西..

public class Node { 

    int index; 
    int id; 
    Node left; 
    Node right; 

    // Constructor and setters/getters. 

    public static void num(Node n) { 

    int ini=0; 
    if(n==null) 
    { 

    } 
    if(n.isLeaf()) 
    { 
     n.index=ini; 
     ini++; 
    } 
    if(!n.isLeaf()) 
    { 
     num(n.getleft()); 
     num(n.getRight()); 
    } 
}

我也希望自己能在樹上的葉子的數量。

例如，我們的樹看起來像

        1 
           / \ 
           2  3 
          /\ /\ 
          6 9 8 10 
         /
          4 
    public static int numberChild(Node n, int count) 

{ 
    if (n == null) { 
     return 0; 
    } 
    if (n.getleft() == null && n.getRight() == null) { 
     return 1 + count; 
    } else { 
     int lc = numberChild(n.getleft(), count); 
     int rc = numberChild(n.getRight(), lc); 
     return rc; 
    } 

}

會給我一個錯誤的葉數，2，而不是4！

任何幫助？

來源

2016-12-01 Zok

您的樹是否以任何方式排序，並且您是否希望以任何順序分配標籤？ –

這棵樹沒有排序，但葉子是，我們開始從左到右索引。這意味着我們需要一個反向波蘭標記。 – Zok

我不會在你的代碼中看到任何錯誤。你可以嘗試調試器嗎？ –

只是想出了什麼是錯的，我分配指標代碼

public void num(Node n) { 


     if(n.getleft()!=null)num(n.getleft()); 
     if(n.getRight()!=null)num(n.getRight()); 
     if(n.isLeaf()) 
     { 
      n.assignIndex(ini); 
      ini++; 
     } 

}

現在它工作得很好:)。謝謝

來源

2016-12-01 05:58:33 Zok

感謝您的分享。所以你現在把'ini'聲明爲一個字段而不是局部變量？ –

是的，因爲我認爲當我把它作爲函數中的局部變量時，每次我調用遞歸時，它都重新初始化爲0 .. – Zok

如果n == null您返回0.您應該返回count或您以前的計數丟失。在你的例子中，當爲6節點計算葉數時，你正確地從它下面的4節點獲得1。然後你給不存在的右邊的孩子調用numberChild()，它返回0，所以你返回的6個節點的計數是0，而不是1.

編輯：給葉子賦值我相信你應該使用相同的用於計算節點的想法，將計數傳遞給遞歸方法，以便知道有多少葉子已經編號到當前節點的左側，並返回更新的計數。您的num方法將像您的numberChild方法的另一個版本一樣，通過將新索引分配給葉節點進行擴展。

來源

2016-12-01 05:48:40

是的，我只是想到了這一點，並修改了我的代碼。現在我正在努力爲從左到右的每個葉子賦值。對於上面的樹，我想要node4.index = 0 node9.index = 1 node8.index = 2 node9.index = 3 – Zok

爲樹中的樹葉指定不同的值

回答

相關問題