编写递归算法，求二叉树的结点个数和叶子数

Question

数据结构

Answer 1

00DLR(liuyu *root) /*中序遍历 递归函数*/
{if(root!=NULL)
{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%d\n",root->data);}
DLR(root->lchild);
DLR(root->rchild); }
return(0);
}
法二：
int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目
{
if(!T) return 0; //空树没有叶子
else if(!T->lchild&&!T->rchild) return 1; //叶子结点
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加
上右子树的叶子数
}//LeafCount_BiTree

注：上机时要先建树！例如实验二的方案一。
① 打印叶子结点值（并求总数）
思路：先建树，再从遍历过程中打印结点值并统计。本回答被网友采纳

Answer 2

写了个比较简单的，包括建立二叉树，还有你需要的递归函数，不懂可追问

#include <stdio.h>
#include <malloc.h>

#define CURRENT 0
#define LEFT 1
#define RIGHT 2

typedef struct BiTree
{
char data; //数据
BiTree* lchild; //左孩子节点
BiTree* rchild; //右孩子节点
BiTree* parent; //父节点
}BiTree;

void InitBiTree(BiTree* tree) //构造空二叉树
{
tree = NULL;
}

void CreateTree(BiTree* tree, char data) //给二叉树赋值
{
tree->data = data;
tree->parent = NULL;
tree->lchild = NULL;
tree->rchild = NULL;
}

int InsertChild(BiTree* tree, int pos, char data) //给孩子节点赋值
{
if (pos == LEFT)
{
if (tree->lchild != NULL)
{
printf("insert left child error!\n");
return false;
}
BiTree* t = (BiTree*)malloc(sizeof(BiTree));
tree->lchild = t;
t->data = data;
t->lchild = NULL;
t->rchild = NULL;
t->parent = tree;
return 1;
}
else if (pos == RIGHT)
{
if (tree->rchild != NULL)
{
printf("insert right child error!\n");
return 0;
}
BiTree* t = (BiTree*)malloc(sizeof(BiTree));
tree->rchild = t;
t->data = data;
t->lchild = NULL;
t->rchild = NULL;
t->parent = tree;
return 1;
}
return 0;
}

int PreOrderTraverse(BiTree* tree, int* countchildren, int* countleaves) // 递归函数
{
BiTree* p = tree;
if (p)
{
(*countchildren)++; // 如果那个节点有数据，就增加子节点数
int lnull, runll;
if (lnull = PreOrderTraverse(p->lchild, countchildren, countleaves))
{
if (runll = PreOrderTraverse(p->rchild, countchildren, countleaves))
{
if (lnull == -1 && runll == -1) // 如果左右节点都为空，则增加叶子节点数
{
(*countleaves)++;
}
return 1;
}
}
return 0;
}
else
{
return -1;
}
}

int main()
{
BiTree bt;
int countchildren = 0;
int countleaves = 0;
InitBiTree(&bt);
CreateTree(&bt, 's');
InsertChild(&bt, LEFT, 'i');
InsertChild(bt.lchild, LEFT, 'A');
InsertChild(bt.lchild->lchild, LEFT, 'x');
InsertChild(bt.lchild, RIGHT, 'B');
InsertChild(bt.lchild->rchild, RIGHT, 'y');
InsertChild(&bt, RIGHT, 'o');
PreOrderTraverse(&bt, &countchildren, &countleaves);
printf("countchildren : %d\n", countchildren);
printf("countleaves : %d\n", countleaves);
return 0;
}本回答被网友采纳

Answer 3

输入格式是怎么样的啊？追问

无论输出格式怎样都行·我只要算法

追答

#include"stdio.h"
const int MAX=1024;
int map[MAX][MAX]={0};
int countNodes(int r,int n)
{
int i,sum=0;
for(i=1;i<=n;i++)
{
if(map[r][i])//如果i是当前点的儿子，就去以i为根的子树里面的结点数统计上来
{
sum+=countNodes(i,n);
}
}
return sum+1;//总的子树结点数加上自己
}
int countLeaves(int r,int n)
{
int i,sum=0,son=0;//son保存当前点的儿子数目，如果son为0当前点就是叶子
for(i=1;i<=n;i++)
{
if(map[r][i])//如果i是当前点的儿子，就去以i为根的子树里面的叶子结点数统计上来
{
son++;
sum+=countLeaves(i,n);
}
}
if(son==0)return 1;//自己是叶子结点

return sum;
}
int main()
{
int n,a,b,i;
scanf("%d",&n);//输入树中结点数目
//假设1是根结点,结点从1到n编号
for(i=1;i<n;i++)//输入n-1条边
{
scanf("%d%d",&a,&b);//输入一对关系，表示a是b的父亲
map[a][b]=1;

}
printf("%d\n",countNodes(1,n));//数结点个数
printf("%d\n",countLeaves(1,n));//数叶子结点数
return 0;
}

追问

这是递归算法吗？

追答

是的啊，你看上面是不是递归函数啊