wustoj(二叉树的繁荣度)

朱雀 2022-06-04 23:46 146阅读 0赞

问题描述:

（1）根据教材中算法6.4所示的算法，按照给出的先序序列建立二叉链表表示的二叉树（结点数不超过26）。

（2）计算该二叉树的繁茂程度。

一颗二叉树的繁茂程度为二叉树的宽度与高度的乘积，二叉树的宽度为各层节点数的最大值。

## Input ##

包含多组测试数据。每组测试数据一行，给出二叉树的先序遍历序列（至少1个结点）

## Output ##

输出二叉树的繁茂程度。

ABC^^DE^G^^F^^^
    A^^
    AB^^C^^

10
    1
    4

题目分析:求繁荣度，我们应该层次遍历二叉树，每一层的最大值就是宽度，层数就是高度。

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<string>
    #include<queue>
    #include<algorithm>
    using namespace std;
    
    string str;
    int cur,len,hight,wight;
    struct stree
    {
        char val;
        struct stree* lchild,*rchild;
    }*Tree;
    void build(struct stree* &T)
    {
        if (cur>=len) return ;
        if (str[cur]=='^') {
            T=NULL,cur++;return ;
        }
        else {
            T=new struct stree();
            T->val=str[cur];
            cur++;
            build(T->lchild);
            build(T->rchild);
        }
    }
    void floororder(struct stree* T)
    {
        queue<struct stree*> que1,que2;
        if (T==NULL) return ;
        que2.push(T);
        while (que2.size()) {
            hight++;
            int a=que2.size();
            wight=max(wight,a);
            while (que2.size()) {
                que1.push(que2.front());
                que2.pop();
            }
            while (que1.size()) {
                struct stree* T;
                T=que1.front();
                que1.pop();
                if (T->lchild!=NULL)
                    que2.push(T->lchild);
                if (T->rchild!=NULL)
                    que2.push(T->rchild);
            }
        }
    }
    int main()
    {
        while (cin>>str) {
            cur=0,len=str.size();
            build(Tree);
            hight=0,wight=0;
            floororder(Tree);
            cout<<wight*hight<<endl;
        }
        return 0;
    }