美文网首页
二叉树计算高度

二叉树计算高度

作者: 王小宝wy | 来源:发表于2017-03-18 22:05 被阅读0次

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

    言归正传,如果知道一棵平衡树的元素数目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));
        }
    }
    
    

    相关文章

      网友评论

          本文标题:二叉树计算高度

          本文链接:https://www.haomeiwen.com/subject/gkmpnttx.html