0

私は1つの試験の練習をしていますが、理解できない例が1つあります。とにかく、タスクは次のようになります。

次のような左子右兄弟ツリーのデータ構造があります。

public class TreeLCRSnode {
    public TreeLCRSnode parent, leftSon, rightSibling;
}

平均の葉の高さの結果を返すdoubleavgH（TreeLCRSnode root）という名前の関数を作成する必要があります。

誰もが確実に理解できるように、leafは子のないノードです。たとえば、木が次のようになっている場合、

4
|
2----7
|
3

次に、2つの葉があります。1つは高さ1（7番）に、もう1つは高さ2（3番）にあります。

4

3 に答える 3

1

このタスクでは、いくつかのグローバル変数を使用する必要があると思います。

  • 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-09T09:22:54.340 に答える
1

これは、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-03T11:10:02.167 に答える
0

まず、ツリーをトラバースするプログラムを作成する必要があります。何かのようなもの：

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

これにより、すべてのノードにアクセスできます。次に、ノードが葉であるかどうかを判断し、平均を計算する方法を理解する必要があります (ヒント: 深さを渡し、これまでに見つかった葉の深さの合計を追跡し、見つかった葉の総数を追跡します)。遠い）。

于 2012-09-08T18:02:31.800 に答える