「二叉树宽度java」二叉树宽度的定义
今天给各位分享二叉树宽度java的知识，其中也会对二叉树宽度的定义进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
二叉树宽度是什么?
宽度:节点的叶子数
深度:节点的层数
算法上有所谓的"宽度优先算法"和"深度优先算法"
二叉树的宽度定义为具有最多结点数的层中包含的结点数。
比如上图中，
第1层有1个节点，
第2层有2个节点，
第3层有4个节点，
第4层有1个节点，
可知，第3层的结点数最多
所以这棵二叉树的宽度就是4
java如何创建一颗二叉树
计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left
subtree）和“右子树”（right
subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的
i
-1次方个结点；深度为k的二叉树至多有2^(k)
-1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0
=
n2
+
1。
树是由一个或多个结点组成的有限集合，其中：
⒈必有一个特定的称为根(ROOT)的结点；
二叉树
⒉剩下的结点被分成n=0个互不相交的集合T1、T2、......Tn，而且，
这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。
树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树
1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为2;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
2.树的深度——组成该树各结点的最大层次。
3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；
4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。
树的表示
树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如右图可写成如下形式：
二叉树
(a(
b(d,e),
c(
f(
,g(h,i)
),
)))
编写计算二叉树最大宽度的算法
分析：二叉树是递归定义的，其计算二叉树的高度可以采取递归方式 int Height(btre bt)//求二叉树bt的深度{int hl,hr; if (bt= =NULL) return(0); else { hl=Height(bt-lch); hr=Height(bt-rch); if(hlhr) return (hl+1); else return(hr+1); } }分析：求二叉树的最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。int Width(BiTree bt)//求二叉树bt的最大宽度{if (bt==null) return (0); //空二叉树宽度为0 else {BiTree Q[]; //Q是队列，元素为二叉树结点指针，容量足够大front=1;rear=1;last=1;//front队头指针,rear队尾指针,last同层最右结点在队列中的位置 temp=0; maxw=0; //temp记局部宽度, maxw记最大宽度 Q[rear]=bt; //根结点入队列 while(front=last) {p=Q[front++]; temp++; //同层元素数加1 if (p-lchild!=null) Q[++rear]=p-lchild; //左子女入队if (p-rchild!=null) Q[++rear]=p-rchild; //右子女入队 if (frontlast) //一层结束， {last=rear; if(tempmaxw) maxw=temp; //last指向下层最右元素, 更新当前最大宽度 temp=0; }//if }//while return (maxw); }//结束width
二叉树的宽度是指什么？
一颗树只有一个节点，它的深度是1；
根节点只有左子树而没有右子树，那么二叉树的深度应该是其左子树的深度加1；
根节点只有右子树而没有左子树，那么二叉树的深度应该是其右树的深度加1；
根节点既有左子树又有右子树，那么二叉树的深度应该是其左右子树的深度较大值加1
二叉树的宽度算法如下：
宽度的定义：
二叉树的宽度定义为具有最多结点数的层中包含的结点数。
求解思路：
这里需要用到二叉树的层次遍历，即广度优先周游。在层次遍历的过程中，通过读取队列中保留的上一层的节点数来记录每层的节点数，以获取所有层中最大的节点数。
具体实现：
//求二叉树的宽度
int treeWidth(BinaryTreeNode *pRoot){
if (pRoot == NULL)
return 0;
int nLastLevelWidth = 0;//记录上一层的宽度
int nCurLevelWidth = 0;//记录当前层的宽度
queueBinaryTreeNode* myQueue;
myQueue.push(pRoot);//将根节点入队列
int nWidth = 1;//二叉树的宽度
nLastLevelWidth = 1;
BinaryTreeNode *pCur = NULL;
while (!myQueue.empty())//队列不空
{
while (nLastLevelWidth!= 0){
pCur = myQueue.front();//取出队列头元素
myQueue.pop();//将队列头元素出对
if (pCur-m_pLeft != NULL)
myQueue.push(pCur-m_pLeft);
if (pCur-m_pRight != NULL)
myQueue.push(pCur-m_pRight);
nLastLevelWidth--;
}
nCurLevelWidth = myQueue.size();
nWidth = nCurLevelWidth nWidth ? nCurLevelWidth : nWidth;
nLastLevelWidth = nCurLevelWidth;
}
return nWidth;
}
参考资料
二叉树的构造与遍历.csdn博客[引用时间2018-5-2]
二叉树宽度java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于二叉树宽度的定义、二叉树宽度java的信息别忘了在本站进行查找喔。