11-求树中节点的个数

7.3.1　求树中节点的个数

问题描述

已知二叉树采用二叉链表存储，要求编写算法，计算二叉树中度为0和度为1的节点个数。

【分析】

这是西北大学考研试题。

求二叉树中度为0的节点个数，即求叶子节点的个数，递归定义如下。

当二叉树为空时，其叶子节点个数为0。当二叉树只有一个根节点时，根节点就是叶子节点，叶子节点个数为1。其他情况下，计算左子树与右子树中叶子节点的和。

求二叉树中度为1的节点个数的递归定义如下。

当二叉树已空时，度为1的节点个数为0。当某个节点只有一个左子节点或右子节点时，则这个节点就是度为1的节点，再加上左右子树中度为1的节点个数就是这棵子树中度为1的节点个数。其他情况下，左右子树中度为1的节点个数之和就是这棵二叉树中度为1的节点个数。

/********************************************
*实例说明：求度为1和度为0的节点个数
*********************************************/
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include<iostream.h>
#define MAXSIZE 100
typedef char DataType;
typedef struct Node
{
    DataType data;
    struct Node   * lchild,*rchild;
}BitNode,*BiTree;
void TreePrint(BiTree T,int level);
BiTree CreateBitTree();
int Degrees1(BitNode *T);
int Degrees0(BitNode *T);
BiTree CreateBitTree()
/*利用先序输入方式创建二叉树*/
{
    DataType ch;
    BiTree bt;
    scanf("%c",&ch);
    if(ch=='#')
        bt=NULL;
    else
    {
        bt=(BitNode*)malloc(sizeof(BitNode));
        bt->data=ch;
        bt->lchild=CreateBitTree();
        bt->rchild=CreateBitTree();
    }
    return bt;
}
int Degrees1(BitNode *T)
//求二叉树中度为1的节点个数
{
    if(T==NULL)                   //空二叉树
        return 0;                 //度为1的节点个数为0
    if(T->lchild!=NULL && T->rchild==NULL || T->lchild==NULL && T->rchild!=NULL) 
    //若只有左子树或右子树
        return 1 + Degrees1(T->lchild) + Degrees1(T->rchild);
    //则该节点的度为1，求左子树和右子树中度为1的节点个数之和
    return  Degrees1(T->lchild) + Degrees1(T->rchild);//其他情况下求左右子树中度为1的节点
    //个数之和
}
int Degrees0(BiTree T)
/*求二叉树中度为0的节点个数*/
{
    if(!T)                           /*如果二叉树是空二叉树，返回0*/
        return 0;
    else
        if(!T->lchild&&!T->rchild)   /*如果左子树和右子树都已空，返回1*/
            return 1;
        else
            return Degrees0(T->lchild)+Degrees0(T->rchild);     /*把左子树的叶子节点个数  
            与右子树的叶子节点个数相加*/
}
void TreePrint(BiTree T,int level)
/*按树状输出的二叉树*/
{
    int i;
    if(T==NULL)                      /*如果指针已空，返回上一层*/
        return;
    TreePrint(T->rchild,level+1);    /*输出右子树，并将层次加1*/
    for(i=0;i<level;i++)             /*按照递归的层次输出空格*/
        cout<<"   ";
    cout<<T->data<<endl;             /*输出根节点*/
    TreePrint(T->lchild,level+1);    /*输出左子树，并将层次加1*/
}
void main()
{
    BiTree T;
    cout<<"请按照先序方式输入二叉树的节点："<<endl;
    T=CreateBitTree();
    cout<<"创建的二叉树："<<endl;
    TreePrint(T,1);
    cout<<"度为0的节点个数:"<<Degrees0(T)<<endl;
    cout<<"度为1的节点个数:"<<Degrees1(T)<<endl;
}

运行结果如图7.26所示。