任意の一本の二叉の木の茂み度を求めます.

「データ構造」の厳蔚敏版の練習問題でこの問題を見ました.繁茂度の定義:各階層のノード数の最大値と木の高さの積樹の深さが求められ、再帰的に呼び出せばいいです.各階層の最大ノードツリーはどうやって求められますか?以下は私の一つの実現方法です.

#include 
#include 
#include 
#include 
using namespace std;

typedef struct TNode
{
    int data;
    struct TNode* lchild;
    struct TNode* rchild;
}BiTree, *pBiTree;

void creat_tree(pBiTree &rt)
{
    char ch;
    ch=getchar();
    if('#'==ch)
    {
        rt=NULL;
    }
    else
    {
        rt=(pBiTree)malloc(sizeof(BiTree));
        rt->data=ch;
        creat_tree(rt->lchild);        //     
        creat_tree(rt->rchild);    //     
    }
}

void PreOrderPrint(pBiTree &rt)
{
    cout << "PreOrderPrint: ";
    if(!rt)
        return;
    stack s;
    s.push(rt);
    while(!s.empty())
    {
        pBiTree cur = s.top();
        cout << (char)(cur->data);
        s.pop();
        if(cur->rchild)
            s.push(cur->rchild);
        if(cur->lchild)
            s.push(cur->lchild);
    }
    cout << '@' << endl;
}

void InOrderPrint(pBiTree &rt)
{
    cout << "InOrderPrint: ";
    if(!rt)
        return;
    stack s;
    pBiTree cur = rt;

    while(!s.empty() || cur != NULL)
    {
        while(cur)
        {
            s.push(cur);
            cur = cur->lchild;
        }
        if(!s.empty())
        {
            cur = s.top();
            cout << (char)(cur->data);
            s.pop();
            cur = cur->rchild;
        }
    }
    cout << '@' << endl;
}

/*
        
*/
#include "bitree.h"
#include 

iint Prosperity(pBiTree &rt)
{
    if(!rt)
        return 0;

    queue q;
    pBiTree cur = rt;
    int now = 1;//current layer's node number
    int next = 2;//next layer's node number
    int i = 0;//loop counter
    int maxLevelNodes = 1; //max among every level's node
    int layers = 0; //Depth, i.e, layers

    q.push(cur);
    while(!q.empty())
    {
        cur = q.front();
        if(cur->lchild)
            q.push(cur->lchild);
        else
            next -= 1;
        if(cur->rchild)
            q.push(cur->rchild);
        else
            next -= 1;
        i++;
        q.pop();
        if(i == now)
        {
            layers++;//if i == now, means go over one layer
            now = next;// let now equals next layer's node number, start next loop
            next = now * 2;//ideally, next layer's node number has twice nodes of current
                            //"ideally" means each node has both lchild and rchild
                            //if some node is lack of one branch, the var next will minus by 1
                            //as shown above;
            i = 0;
            if(maxLevelNodes < now)
                maxLevelNodes = now;
        }
    }
    return maxLevelNodes * layers;
}

int main(int argc, char const *argv[])
{
    pBiTree root = NULL;
    creat_tree(root);
    PreOrderPrint(root);

    cout << "Prosperity: " << Prosperity(root) << endl;

    return 0;
}

層と関係があるので、自然に層順で巡る考え方を考えました.二叉の木が層順に遍歴されると、下の層の結点樹は上の層の二倍になります.では、上の階のある結点が一つの分岐点に欠けていると、下の層に一つの結点が足りなくなります.この点を十分に利用して、各層を巡回し終わった時に、次の層にいくつのノードがあるかを計算できます.そうすると、どの層の結点が一番多いかが分かります.nowは現在の層の接合点を保存しています.nextは次の層の接合点を格納します.(理想は二倍で、足りないものはマイナスすればいいです.)