C++数据结构——统计二叉树的叶结点个数

统计二叉树的叶结点个数

根据带虚结点的先序序列建立二叉树，计算其叶子结点的数目后输出。

输入格式:

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

输出格式:

对于每组测试，输出所建立的二叉树的叶子结点数目。输出格式为：“leaf:num”，其中num 为二叉树的叶结点个数。

输入样例:
HDAC*BGFE**
-+axb-cd/ef
输出样例:
leaf:3
leaf:6

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

解题代码

#include<bits/stdc++.h>
using namespace std;
string str;
int len=0;

template<class T>
class Tree{
	public:
		
		Tree(){
			root=NULL;
		}
		struct treeNode{
			T data;
			treeNode *L_child,*R_child;
			treeNode(T d){
				data=d; 
			} 
		};
		treeNode *root;
		treeNode* createNode()
		{
			treeNode *t;
			if(len>=str.size()){
				return NULL;
			}
			T data = str[len++];
			if(data=='*'){
				t=NULL;
			}else{
				t=new treeNode(data);
				t->L_child=createNode();
				t->R_child=createNode(); 
			}
			return t;
			
		};
		int findLeaf(treeNode *root);
};

template<class T>
int Tree<T>::findLeaf(treeNode *root)
{
	int ans = 0;
	if(root==NULL) return 0;
	if(!root->L_child&&!root->R_child){
		return 1;
	}
	return ans+findLeaf(root->L_child)+findLeaf(root->R_child);
}



int main()
{
	while(cin>>str){
		len=0;
		Tree<char> *tree = new Tree<char>();
		tree->root=tree->createNode();
		cout<<"leaf:"<<tree->findLeaf(tree->root)<<endl;
	}
}

解题思路

就是按照先序遍历的顺序创建二叉树，这里的话HDAC*BGFE**
先序遍历，那么就是H是根节点，然后遇到D，因为是先序遍历，中-左-右，所有D在的左子树且为根节点，然后A在D的左子树，那么存入后，继续递归，然后后面遇到了*号证明A的左子树和右子树都为NULL，此时A遍历存储结束，返回D，D的左子树也遍历完了，那么C就是D的右子树，遇到星号，那么C的左子树是NULL，以此类推吧，这里的代码和前面那题很像，可以参考

https://blog.csdn.net/weixin_44546342/article/details/124576839?spm=1001.2014.3001.5502