我必须为二叉树实现递归方法,并想看看我编写的方法是否正确实现,因为我无法测试它们。这些不是实际的方法。我只需要编写算法的伪代码。
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)
}
}