二叉树的每层结点数量如何输出

Question

#ifndef BITREE_H
#define BITREE_H

template<class T>
struct BiNode
{
    T data;
    BiNode<T> *lchild, *rchild;
};

template<class T>
class BiTree
{
public:
    BiTree();                //构造函数，建立一棵二叉树
    ~BiTree(void);           //析构函数，释放二叉树占用的存储空间
    BiNode<T> *Getroot();    //获得指向根节点的指针
    void PreOrder(BiNode<T> *root);     //前序遍历
    void InOrder(BiNode<T> *root);      //中序遍历
    void PostOrder(BiNode<T> *root);    //后序遍历
    int btheight(BiNode<T> *root,int height);        //二叉树的高度
    int countNode(BiNode<T> *root,int level,int& count);    //各层结点数
private:
    BiNode<T> *root;                  //根节点的头指针
    BiNode<T> *Creat();               //有参构造函数调用
    void Release(BiNode<T> *root);    //析构函数调用       
};

#endif

template<class T>
BiTree<T>::BiTree()
{
    this->root=Creat();
}

template<class T>
BiTree<T>::~BiTree(void)
{
    Release(root);
}

template<class T>
BiNode<T> *BiTree<T>::Getroot()
{
    return root;
}

template<class T>
void BiTree<T>::PreOrder(BiNode<T> *root)
{
    if(root==NULL)
        return;
    else
    {
        cout<<root->data<<" ";   //访问根节点
        PreOrder(root->lchild);  //前序遍历root的左子树
        PreOrder(root->rchild);  //前序遍历root的右子树
    }
}

template<class T>
void BiTree<T>::InOrder(BiNode<T> *root)
{
    if(root==NULL)
        return;
    else
    {
        InOrder(root->lchild);  //中序遍历root的左子树
        cout<<root->data<<" ";  //访问根节点
        InOrder(root->rchild);  //中序遍历root的右子树
    }
}

template<class T>
void BiTree<T>::PostOrder(BiNode<T> *root)
{
    if(root==NULL)
        return;
    else
    {
        PostOrder(root->lchild);  //后序遍历root的左子树
        PostOrder(root->rchild);  //后序遍历root的右子树
        cout<<root->data<<" ";    //访问根节点
    }
}

template<class T>
BiNode<T> *BiTree<T>::Creat()
{
    BiNode<T> *root;
    T ch;
    cin>>ch;
    if(ch=="#") root=NULL;
    else
    {
        root = new BiNode<T>;  //生成一个结点
        root->data=ch;
        root->lchild=Creat();  //递归建立左子树
        root->rchild=Creat();  //递归建立右子树
    }
    return root;
}

template<class T>
void BiTree<T>::Release(BiNode<T> *root)
{
    if(root != NULL)
    {
        Release(root->lchild);  //释放左子树
        Release(root->rchild);  //释放右子树
        delete root;
    }
}

template<class T>
int BiTree<T>::btheight(BiNode<T> *root,int height)
{
    
    if(root == NULL)
    {
        height=0;
        return 0;
    }
    int left;
        btheight(root->lchild,left);
        int right;
        btheight(root->rchild,right);
        height = left>right ? left+1:right+1;
}

template<class T>
int BiTree<T>::countNode(BiNode<T> *root,int level,int& count)
{
    if(!root || level<0)
        return 0;
    if(level == 0)
    {
        cout<<root->data<<" ";
        count++;
        return 1;
    }
    return countNode(root->lchild,level-1,count) + countNode(root->rchild,level-1,count);
}

void main()
{
    cout<<"请以先序遍历输入一棵二叉树的结点，空结点用 # 代替"<<endl;
    BiTree<string> bt;  //创建一棵树
    BiNode<string> *root = bt.Getroot();  //获得指向根节点的指针
    cout<<"前序遍历："<<endl;
    bt.PreOrder(root);
    cout<<endl;
    cout<<"中序遍历："<<endl;
    bt.InOrder(root);
    cout<<endl;
    cout<<"后序遍历："<<endl;
    bt.PostOrder(root);
    cout<<endl;
    int height=0;
    cout<<"二叉树的高度为："<<bt.btheight(root,height)<<endl;
    for(int i=0;i<height;i++)
    {
        int count = 0;
        bt.countNode(root,i,count);
        cout<<"结点个数为："<<count<<endl;}
    system("pause");
}

调试不出结果

Answer 1

对于你这个问题可以参考如下链接：

统计二叉树每层节点个数并打印每层节点_byf_study_alway的专栏-CSDN博客_统计二叉树每层节点个数 先看百度一道面试题：有一颗二叉树，定义树的高度为从根到叶子节点的最长距离，树的宽度为每层节点的最大值，树的面积定义为高度和宽度的乘积。写一个函数计算一个二叉树的面积。(15分)解决这道题参考资料剑指offer和编程之美，分别求求二叉树高度和宽度。都是采用递归：求高度参考：http://blog.csdn.net/buyingfei8888/article/details https://blog.csdn.net/buyingfei8888/article/details/38346057

如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!