Question

数据结构二叉树求结点个数问题

求二叉树第k层上的叶子结点数的程序。下面是创建二叉树的程序请按照这个编写，编出来的话100分送上
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode{
char data;
BiTNode *lchild,*rchild;
}BiTNode,*BiTtree;
void CreateTree(BiTtree &T)
{
char ch;
T=(BiTtree)malloc(sizeof(BiTNode));
if(!T)exit(0);
scanf("%c",&ch);
if(ch==' ')T=0;
else
{
T->data=ch;
CreateTree(T->lchild);
CreateTree(T->rchild);
}
}

Answer 1

#include <iostream>
#include <cstdlib>
#include <string>
#include <strstream>

using namespace std;

typedef struct BiTNode
{
char data;
BiTNode *lchild,*rchild;
}BiTNode,*BiTtree;

// 创建二叉树(中序遍历)
void CreateTree(BiTtree &T)
{
char ch;
T=(BiTtree)malloc(sizeof(BiTNode));
if(!T)
{
exit(0);
}
ch = getchar();
// 空节点或 结束符
if(ch==' ' || ch =='#')
{
T=NULL;
}
else
{
T->data=ch;
CreateTree(T->lchild);
CreateTree(T->rchild);
}
}
/*
返回二叉树 T 的高度
*/
int GetTreeHeight(BiTtree &T)
{
if(T == NULL)
{
return 0;
}
else
{
// 左子树的高
int leftTreeHeight = GetTreeHeight(T->lchild);
// 右子树的高
int rightTreeHeight = GetTreeHeight(T->rchild);
return (leftTreeHeight>rightTreeHeight)?(leftTreeHeight+1):(rightTreeHeight+1);
}
}

/*
求二叉树第 level 层上的叶子结点数

level 从 1 开始编号
返回 : 二叉树 T 的第 level 层上的叶子结点数
*/
int GetLBottomNodeOnTree(BiTtree &T,int level )
{
if(T == NULL)
{
return 0;
}
else if(level == 1)
{
if(T->lchild == NULL && T->rchild == NULL)
{
return 1;
}
else
{
return 0;
}
}
else
{
return GetLBottomNodeOnTree(T->lchild,level-1) + GetLBottomNodeOnTree(T->rchild,level-1);
}
}

/*
求二叉树上节点总数

返回 : 二叉树上节点总数
*/
int GetLTotalNodeOnTree(BiTtree &T)
{
if(T == NULL)
{
return 0;
}
else
{
return 1 + GetLTotalNodeOnTree(T->lchild) + GetLTotalNodeOnTree(T->rchild);
}
}

/*
求二叉树上叶子节点总数

返回 : 二叉树上叶子节点总数
*/
int GetLTotalBottomNodeOnTree(BiTtree &T)
{
if(T == NULL)
{
return 0;
}
else if(T->lchild == NULL && T->rchild == NULL)
{
return 1;
}
else
{
return GetLTotalBottomNodeOnTree(T->lchild) + GetLTotalBottomNodeOnTree(T->rchild);
}
}

/*
打印二叉树，并输出二叉树相关信息
T : 二叉树根节点
其余参数为递归打印二叉树参数，第一次调用使用有默认值，不用传入

二叉树图形说明：
A(root,1,F) ：A节点是根节点(root)， 在第 (1) 层 , 不是叶子节点(F)
B(L,2,T) ：B节点是左节点(Left)， 在第 (2) 层 , 是叶子节点(T)
C(R,2,F) ：C节点是右节点(Right)，在第 (1) 层 , 不是叶子节点(F)

*/
void PrintTree(BiTtree &T,int currentLevel=1,bool isLastNode = true,string prefixe="",string label="root")
{

if(T == NULL)
{
if(currentLevel == 1)
{
cout << "空树"<<endl;
}
else
{
return ;
}
}
else
{
if(currentLevel == 1)
{
cout
<< T->data
<< "("
<< label << ","
<< currentLevel << ","
<< ((T->lchild || T->rchild)==NULL?"T":"F")
<< ")"
<<endl;

PrintTree(T->lchild,currentLevel+1,T->rchild==NULL?true:false,"","L");
PrintTree(T->rchild,currentLevel+1,true,"","R");
}
else
{
if(isLastNode)
{
cout
<< (prefixe + "└─")
<< T->data
<< "("
<< label << ","
<< currentLevel << ","
<< ((T->lchild || T->rchild)==NULL?"T":"F")
<< ")"
<<endl;

PrintTree(T->lchild,currentLevel+1,T->rchild==NULL?true:false,(prefixe + " "),"L");
PrintTree(T->rchild,currentLevel+1,true,(prefixe + " "),"R");
}
else
{
cout
<< (prefixe + "├─")
<< T->data
<< "("
<< label << ","
<< currentLevel << ","
<< ((T->lchild || T->rchild)==NULL?"T":"F")
<< ")"
<<endl;

PrintTree(T->lchild,currentLevel+1,T->rchild==NULL?true:false,(prefixe + "│ "),"L");
PrintTree(T->rchild,currentLevel+1,true,(prefixe + "│ "),"R");
}
}

}
}

int main(int argc, char *argv[])
{
BiTtree T;
CreateTree(T);
cout << "二叉树高：" << GetTreeHeight(T) << endl;
cout << "二叉树总节点数：" << GetLTotalNodeOnTree(T) << endl;
cout << "二叉树叶子节点总数：" << GetLTotalBottomNodeOnTree(T) << endl;
cout<<"二叉树图形："<<endl;
PrintTree(T);
for(int level=1;level<=GetTreeHeight(T);level++)
{
cout << "第 " << level << " 层有 " << GetLBottomNodeOnTree(T,level) << " 个叶子节点！"<<endl;
}
return 0;
}
/*

测试数据：
AB CDFIKO PQ R S L EG H J M #
二叉树高：10
二叉树总节点数：18
二叉树叶子节点总数：6
二叉树图形：
A(root,1,F)
├─B(L,2,T)
└─C(R,2,F)
├─D(L,3,F)
│ └─F(L,4,F)
│ └─I(L,5,F)
│ ├─K(L,6,F)
│ │ ├─O(L,7,T)
│ │ └─P(R,7,F)
│ │ └─Q(L,8,F)
│ │ └─R(R,9,F)
│ │ └─S(R,10,T)
│ └─L(R,6,T)
└─E(R,3,F)
├─G(L,4,T)
└─H(R,4,F)
└─J(R,5,F)
└─M(R,6,T)
第 1 层有 0 个叶子节点！
第 2 层有 1 个叶子节点！
第 3 层有 0 个叶子节点！
第 4 层有 1 个叶子节点！
第 5 层有 0 个叶子节点！
第 6 层有 2 个叶子节点！
第 7 层有 1 个叶子节点！
第 8 层有 0 个叶子节点！
第 9 层有 0 个叶子节点！
第 10 层有 1 个叶子节点！

*/

Answer 2

按您的写法，写了一个查找统计函数，也是递归方式，只按层数查找。
int FindNodeForLayer(BiTtree &T,int layer)
{
if(T==NULL)
return 0;
if(layer==0)
{
if(T->lchild==NULL && T->rchild==NULL)
return 1;
else
return 0;
}
return (FindNodeForLayer(T->lchild,layer-1) + FindNodeForLayer(T->rchild,layer-1));
}

Answer 3

100分我不写,看楼下的