二叉树计算高度

2017-03-18  本文已影响0人  王小宝wy

最近自己犯了一个愚蠢至极的错误,被问到如何计算一颗平衡二叉树的高度,居然一时没想起来,其实答案相当简单,用句老师们经常爱讲的话就是,这是道送分题啊,结果自己居然没把握住...(真恨不得弄死自己)

言归正传,如果知道一棵平衡树的元素数目m,则二叉树的高度为log2m,由此可写出代码

public class BinaryTreeNode<T> {
    public T element;

    public BinaryTreeNode<T> left, right;

    public BinaryTreeNode(T element) {
        this.element = element;
        this.left = null;
        this.right = null;
    }

    public int numChildren() {
        int childrenCount = 0;
        if (left != null) {
            childrenCount = 1 + left.numChildren();
        }

        if (right != null) {
            childrenCount = childrenCount + 1 + right.numChildren();
        }

        return childrenCount;
    }

    public int getHeight(int nodesNum) {
        return (int)(Math.log(nodesNum) / Math.log(2));
    }
}

上一篇下一篇

猜你喜欢

热点阅读