Question

二叉树的第i层上至多有多少个结点

Answer 1

第一层为 1 2^0 ，第二层为 2 2^1 ，第三层为4 2^2 。 第n层为 2^(n-1) ，总节点数满足等比数列所以=a1(1-2^n)/(1-2)=2^n-1。

在二叉树中还有种特殊的二叉树就是完全二叉树：所有结点中除了叶子结点以外的结点都有两棵子树。如果完全二叉树中只有最底层为叶子结点那么又称为满二叉树。

n个节点（n>=2）的二叉树有 A[n] = ∑ [m=0到n-1] ( A[m]*A[n-m-1] ) ，求和的每一项，分别表示根的左子树为m个节点、右子树为 n-m-1个节点的情况。刚好就是catalan数，直接用catalan数的公式：h(n)=C(2n,n)/(n+1)

扩展资料：

类型

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

Answer 2

满二叉树的时候结点最多 2^（i-1），2^k-1

Answer 3

第一层为 1 2^0
第二层为 2 2^1
第三层为4 2^2
...
第n层为 2^(n-1) ,总节点数满足等比数列所以=a1(1-2^n)/(1-2)=2^n-1

Answer 4

根据二叉树性质1可知：

       在非空二叉树的第i层上至多有2^i-1(i≥1)个结点。