JChe_ 2022-01-09 00:40 采纳率: 100%
浏览 50
已结题

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


#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");
}

调试不出结果

img

  • 写回答

1条回答 默认 最新

报告相同问题?

问题事件

  • 系统已结题 1月18日
  • 已采纳回答 1月10日
  • 创建了问题 1月9日

悬赏问题

  • ¥15 (有偿)懂数值分析和含时变参数微分方程的来
  • ¥15 layui父页的数据表格如何用弹窗页提交后的查询数据来更新数据表格内容?
  • ¥15 abaqus随机生成二维颗粒
  • ¥15 安装ansys许可证管理器时出现了这个问题,如何解决?
  • ¥100 高价求算法,利用智能手机传感器计算车辆的三轴g值
  • ¥15 Blazor server 数据库操作异常,如何解决?(语言-c#)
  • ¥15 uni-app开发APP运行到浏览器访问接口跨域
  • ¥100 mfc消息自创建控件
  • ¥15 网页视频跳过后学习进度未增加
  • ¥15 研究生初试录取系统设计的c++