[原]统计一个二叉树的每一层 节点个数(队列,递归)

刘嘉辉 17/11/28 22:51:10

今天遇到一个问题就是利用队列求解二叉树的某一层的节点个数,乍一看感觉蛮简单,一上手让我有点头凉凉。

首先要解决的问题就是如何在队列中用标志来对二叉树进行分层,脑子里虽然有个大概的思路,弄几个循环,再来几个变量控制,也忒麻烦了。找了下博客也没看懂多少,高乐高还是给整出来了。思路如下。
emmmmm,我们不知道如何解决层的问题,再细分就是需要知道某一层有多少个,也就间接解决了层的问题。有点绕啊,不卖关子了,直接说了。
两个数,int curcount(来记录当前层的节点个数), int nextcount(来记录下一层的节点个数);
显然,curcount的初始值为1,因为只有一个根结点,而nextcount由于未知,故置为0.

void count_tree(Tnode *root,int level)//level 传进来的层数
{
    int  curcount=1,nextcount=0;//初始化当前节点个数,及下一行节点个数
    int count=1; //根节点所在层数为1
    Qlist *Q;   //队列
    Tnode *temp;
    Q = (Qlist *) malloc (sizeof(Qlist));
    Q->next = NULL;
    enqueue(Q,root);  //入队
    while(Q->next!= NULL){

        temp = dequeue(Q);  //出队
        curcount--;         //当前层节点个数减一

        if(temp->Lchild != NULL){//下一层有则加一个
            enqueue(Q,temp->Lchild);
            nextcount++;
        }
        if(temp->Rchild != NULL){//同上
            enqueue(Q,temp->Rchild);
            nextcount++;
        }
        if(curcount == 0){  //当 当前层的节点出完 队列中当前层节点剩余个数为0,是不是就转到下一层了 
            count++;  //层数加一
            if(level == count)
                printf("%d",nextcount);//输出节点个数
            curcount = nextcount; //赋值
            nextcount = 0; //下一层节点个数归零
        }
    }
}

再来个递归版的
递归啊就无脑递归就行了传个参数当当前的层数与所要求相同,个数加加。
代码如下

int COUNT_tree(Tnode *root, int depth, int k, int *number) {
    if (root == NULL)
        return 0;
    if (depth == k) {
        (*number)++;
    }
    COUNT(root->Lchild, depth + 1, k, number);
    COUNT(root->Rchild, depth + 1, k, number);
    return *number;
}
作者:Holy_666 发表于2017/11/28 22:51:10 原文链接
阅读:1 评论:0 查看评论