数据结构二叉树——统计二叉树的结点、深度、叶子结点个数
统计二叉树的结点、深度、叶子结点个数的结果总是等于1
#include
//visual studio 2010 c++
我引用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;
}
这段代码实现了二叉树的创建、遍历和统计节点数、深度、叶子节点个数等功能。但是在输出叶子节点及其个数时，存在一个问题，即每次递归时都会将n清零，导致最终输出的叶子节点个数总是等于1。下面是修改后的代码：
#include
#include
#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;
}
displeaf(T->lchild, n);
displeaf(T->rchild, n);
}
}
int main()
{
Queue Q;
initQueue(Q);
printf("请输入根节点的数据：");
Bitree T;
createlist(T);
enQueue(Q, T);
printf("先序遍历的结果： ");
XianXu(T);
printf("\
中序遍历的结果： ");
ZhongXu(T);
printf("\
后序遍历的结果： ");
HouXu(T);
printf("\
层次遍历的结果： ");
CengCi(T, Q);
printf("\
统计二叉树中结点的个数： %d", NodeCount(T));
printf("\
二叉树的深度： %d", depth(T));
printf("\
叶子节点及其个数： ");
int n = 0;
displeaf(T, n);
printf(" %d", n);
return 0;
}