algorithm - 左子右兄弟二叉树的平均叶高

Question

我正在为一场考试练习，但我有一个我想不通的例子。无论如何，任务是这样的：

您有一个左子右兄弟树的数据结构，如下所示：

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

您需要编写一个名为 double avgH(TreeLCRSnode root) 的函数，该函数将返回平均叶高的结果。

为了确保每个人都明白，叶子是一个没有任何孩子的节点。例如，如果一棵树看起来像这样，

4
|
2----7
|
3

然后有两片叶子，一张在高度 1（第 7 号），一张在高度 2（第 3 号）。

Answer 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;
    }
}

Answer 2

这是对Boris Strandjev 答案的轻微修改。它的目标是更简洁一些并避免全局变量，因为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);
    }
}

Answer 3

首先，您需要编写一个遍历树的程序。就像是：

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

这将使您到达所有节点。然后你只需要确定节点是否是叶子，并弄清楚如何计算平均值（提示：传递一个深度，跟踪到目前为止找到的叶子的深度总和，以及找到的叶子总数远的）。