求二叉树第k层结点的个数–c++【做题记录】
【问题描述】
求出二叉树的第K层结点个数。
【输入形式】
第一行输入扩展二叉树树的前序遍历序列
第二行输入k值,(k>0)。
【输出形式】
输出树的第K层结点个数。
【样例输入】
ab##cd##e##
2
【样例输出】
2
【样例说明】
上述输入对应以下结构的二叉树:
a
/
b c/
d e【提示】 上述例子中第二层只有b,c两个节点,因此输出第2层结点个数为2。 编程时可以利用层序遍历,当出队找到第一个符合k层的数据时,开始统计本层节点个数。
【代码】
#include
#include
#include
const int MAX=1000;
using namespace std;
struct BiNode
{
char data;//数据域
BiNode *lchild, *rchild;//左右儿子指针
};
class BiTree {
private:
BiNode *root;
public:
BiTree()
{
root=creat(root);
}
BiNode *creat(BiNode *bt);
void mirror(BiNode *bt);
void preOrder(BiNode * bt);
BiNode * getRoot(){return root;}
int getknode(BiNode *bt,int k);
};
BiNode *BiTree::creat(BiNode *bt)
{
char ch;
cin>>ch;
if(ch=='#')
bt=NULL;
else
{
bt=new BiNode;
bt->data=ch;
bt->lchild=creat(bt->lchild);
bt->rchild=creat(bt->rchild);
}
return bt;
}
/**前序遍历*/
void BiTree::preOrder(BiNode * bt)
{
if(bt==NULL)
return;
else{
cout<data;
preOrder(bt->lchild);
preOrder(bt->rchild);
}
}
// 求结点个数
int BiTree::getknode(BiNode *bt,int k)
{
if(bt==NULL||klchild,k-1)+getknode(bt->rchild,k-1);
// 先计算左子树第k-1层的结点个数,再计算右子树第k-1层结点个数,相加
}
int main()
{
BiTree tree;
int a,b;
cin>>a;
b=tree.getknode(tree.getRoot(),a);
cout<<b;
return 0;
}