数据结构二叉树——统计二叉树的结点、深度、叶子结点个数

Question

统计二叉树的结点、深度、叶子结点个数的结果总是等于1

#include<stdio.h>
#include<stdlib.h>
#define maxQsize 15
typedef struct Tree
{
    char date;
    struct Tree *lchild;
    struct Tree *rchild;
}Bitnode,*Bitree;
void createlist(Bitree &T)
{
    char c;
    int n;
    scanf("%c",&c);
    n=getchar();
    if(c=='#')
        T=NULL;
    else
    {
        T=(Bitree)malloc(sizeof(Tree));
        T->date=c;
        printf("请输入%c的左子树：",T->date);
        createlist(T->lchild);
        printf("请输入%c的右子树：",T->date);
        createlist(T->rchild);
    }
}
typedef struct Queue
{
    Bitree *date;
    int front;
    int rear;
}Queue;
void initQueue(Queue &Q)
{
    Q.date=new Bitree[maxQsize];
    Q.front=Q.rear=0;
}
void enQueue(Queue &Q,Bitree &T)//入队
{
    if((Q.rear+1)%maxQsize==Q.front)
        return;
    Q.date[Q.rear]=T;
    Q.rear=(Q.rear+1)%maxQsize;
}
void deQueue(Queue &Q,Bitree &T)//出队
{
    if(Q.front==Q.rear)
        return;
    T=Q.date[Q.front];
    Q.front=(Q.front+1)%maxQsize;
}
//先序遍历
void XianXu(Bitree &T)
{
    if(T==NULL)
        return;
    printf("%c",T->date);
    XianXu(T->lchild);
    XianXu(T->rchild);
}
//中序遍历
void ZhongXu(Bitree &T)
{
    if(T==NULL)
        return;
    ZhongXu(T->lchild);
    printf("%c",T->date);
    ZhongXu(T->rchild);
}
//后序遍历
void HouXu(Bitree &T)
{
    if(T==NULL)
        return;
    HouXu(T->lchild);
    HouXu(T->rchild);
    printf("%c",T->date);
}
//层次遍历
void CengCi(Bitree &T,Queue &Q)
{
    while(Q.front!=Q.rear)//对列非空
    {
        deQueue(Q,T);//出队且返回给T
        printf("%c",T->date);
        if(T->lchild!=NULL)
            enQueue(Q,T->lchild);
        if(T->rchild!=NULL)
            enQueue(Q,T->rchild);
    }
}
//二叉树深度
int depth(Bitree &T)
{
    int numl,numr;
    if(T==NULL)
        return 0;
    else
    {
        numl=depth(T->lchild);
        numr=depth(T->rchild);
        if(numl>numr)
            return (numl+1);
        else
            return (numr+1);
    }
}
//统计二叉树中结点的个数
int NodeCount(Bitree T)
{
    if(T==NULL)
        return 0;
    else
        return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
//输出叶子节点及其个数
void displeaf(Bitree &T,int n)
{
    if(T==NULL)
        return;
    else
    {
        if(T->lchild==NULL&&T->rchild==NULL)
        {
            printf("%c",T->date);
            n+=1;
        }
        else{}
        displeaf(T->lchild,n);
        displeaf(T->rchild,n);
        printf("    %d",n);
    }
}
int main()
{
    Queue Q;
    initQueue(Q);
    printf("请输入根节点的数据：");
    Bitree T;
    createlist(T);
    enQueue(Q,T);
    printf("先序遍历的结果：  ");
    XianXu(T);
    printf("\n中序遍历的结果：  ");
    ZhongXu(T);
    printf("\n后序遍历的结果：  ");
    HouXu(T);
    printf("\n层次遍历的结果：  ");
    CengCi(T,Q);
    printf("\n统计二叉树中结点的个数：  %d",NodeCount(T));
    printf("\n二叉树的深度：  %d",depth(T));
    //printf("\n二叉树的总结点数：  ");
    printf("\n叶子节点及其个数：  ");
    displeaf(T,0);
    return 0;
}

//visual studio 2010 c++

Answer 1

我引用ChatGPT作答：
在你的代码中，统计二叉树的结点、深度和叶子结点个数的实现是正确的。然而，输出结果总是等于1的问题出现在 scanf("%c", &c) 这一行。这是由于在读取字符后，你需要读取输入缓冲区中的换行符。而换行符在 ASCII 码中是 10，而不是在 getchar() 函数中读入的整数，所以你需要调用 getchar() 一次来消耗输入缓冲区中的换行符。

以下是修改后的代码，注意到在读取 n 时，我使用了一个 getchar() 来消耗输入缓冲区中的换行符。

void createlist(Bitree &T)
{
    char c;
    int n;
    scanf("%c", &c);
    getchar(); // 读取并消耗换行符
    if (c == '#')
        T = NULL;
    else
    {
        T = (Bitree)malloc(sizeof(Tree));
        T->date = c;
        printf("请输入%c的左子树：", T->date);
        createlist(T->lchild);
        printf("请输入%c的右子树：", T->date);
        createlist(T->rchild);
    }
}

int main()
{
    // ...
    createlist(T);
    enQueue(Q, T);
    printf("先序遍历的结果：  ");
    XianXu(T);
    printf("\n中序遍历的结果：  ");
    ZhongXu(T);
    printf("\n后序遍历的结果：  ");
    HouXu(T);
    printf("\n层次遍历的结果：  ");
    CengCi(T, Q);
    printf("\n统计二叉树中结点的个数：  %d", NodeCount(T));
    printf("\n二叉树的深度：  %d", depth(T));
    printf("\n叶子节点及其个数：  ");
    displeaf(T, 0);
    return 0;
}