C++数据结构——计算二叉树最大的宽度

计算二叉树最大的宽度

根据带虚结点的先序序列建立二叉树，计算该二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）并输出。

输入格式:

测试数据有多组，处理到文件尾。每组测试数据在一行中输入一个字符串（不含空格且长度不超过80），表示二叉树的先序遍历序列，其中字符*表示虚结点（对应的子树为空）。

输出格式:

对于每组测试，输出二叉树的最大宽度。输出格式为：“maxWidth: max”，其中max为二叉树的最大宽度值。

输入样例:
HDA**C*B**GF*E***
-+a**xb**-c**d**/e**f**
输出样例:
maxWidth: 3
maxWidth: 4

代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

解题代码

#include
using namespace std;
string str;
int len;
template<class T>
struct treeNode{
	T d;
	treeNode *L_child,*R_child;
};

template<class T>
class Tree{
	public:
		treeNode<T>* createNode();
		treeNode<T>* getRoot();
		void getDepth(stack< treeNode<T>* > s,int &num);
	private:
		treeNode<T> *root;
};

template<class T>
treeNode<T>* Tree<T>::createNode()
{
	if(len>=str.size()) return NULL;
	T d = str[len++];
	if(d=='*')return NULL;
	treeNode<T> *node = new treeNode<T>();
	node->d=d;
	node->L_child=createNode();
	node->R_child=createNode();
	return node;
}
template<class T>
treeNode<T>* Tree<T>::getRoot(){
	return this->root;
}
template<class T>
void Tree<T>::getDepth(stack< treeNode<T>* > s,int &num)
{
	stack< treeNode<T>* > s1;
	treeNode<T>* t;
	num=s.size()>num?s.size():num;
	while(!s.empty()){
		t=s.top();
		if(t->L_child!=NULL){
			s1.push(t->L_child);
		}
		if(t->R_child!=NULL){
			s1.push(t->R_child);
		}
		s.pop();
	}
	if(s1.size()==0){
		return;
	}
	getDepth(s1,num);
}
int main()
{
	int num;
	while(cin>>str){
		len=0;
		num=0;
		Tree<char> *tree = new Tree<char>();
		treeNode<char> *root =tree->getRoot();
		root = tree->createNode();
		stack<treeNode<char>* > s;
		s.push(root);
		tree->getDepth(s,num);
		cout<<"maxWidth: "<<num<<endl;
	}
}

解题思路

这里的创建树的思路是和之前的思路是一样的，用的是模板类，然后这里，要得到最大深度，意思就是算出每一层的结点数量，然后找到最大的结点数量。协议二哥getDepth函数，然后传递一个栈s，函数中新创建一个空栈s1，将栈s中的所有不为NULL的子结点放入s1中，然后继续递，直至栈空时不再进行递归。