求二叉树结点数和叶子结点数

二叉树的构建我就省略啦

#include <iostream>
#include <malloc.h>
#include <cstdio>
#include <queue>
typedef int Status;
using namespace std;

头文件用<queue>

Status allnodenum(BiTree &T)//求二叉树所有节点数
{
    if(!T)return 0;
    int l,r,num;
    l=allnodenum(T->lchild);
    r=allnodenum(T->rchild);
    num=l+r;
    num++;
    return num;
}

从叶子结点往上数,每个结点它的左子树和右子树结点数相加,再加上它本身,就是以该结点为根的树的结点数。

Status leafnodenum(BiTree &T)//叶子节点数
{
    int num=0;
    queue<BiTree> Q;
    if(!T)return error;
    Q.push(T);
    BiTree p=T;
    while(!Q.empty())
    {
        Q.pop();
        if(p->lchild==NULL&&p->rchild==NULL)num++;//左右子树都为空,即为叶子结点
        if(p->lchild)Q.push(p->lchild);
        if(p->rchild)Q.push(p->rchild);
        p=Q.front();
    }
    return num;
}//层序遍历改为求叶子结点数

刚开始是想着用上面求总结点数的方法求叶子结点数,想到一半就卡住了。

就用了<层序遍历>的方法,把所有结点都遍历一遍,如果它的左右孩子都为空,即为叶子结点,然后累加,求得叶子结点数。

    原文作者:Del_G
    原文地址: https://blog.csdn.net/Qinie_/article/details/80279904
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞