二叉树宽度是什么?

我是初学者想要具体的定义！

热心网友 · 2018-4-30 02:34:22

宽度:节点的叶子数
深度:节点的层数

算法上有所谓的"宽度优先算法"和"深度优先算法"

二叉树的宽度定义为具有最多结点数的层中包含的结点数。
聽

聽

比如上图中，
第1层有1个节点，聽
第2层有2个节点，聽
第3层有4个节点，聽
第4层有1个节点，
可知，第3层的结点数最多
所以这棵二叉树的宽度就是4

infect · 2018-4-30 02:34:23

要求二叉树的宽度的话，则可根据树的高度设置一个数组temp。temp用于存放第i层上的结点数(即宽度)。在访问结点时,把相应计算该结点下一层的孩子数并存入相应数组元素中，遍历左子树后向上返回一层计算右子树的宽度，并取出最大的一个数组元素作为树的宽度。

#define M 10 //假设二叉树最多的层数
int Width(BinTree T)
{
int static n[M];//向量存放各层结点数
int static i=1;
int static max=0;//最大宽度
if(T)
{
if(i==1) //若是访问根结点
{
n++; //第1层加1
i++; //到第2层
if(T->lchild)//若有左孩子则该层加1
n++;
if(T->rchild)//若有右孩子则该层加1
n++;
}
else
{ //访问子树结点
i++; //下一层结点数
if(T->lchild)
n++;
if(T->rchild)
n++;
}
if(maxlchild);//遍历左子树
i--; //往上退一层
Width(T->rchild);//遍历右子树
}
return max;
}//算法结束

希望可以给你帮助！

请留言 · 2018-4-30 02:34:24

1：设置两个变量left,right。分别记录“以根节点为基准的偏离值”，再设置maxleft,和maxright记录遍历过程中遇到的最大值。
2：最后宽度就算两个值相加。

捡到的幸福 · 2018-4-30 02:34:25

首先画出二叉树的层次图
然后取个数最多的一层就是了

二叉树宽度是什么?

4 个回复