网上有关“二叉树的高度和深度计算公式”话题很是火热，小编也是针对二叉树的高度和深度计算公式寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。
原题:
以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。
标准答案:
①求树的高度
思想:对非空二叉树，其深度等于左子树的最大深度加1。
Int
Depth(BinTree
*T)
{
int
dep1,dep2;
if(T==Null)
return(0);
else
{
dep1=Depth(T->lchild);
dep2=Depth(T->rchild);
if(dep1>dep2)
return(dep1+1);
else
return(dep2+1);
}
②求树的宽度
思想:按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
int
Width(BinTree
*T)
{
int
front=-1,rear=-1;/*
队列初始化*/
int
flag=0,count=0,p;
/*
p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值。*/if(T!=Null)
{
rear++;
q[rear]=T;
flag=1;
p=rear;
}
while(front<p)
{
front++;
T=q[front];
if(T->lchild!=Null)
{
rear++;
q[rear]=T->lchild;
count++;
}
if(T->rchild!=Null)
{
rear++;
q[rear]=T->rchild;
count++;
}
if(front==p)
/*
当前层已遍历完毕*/
{
if(flag<count)
flag=count;
count=0;
p=rear;
/*
p指向下一层最右边的结点*/
}
}
/*
endwhile*/
return(flag);
}
如何求二叉树深度
(1)n1=n-2n0+1
(2)n=n0+2^(k-1) -1
(3)n=2n0-1
二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。
怎么计算二叉树高度？
二叉树性质如下：
1 ：在二叉树的第i层上至少有2^（i-1）个结点
2：深度为k的二叉树至多有2^(k-1)个结点
3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
4：具有n个结点的完全二叉树的深度是log2n+1（向下取整）
5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1?i?n)，有：
如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是?i/2?
如果2i>n，则结点i无左孩子；如果2i?n，则其左孩子是2i
如果2i+1>n，则结点i无右孩子；如果2i+1?n，则其右孩子是2i+1
二叉树深度算法如下：
深度为m的满二叉树有2^m-1个结点；
具有n个结点的完全二叉树的深度为[log2n]+1.（log2n是以2为底n的对数）
分析二叉树的深度（高度）和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。
int Depth (BiTree T ){ // 返回二叉树的深度
if ( !T ) depthval = 0;
else {
depthLeft = Depth( T->lchild );
depthRight= Depth( T->rchild );
depthval = 1 + (depthLeft > depthRight ?
depthLeft : depthRight);
}
return depthval;
}
扩展资料：
一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。
二叉树的深度是从根节点开始（其深度为1）自顶向下逐层累加的；而二叉树高度是从叶节点开始（其高度为1）自底向上逐层累加的。虽然树的深度和高度一样，但是具体到树的某个节点，其深度和高度是不一样的。
百度百科—二叉树
关于“二叉树的高度和深度计算公式”这个话题的介绍，今天小编就给大家分享完了，如果对你有所帮助请保持对本站的关注！
本文来自作者[又蕊]投稿，不代表育友号立场，如若转载，请注明出处：https://m.jxydedu.cn/kepu/202512-823.html
评论列表（3条）
我是育友号的签约作者“又蕊”
本文概览：网上有关“二叉树的高度和深度计算公式”话题很是火热，小编也是针对二叉树的高度和深度计算公式寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您...
文章不错《二叉树的高度和深度计算公式》内容很有帮助