左邊兒童右邊同胞二叉樹的平均葉高

我正在練習一個考試，我有一個例子，我不知道。無論如何，任務是這樣的：左邊兒童右邊同胞二叉樹的平均葉高

您有左子右兄弟樹的數據結構，看起來這樣的：
public class TreeLCRSnode { 
    public TreeLCRSnode parent, leftSon, rightSibling; 
} 
你需要寫一個名爲函數雙avgH（TreeLCRSnode根）將返回平均葉高的結果。

可以肯定，大家都明白，葉子是沒有任何孩子的節點。因此，例如，如果一個樹看起來像這樣，

4 
| 
2----7 
| 
3

然後在兩個葉，一個在高度1（無7）和一個在高度2（3號）。

來源

2012-09-08 dperitch

我認爲這個任務，你需要使用幾個全局變量：

currentHeight - 在遞歸
leafHeightSum當前高度 - 所有當前發現的葉子
leafNumber - 所有的計數發現了到現在離開

然後將溶液可以是這樣的：

int currentHeight, leafHeightSum, leafNumber; 
double traverse(TreeLCRSnode node) { 
    currentHeight = 0; 
    leafHeightSum = 0; 
    leafNumber = 0; 
    traverseHelper(node); 
    // if the tree can be empty you might need a check here. 
    return (double)leafHeightSum/(double)leafNumber; 
} 

void traverseHelper(TreeLCRSnode node) { 
    while (node != null) { 
     if (node.leftSon) { 
      currentHeight++; 
      traverseHelper(node.leftSon); 
      currentHeight--; 
     } else { 
      leafHeightSum += currentHeight; 
      leafNumber++; 
     } 
     node = node.rightSibling; 
    } 
}

來源

2012-09-09 09:22:54

如果你問我，這看起來很好。謝謝鮑里斯。 – dperitch

首先你需要編寫一個遍歷樹的程序。像這樣：

void traverse(TreeLCRSnode node) { 
    while (node != null) { 
     if (node.leftSon) traverse(node.leftSon); 
     node = node.rightSibling; 
    } 
}

這將讓你到所有的節點。然後，你只需要確定節點是否是一片葉子，並找出如何計算平均值（提示：繞過一個深度，記錄到目前爲止發現的葉片深度總和以及發現的葉片總數遠）。

來源

2012-09-08 18:02:31

我已經做到這一點，但我仍然不知道如何前進。如何檢測我在哪個級別，如何計算所有級別以及如何計算所有葉子？特別是當我只能將一個參數發送到遞歸函數時。 – dperitch

這是對Boris Strandjev answer的輕微修改。它的目標是要多一點，並避免全局變量，因爲currentHeight是按值傳遞的，leafNumber是通過引用傳遞的，葉高的總和是返回值。

double traverse(TreeLCRSnode node) { 
    int leafNumber=0; 

    return (double)traverseHelper(node,0,&leafNumber)/(double)leafNumber; 
} 

int traverseHelper(TreeLCRSnode node, int currentHeight, int *leafNumber) { 
    if(!node) return 0; 

    if(!node.leftSon) { 
     (*leafNumber)++; 
     return currentHeight + traverse(node.rightSibling, currentHeight, leafNumber); 
    } else { 
     return traverse(node.leftSon, currentHeight+1, leafNumber) + traverse(node.rightSibling, currentHeight, leafNumber); 
    } 
}

來源

2012-12-03 11:10:02 Bula

左邊兒童右邊同胞二叉樹的平均葉高

回答

相關問題