3005-基于二叉链表的二叉树最大宽度的计算（附思路，注释，可能错误分析）

abcd00e00f00ig00h00
abd00e00cf00g00
0

4
4

二叉树子树平均值的最大值。思路：

大思路：

为每个BNode节点另外设置一个level值  以记录当前节点在第几层，设置一个Floor数组来根据每个结点的level值记录每层都有几个节点，最后再遍历树，更新Floor[]的值，输出最大的即可。

细分：

SetLevel函数用来设置level值，全局变量lv初始化为1。一开始先让树的第一层level为1。遍历树，若当前节点存在且有左节点或右节点，那么就可以设置它的下一级层级。由于是设置下一层的层级，那么每次都要修正lv的值与当前节点的level一样（这句很重要！！因为若是不那么“平衡”的二叉树，就会出现有一个parent有两个child节点，其中只有一个叶子结点，则对这个叶子节点原本只用回退一次，却让lv++执行两次的情况）（调试出来的…具体情况忘记了qwq），调整好lv的值后再lv++，就是下一层级结点的值了！

代码：

#include <iostream>
using namespace std;
typedef struct BNode
{char data;int level;struct BNode* lchild, * rchild;
}*BTree, BNode;
int lv = 1;
int Floor[200];
void Create(BTree& bt, string s, int& i)//引用i！！！
{if (s[i] == '0')bt = NULL;else{bt = new BNode;bt->data = s[i];Create(bt->lchild, s, ++i);Create(bt->rchild, s, ++i);}
}
void Setlevel(BTree bt)
{if (bt)//当前节点非空{if (bt->lchild || bt->rchild)//既有左节点又有右节点{lv = bt->level;//这一步是为了防止叶子节点会走else语句两次，导致lv回退两次（本应该回退一次到上一层即可），而时刻让lv保持和当前节点相同的层级++lv;//预设下一层级的层数if (bt->lchild && bt->rchild)//左右节点都有，赋层级值{bt->lchild->level = lv;bt->rchild->level = lv;}else if (bt->lchild && !bt->rchild)//只有左节点bt->lchild->level = lv;else//只有右节点bt->rchild->level = lv;Setlevel(bt->lchild);//只有有叶子节点才接着设置呀，所以这两句写在这个if里面Setlevel(bt->rchild);}}
}
void Traverse(BTree bt)
{if (bt){Floor[bt->level]++;Traverse(bt->lchild);Traverse(bt->rchild);}
}
int main()
{string s;while (cin >> s && s != "0"){int i = -1;BTree b;Create(b, s, ++i);b->level = 1;//第一层层高肯定是1Setlevel(b);Traverse(b);int maxi = Floor[1];for (int i = 2; i < 200; i++){if (Floor[i] > maxi)maxi = Floor[i];if (Floor[i] == 0)break;}cout << maxi << endl;lv = 1;for (int i = 1; i < 200; i++){if (Floor[i] == 0)break;Floor[i] = 0;}}return 0;
}