1

如何递归地找到二叉树中节点高度的总和？

例子：

在此处输入图像描述

public int totalHeight() {
    return totalHeight(root);
}

private int totalHeight(BinaryNode<AnyType> n) {

    int totalHeight = 0;

    if (n.left == null && n.right == null)
        return totalHeight;
    if (n.left != null && n.right != null)
        return totalHeight + 1
                + Math.max(totalHeight(n.left), totalHeight(n.right));
    if (n.left != null)
        return totalHeight + 1 + Math.max(totalHeight(n.left), -1);
    if (n.right != null)
        return totalHeight + 1 + Math.max(-1, totalHeight(n.right));

    return totalHeight;
}

我试过这个，但它只得到树的高度而不是所有节点高度的总和。

我觉得很难在递归中跟踪计数器，似乎totalHeight每次递归调用都设置为0。情况不妙。

4

8 回答 8

1

一个简单的版本是执行两遍过程，首先记录每个节点的高度，然后遍历节点以总结它们。这种方法可以递归，但很容易在计算高度时通过求和来完成。

public static int totalHeightSum = 0;

private int calculateHeightAndAdd ( Node n )
{
     if ( n == null )
        return 0;

     int leftHeight = calculateHeightAndAdd ( n.left );
     int rightHeight= calculateHeightAndAdd ( n.right);

     int myHeight = 1 + Math.max ( leftHeight, rightHeight );

     totalHeightSum += myHeight;

     return myHeight;
}
于 2012-07-13T19:28:51.340 回答
0

鉴于您对节点高度的实现，让我们简单地调用它height(BinaryNode<?>)，您可以：

如果您有权访问集合中的所有节点：

int sumHeight(List<BinaryNode<?>> nodes) {
    int sum = 0;
    for (BinaryNode<?> node: nodes) {
        sum += height(node);
    }
    return sum;
}

如果您只能访问树结构中的节点：

int sumHeight(BinaryNode<?> node) {
    if (node == null) return 0;
    return height(node) + sumHeight(node.left) + sumHeight(node.right);
}

看看是否有可以在一次递归中进行计算的算法（也许是一些回溯算法？）会很有趣。

于 2012-07-13T13:18:10.107 回答
0

好的。我已经提出了一个解决方案。

a) 如果n == null返回0

b) 如果n.left == null && n.right == null返回0

c) 总高度为total height of left+ total height of right+the height of it self

  • 自身的高度是：

1）如果左侧较大，则左侧总高度减去左侧左侧总高度

2）如果右侧较大，则右侧总高度减去右侧右侧总高度

public int totalHeight() {
    return totalHeight(root);
}

private int totalHeight(BinaryNode<AnyType> n) {
    if (n == null)
        return 0;
    else if (n.left == null && n.right == null)
        return 0;
    else
        return totalHeight(n.left)
                + totalHeight(n.right)
                + (totalHeight(n.left) > totalHeight(n.right) ? totalHeight(n.left)
                        - (n.left == null ? 0 : totalHeight(n.left.left))
                        : totalHeight(n.right)
                                - (n.right == null ? 0
                                        : totalHeight(n.right.right))) + 1;
}
于 2012-07-16T15:12:02.643 回答
0

我假设您在插入期间没有更新高度。

解决方案：我会以一种无序的方式遍历树。所以我首先声明root.height=0。

然后说

BinaryNode right;
BinaryNode left;
BinaryNode parent;
static int level;
int height;


if(left!=null)
{
    left.height=left.parent.height+1;
    level=level+left.height;
    left.yourMethod();
}

if(right!=null)
{
    right.height= right.parent.height+1; 
    level=level+right.height;
    right.yourMethod();
}

因此，您现在将拥有存储所有高度的关卡。

替代方法可以是使用队列的广度优先搜索遍历，但答案是一样的。希望这可以帮助。

于 2013-08-16T23:56:49.680 回答
0

递归查找每个节点的高度并不断添加到静态变量。或者，您可以记住高度并存储在每个节点中，然后再进行一次递归以将它们相加。

递归应该返回节点 n 的高度，而不是子树中每个节点的总高度。

于 2012-07-13T10:03:59.263 回答
0

void addHeights(class tree* root, int depth, int& sum) { if(root) { addHeights(root->left, depth+1, sum);
addHeights(root->right, depth+1, sum); 总和 += 深度；} }

于 2015-07-08T20:50:22.243 回答
0 
public int sum(){
    return sum(root);
}
private int sum(BinaryNode <?> n){
    if(n == null)
        return 0;
    else
        return n.data + sum(n.left) + sum(n.right);

}

尽管我假设您将节点内的数据称为“数据”，但我需要更多数据来评估您的代码。

因此，如果节点为空，则表示您已到达树的末尾并返回 0。否则，它将获取数据并先向左然后向右遍历。每次递归时，它们都会被添加，直到没有更多的节点可以添加。

于 2015-09-12T11:51:59.130 回答
-1 
 private  int maxHeight(BinaryNode<AnyType> n) {
  if (n ! = null) return 0;
  int leftheight = maxHeight(n.left);
   int rightheight = maxHeight(n.right);
  return (leftheight > rightheight) ? leftheight + 1 : rightheight + 1;
}

到目前为止，你已经知道了4种情况来计算身高

本质是如果左孩子或右孩子存在，则继续向左或向右节点。如果存在，则返回 1。

计数功能在最后一条语句中。那就是要计算最大的高度。

主要课程是在方法工作时熟悉递归和编程堆栈。

于 2012-07-13T09:50:16.447 回答