数据结构算法设计——统计二叉树叶子结点的个数,并输出结果
发布网友
发布时间：2022-04-24 18:34
共4个回答
热心网友
时间：2023-11-01 23:10
代码如下：
#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreatTree(BiTree &A)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
{
A=NULL;
}
else
{
A=new BiTNode;
A->data=ch;
CreatTree(A->lchild);
CreatTree(A->rchild);
}
}
int NodeTree(BiTree A)
{
if(A==NULL)
return 0;
else if(A->lchild==NULL&&A->rchild==NULL)
return 1;
else
return NodeTree(A->lchild)+NodeTree(A->rchild);
}
int main()
{
BiTree A;
int b;
printf("先序法赋值（空用#表示）：");
CreatTree(A);
b=NodeTree(A);
printf("共有%d个叶子节点\n",b);
}
扩展资料
二叉树的性质
1、对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
2、有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则 如果I>1，则其父结点的编号为I/2；
如果2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*I>N，则无左孩子；
如果2*I+1<=N，则其右孩子的结点编号为2*I+1；若2*I+1>N，则无右孩子。
3、给定N个结点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。
4、设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i[2]
热心网友
时间：2023-11-01 23:10
#include <iostream.h>
#include <stdlib.h>
struct inform /*建立输入信息结构体inform*/
{ char data;
int l;
int r;
int signl; /*作为标记的signl,signr*/
int signr;
};
struct leafnode /*建立叶子节点结构体*/
{
char leaf;
leafnode* lchild;
leafnode* rchild;
};
void print(inform* ps, int n);
void judge ( inform* ps );
leafnode* creatree(); /*声明二叉树的建立函数*/
void preorder (leafnode* T); /*声明先序遍历函数*/
void inorder (leafnode* T); /*声明中序遍历函数*/
void postorder (leafnode* T); /*声明后序遍历函数*/
char a[100];
int k=1;
int s=0;
inform *p;
void main()
{
/*-------------------------------按格式输入信息-----------------------------------*/
int n;
cout<<"请输入二叉树内容：第一行为节点总数n ，后面的n行是节点的具体形式："<<endl;
cout<<"n= ";
cin>>n;
p=(inform* )malloc( n*sizeof(inform) ); /*开辟的一个叶子结构体型的指针数组*/
inform *p1; p1=p;
for(int i=0; i<n; i++)
{
cin>>(p+i)->data>>(p+i)->l>>(p+i)->r;
if((p+i)->l != -1) (p+i)->signl=1; /*用signl signr 的0，1标示输入的信息中是否有左或右孩子*/
else (p+i)->signl= 0;
if((p+i)->r !=-1) (p+i)->signr=1;
else (p+i)->signr= 0;
}
/*--------------------------------------------------------------------------------------------*/
a[0]= p->data;
judge ( p1 ); /*用递归算法将输入数据信息转为线性字符串*/
cout<<endl<<"输出转换的线性字符串： "<<endl;
cout<<a<<endl<<endl;
/*------------------------------------------遍历-----------------------------------*/
leafnode* T;
T= creatree();
/*先续遍历二叉树*/
cout<<"先序遍历二叉树： "<<endl;
preorder( T );
cout<<endl<<"中序遍历二叉树： "<<endl;
inorder ( T );
cout<<endl<<"后序遍历二叉树： "<<endl;
postorder( T );
cout<<endl<<endl;
}
/*------------------------------------------函数定义-------------------------------*/
void judge( inform* ps ) /*用函数的递归来将输入的信息转化为线性的数组*/
{
inform* b;
if (ps->signl==0)
{
a[k]='@';
k++;
}
else
{
b = p+(ps->l);
a[k] = b->data;
k++;
judge(b);
}
if ((ps->signr) == 0)
{
a[k]='@';
k++;
}
else
{
b = p+(ps->r );
a[k] = b->data;
k++;
judge(b);
}
}
leafnode* creatree() /*建立二叉树函数*/
{
char ch;
leafnode *t;
ch= a[s];
s++;
if(ch=='@')
{
t=NULL;
}
else
{
t=(leafnode* )malloc(sizeof(leafnode));
t->leaf=ch;
t->lchild=creatree();
t->rchild=creatree();
}
return t;
}
/*先序遍历的递归函数*/
void preorder (leafnode* T)
{
if(T)
{
cout<<T->leaf;
preorder(T->lchild);
preorder(T->rchild);
}
}
/*中序遍历的递归函数*/
void inorder (leafnode* T)
{
if(T)
{
inorder(T->lchild);
cout<<T->leaf;
inorder(T->rchild);
}
}
/*后序遍历的递归函数*/
void postorder (leafnode* T)
{
if(T)
{
postorder(T->lchild);
postorder(T->rchild);
cout<<T->leaf;
}
}
热心网友
时间：2023-11-01 23:11
热心网友
时间：2023-11-01 23:12
当x=NULL f(x)=0;
当x左右子树为空 f(x)=1;
其他 f(x)=f(bt->lchild)+f(bt-rchild)
-----------------------------------------------------------------------
int Count(BTreeNode *BT)
{
int l,r;
if(BT==NULL) return 0;
else if(BT->Lchild==NULL&&BT->Rchild==NULL) return 1;
else
{
l=Count(BT->Lchild);
r=Count(BT->Rchild);
return (l+r);
}
}
