6-8 最宽层次结点数 分数 10

1.题目描述

2.本题ac答案

2.1法一: 代码复用

//二叉树第i层结点个数
int LevelNodeCount(BiTree T, int i)
{if (T == NULL || i < 1)return 0;if (i == 1) return 1;return LevelNodeCount(T->lchild, i - 1) + LevelNodeCount(T->rchild, i - 1);
}
int GetDepthOfBiTree(BiTree T)
{if (T == NULL)return 0;return GetDepthOfBiTree(T->lchild) > GetDepthOfBiTree(T->rchild) ? GetDepthOfBiTree(T->lchild) + 1: GetDepthOfBiTree(T->rchild) + 1;
}
int MaxWidth(BiTree T)
{int per = 0;int max = 0;for (int i = 1; i <= GetDepthOfBiTree(T); i++){per = LevelNodeCount(T, i);if (per > max)max = per;}return max;
}

2.2法二: 顺序队列实现层序遍历

int MaxWidth(BiTree T) 
{if (T == NULL)return 0;BiTree queue[100] = { 0 };BiTree cur = NULL;int begin = 0, end = 0;int perLevel = 0, max = 0;//每入队一个结点 end++表示有效数据加一queue[end++] = T;//begin != end: 队中还有结点 还未取到上一层所有结点的子结点while (begin != end){perLevel = end - begin;if (perLevel > max)max = perLevel;//cur指向队头结点 (马上就要被遗弃 因为已经被访问)//begin++表示当前结点已被遍历 当前结点被遗弃cur = queue[begin++];if (cur->lchild)queue[end++] = cur->lchild; if (cur->rchild)queue[end++] = cur->rchild;}return max;
}

3.C++层序遍历求最大宽度

3.1层序遍历代码

void LevelTraverse(BiTNode* T)
{if (T == nullptr)return;queue<struct BiTNode*> q;q.push(T);while (!q.empty()){BiTNode* front = q.front();cout << front->data;q.pop();if (front->lchild)q.push(front->lchild);if (front->rchild)q.push(front->rchild);}cout << endl;
}

3.2求最大宽度

typedef char ElemType;
typedef struct BiTNode
{ElemType data;struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
int MaxWidth(BiTree T)
{if (T == nullptr)return 0;queue<BiTree> q;q.push(T);int max = 0;while (!q.empty()){//当前层结点数int perLevel = q.size();  if (perLevel > max)max = perLevel;//for循环的作用://遍历当前栈中的结点 拿出一个结点node 把它的孩子入栈后就删除node//此时栈中存的结点是下一层结点for (int i = 0; i < perLevel; i++){BiTree front = q.front();q.pop();if (front->lchild) q.push(front->lchild);if (front->rchild)q.push(front->rchild);}}return max;
}