-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 回答