-1

我必须为二叉树实现递归方法，并想看看我编写的方法是否正确实现，因为我无法测试它们。这些不是实际的方法。我只需要编写算法的伪代码。

a) 计算树中的节点数

countNodes(TreeNode root){
    if(root == null)
        return 0;
    else{
        TreeNode left = root.getLeftChild();
        TreeNode right = root.getRightChild();
        return (countNodes(left)+countNodes(right)) + 1;
    }
}

b) 计算树的高度

height(TreeNode root){
    if(root == null)
        return 0;
    else{
        return Math.max(height(root.getLeftChild()), height(root.getRightChild()) +1;
    }
}

c) 找到最大元素

maxElem(TreeNode root){
    if(root == null)
        return 0;
    else{
        int temp = 0;
        temp = Math.max(maxElem(root.getLeftChild()), maxElem(root.getRightChild()));
        return Math.max(root.getValue, temp);
    }
}

d) 求元素之和

sum(TreeNode root){
    if(root == null)
        return 0;
    else{
        return (sum(root.getLeftChild()) + sum(root.getRightChild())) + root.getValue();
    }
}

e) 求元素的平均值

average(TreeNode root){
    int sum = sum(root);
    int elems = countNodes(root);
    return sum/elems;
}

f) 查找特定项目

search(int i, TreeNode root){
    if(root == null)
        return false;
    else if(root.getValue == i)
        return true;
    else{ 
        search(i, root.getLeftChild);
        search(i, root.getRightChild);
    }
}

g) 确定一个项目是否是另一个项目的祖先

isAncestor(TreeNode p, NodeNode c){
    if(p==null)
        return false;
    else
        return (c in p.getLeftChild() || c in p.getRightChild())
}

h) 确定已满的最高级别

maxFull(TreeNode root)
    if(root == null)
        return 0;
    else{
        return(numNodes in level h == 2^h - 1)
    }
}
4

3 回答 3

2

您的 MaxElm 方法是错误的。如果所有元素都有负值，它将不起作用。

于 2013-04-01T01:28:10.120 回答
1

有几个小问题：

1）asMTilsted 建议，如果您的树仅包含负值，则 maxElem 不起作用
2）平均值可能不正确，因为这是一个 int 而不是 double，请尝试对树元素的总和和计数进行类型转换，然后返回他们的商。
3）在您的函数搜索中，您不会在最后一个 else 语句中返回任何内容。试试：（return search(i, root.getLeftChild()) || search(i, root.getRightChild());在你的其余代码中，这些是函数而不是属性......

其余的似乎很好:)

于 2013-04-01T01:43:40.543 回答
0

我必须为二叉树实现递归方法，并想看看我编写的方法是否正确实现，因为我无法测试它们。这些不是实际的方法。我只需要编写算法的伪代码。

你可以测试它们。

用（比如说）Java 将它们写成真正的代码，编写一些单元测试，然后运行它们。

如果您在一天结束时必须提交的东西是伪代码而不是真正的代码，那么您可以手动将 Java 转换回伪代码......

严格来说，除非您指定了伪代码语言是/意味着什么，否则您不能说伪代码是否正确。

于 2013-04-01T01:34:28.367 回答