使用非递归方法Java的二叉树的大小 [英] Size of a binary tree with non recursive method Java

问题描述

您好，我正在尝试编写一种非递归方法来获取节点的大小，因为Java中的递归非常昂贵.这将包括子节点的数量+ 1(自身).我已经转换了C实现如何在Java中以非递归方式获取二叉树中的叶节点数量?，但这是不正确的.

Hello I'm trying to write a non recursive method for getting the size of a node since recursion in Java is expensive. This would include the number of child nodes + 1 (itself). I've converted an C implementation How can I get number of leaf nodes in binary tree non-recursively? in to Java but it's not correct.

非递归计算二进制树大小的算法.

algorithm for counting the size of binary tree, non recursively.

public int size(Node n) {
    Stack<Node> sizeStack = new Stack();
    int count = 1;//includes the n node
    if(n == null) {
        return 0;
    }
    sizeStack.push(n);
    while(!sizeStack.isEmpty()){
        node = sizeStack.pop();
        while(node != null) {
            count++;
            if(node.right != null){
                sizeStack.push(node.right);
            }
            node = node.left;
        }
    }
    return count;
}

推荐答案

您的算法正在计算叶子节点.您自己的愿望是计算所有个节点.用于计数叶节点的算法仅在弹出叶节点时才添加到计数器，这对于Java和C都是正确的.因此，实际上您的程序是好的-但不适用于您已定义的问题.

Your algorithm is counting leaf nodes. Your own wish was to count all the nodes. An algorithm for counting leaf nodes only adds to the counter when it pops a leaf node, and that's true both for Java and for C. So actually your program is good - but not for the problem you have defined.

为了计数所有节点，每次从堆栈中弹出节点时，都必须增加计数器.这意味着您必须推送所有节点，而不是像对待叶节点那样循环.

In order to count all the nodes, you have to increment the counter every time you pop a node from the stack. This means you have to push all the nodes, rather than loop the way you have for the leaf nodes.

如果您想节省推送操作(这是该算法优于递归的唯一原因，除非树向右不平衡)，您应该仅对要检查的每个节点增加计数器，但是保持基本循环不变.

If you want to save on push operations (which is the only reason why this algorithm will be better than recursion, unless the tree is unbalanced towards the right) you should just increment the counter for every node that you are examining, but keep the basic loop as it was.

public int size(Node n) {
    Stack<Node> sizeStack = new Stack();
    int count = 1;//includes the n node
    if(n == null) {
        return 0;
    }
    sizeStack.push(n);
    while(!sizeStack.isEmpty()){
        node = sizeStack.pop();
        while(node != null) {
            count++;
            if(node.right != null){
                sizeStack.push(node.right);
            }
            node = node.left;
        }
    }
    return count;
}

这篇关于使用非递归方法Java的二叉树的大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！