二叉树节点数及叶子节点数
继续二叉树系列的代码内容。今天写的是求二叉树节点个数及叶子节点个数的代码。采用了递归的方法求解。
代码如下:
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
typedef struct BiTNode
{
char data;//树中节点的数据
struct BiTNode *lchild,*rchild;//节点的左孩子指针和右孩子指针
}BiTNode,*BiTree;//二叉树节点
//创建树
void CreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch == '#')
{
T = NULL;
return;
}
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
//计算树中的叶子节点数
int LeafCount(BiTree T)
{
if(NULL == T)
{
return 0;
}
else
{
if(NULL == T->lchild && NULL == T->rchild)
{
return 1;
}
else
{
return LeafCount(T->lchild) + LeafCount(T->rchild);
}
}
}
//树的节点个数
int Nodes(BiTree T)
{
if(NULL == T)
return 0;
else
{
if(NULL == T->lchild && NULL == T->rchild)
return 1;
else
{
return Nodes(T->lchild) + Nodes(T->rchild) + 1;
}
}
}
int main(int argc, char* argv[])
{
BiTree T = NULL;
CreateBiTree(T);
int leaf = LeafCount(T);
printf("BiTree leaf num is %d\n",leaf);
int nodes = Nodes(T);
printf("BiTree nodes is %d\n",nodes);
return 0;
}
构建的二叉树如下图:
运行结果如下图:
相对于第一天开始写代码,现在自己对于数据结构的定义,二叉树的创建已经很熟练了。现在写代码无需参考书中的伪代码,自己直接就可以写出来,虽然可能需要调试多次才能得到正确的结果,但相对于一周前的自己,现在的自己已经有很大进步了。毕竟一年多没有写过代码,没有看过相关的内容。虽然荒废了很多,但是我觉得捡起来是很快的,加油!