二叉树的深度与什么有关？

一颗树只有一个节点，它的深度是1；

根节点只有左子树而没有右子树，那么二叉树的深度应该是其左子树的深度加1；

根节点只有右子树而没有左子树，那么二叉树的深度应该是其右树的深度加1；

根节点既有左子树又有右子树，那么二叉树的深度应该是其左右子树的深度较大值加1

二叉树的宽度算法如下：

宽度的定义：?

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

求解思路：?

这里需要用到二叉树的层次遍历，即广度优先周游。在层次遍历的过程中，通过读取队列中保留的上一层的节点数来记录每层的节点数，以获取所有层中最大的节点数。

具体实现：

//求二叉树的宽度 ?

int treeWidth(BinaryTreeNode *pRoot){ ?

if (pRoot == NULL)

return 0; ?

int nLastLevelWidth = 0;//记录上一层的宽度 ?

int nCurLevelWidth = 0;//记录当前层的宽度 ?

queue<BinaryTreeNode*> 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]