求二叉树深度的算法，求二叉树深度的公式

大家好，感谢邀请，今天来为大家分享一下求二叉树深度的算法的问题，以及和求二叉树深度的公式的一些困惑，大家要是还不太明白的话，也没有关系，因为接下来将为大家分享，希望可以帮助到大家，解决大家的问题，下面就开始吧！

完全二叉树结点深度计算公式

计算二叉树的深度：

满二叉树的深度为k=log2(n+1)

在完全二叉树中，具有n个结点的完全二叉树深度为(log2n)+1,其中(log2n)+1是向下取整。

计算完全二叉树深度公式-推导证明：

假设两种极端情况

<1>该树为满二叉树时，结点n1=2^k-1

此时k=log2(n1+1)

<2>当该树为满二叉树附加一个结点时，n2=2^(k-1),此时k=log2n2+1,

并且log2(n1+1)=log2n2+1

对任意结点n的完全二叉树，n2<=n<=n1

2^(k-1)<=n<=2^k-1

log2(n+1)<=k<=log2n+1

则k向下取整log2n+1

二叉树分支数计算

1.n个节点的二叉树一共有((2n)!)/(n!*(n+1)!)种

2.n层二叉树的第n层最多为2^(n-1)个

3.二叉树节点计算公式N=n0+n1+n2，度为0的叶子节点比度为2的节点数多一个。N=1*n1+2*n2+1

4.对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1

5.具有n个节点的完全二叉树的深度为log2(n)+1

6.B-树，除叶子与根节点以外的任意结点的分支数介于[m/2，m](取上整)

7.具有n个结点的完全二叉树的深度为[log2n]+1

8.树的高度：从根节点到所有叶节点中最大的边的数目。树的深度：从根节点到所有叶节点中最多的节点数目。

完全二叉树深度的公式

计算二叉树的深度：

满二叉树的深度为k=log2(n+1)

在完全二叉树中，具有n个结点的完全二叉树深度为(log2n)+1,其中(log2n)+1是向下取整。

计算完全二叉树深度公式-推导证明：

假设两种极端情况

<1>该树为满二叉树时，结点n1=2^k-1

此时k=log2(n1+1)

<2>当该树为满二叉树附加一个结点时，n2=2^(k-1),此时k=log2n2+1,

并且log2(n1+1)=log2n2+1

对任意结点n的完全二叉树，n2<=n<=n1

2^(k-1)<=n<=2^k-1

log2(n+1)<=k<=log2n+1

则k向下取整log2n+1

三层二叉树算法

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^（i?1）个结点;深度为k的二叉树至多有2^k?1个结点;对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。二叉树算法常被用于实现二叉查找树和二叉堆。

求助：二叉树的高度和深度有什么区别

不一样，高度是指节点到树叶（没有子节点的节点）的距离；深度是节点到根的距离。

OK，本文到此结束，希望对大家有所帮助。