C语言实现二叉树中统计叶子结点的个数&度为1&度为2的结点个数
2024-10-18 18:26:18
算法思想
统计二叉树中叶子结点的个数和度为1、度为2的结点个数，因此可以参照二叉树三种遍历算法（先序、中序、后序）中的任何一种去完成，只需将访问操作具体变为判断是否为叶子结点和度为1、度为2的结点及统计操作即可。
Code
#include <stdio.h>
#include <stdlib.h> int LeafCount=;
int Degree1Count=;
int Degree2Count=; typedef char DataType; //二叉链表结点的数据类型 typedef struct Node //定义二叉树的二叉链表结点结构
{
DataType data;
struct Node *LChild; //左子树
struct Node *RChild; //右子树
}BiTNode,*BiTree; void CreateBiTree(BiTree *bt); //创建二叉链表函数
void PreOrder(BiTree root); //先序遍历二叉树
void InOrder(BiTree root); //中序遍历二叉树
void PostOrder(BiTree root); //后序遍历二叉树
void Leaf(BiTree root); //统计叶子结点数目
void Degree1(BiTree root); //统计度为1的结点数目
void Degree2(BiTree root); //统计度为2的结点数目 int main()
{
BiTree bt;
int choice;
while(true)
{ //二叉树操作选择菜单
printf("*****************Please enter your choice*****************\n\n");
printf(" choice 1：创建二叉树\n");
printf(" choice 2：先序遍历二叉树\n");
printf(" choice 3：中序遍历二叉树\n");
printf(" choice 4：后序遍历二叉树\n");
printf(" choice 5：打印叶子结点数目\n");
printf(" choice 6：打印度为1的结点数目\n");
printf(" choice 7：打印度为2的结点数目\n");
printf(" choice 0：退出\n\n");
scanf("%d",&choice);
switch(choice)
{
case : CreateBiTree(&bt);
break;
case : PreOrder(bt);
printf("\n");
break; case : InOrder(bt);
printf("\n");
break;
case : PostOrder(bt);
printf("\n");
break;
case : Leaf(bt);
printf("该二叉树叶子结点的数目为：%d\n",LeafCount);
break;
case : Degree1(bt);
printf("该二叉树度为1的结点数目为：%d\n",Degree1Count);
break;
case : Degree2(bt);
printf("该二叉树度为2的结点数目为：%d\n",Degree2Count);
break;
case : exit();
break;
default:
printf("ERROR！！\n");
exit();
break;
}
}
return ;
} void CreateBiTree(BiTree *bt)
{
char ch;
printf("Please enter data:");
getchar();
ch = getchar();
if(ch == '.') //读入的数据是'.'则将当前树根置为空
{
*bt = NULL;
}
else //读入正常数据,为当前树根分配地址空间
{
*bt = (BiTree)malloc(sizeof(BiTNode));
(*bt)->data = ch;
CreateBiTree(&((*bt)->LChild)); //递归调用CreateBiTree()函数,处理左子树
CreateBiTree(&((*bt)->RChild)); //递归调用CreateBiTree()函数,处理右子树
}
} void PreOrder(BiTree root) //先序遍历二叉树,root为指向二叉树根结点的指针
{
if(root!=NULL)
{
printf("%c ",root->data); //访问根结点
PreOrder(root->LChild); //先序遍历左子树
PreOrder(root->RChild); //先序遍历右子树
}
} void InOrder(BiTree root) //中序遍历二叉树,root为指向二叉树根结点的指针
{
if(root!=NULL)
{
InOrder(root->LChild); //中序遍历左子树
printf("%c ",root->data); //访问根结点
InOrder(root->RChild); //中序遍历右子树
}
} void PostOrder(BiTree root) //中序遍历二叉树,root为指向二叉树根结点的指针
{
if(root!=NULL)
{
PostOrder(root->LChild); //后序遍历左子树
PostOrder(root->RChild); //后序遍历右子树
printf("%c ",root->data); //访问根结点
}
} void Leaf(BiTree root)
{
if(root!=NULL)
{
Leaf(root->LChild);
Leaf(root->RChild);
if(root->LChild==NULL && root->RChild==NULL)
{
LeafCount++; //统计叶子结点数目
}
}
} void Degree1(BiTree root)
{
if(root!=NULL)
{
Degree1(root->LChild);
Degree1(root->RChild);
if((root->LChild==NULL && root->RChild!=NULL)||(root->LChild!=NULL && root->RChild==NULL))
{
Degree1Count++; //统计度为1的结点数目
}
}
} void Degree2(BiTree root)
{
if(root!=NULL)
{
Degree2(root->LChild);
Degree2(root->RChild);
if(root->LChild!=NULL && root->RChild!=NULL)
{
Degree2Count++; //统计度为2的结点数目
}
}
}
最新文章
- Microsoft Loves Linux
- CSS3教程:box-sizing属性的理解
- TADOQuery学习总结
- 长时间停留在calculating requirements and dependencies 的解决方案
- CSS3 transform对普通元素的N多渲染影响
- CentOS7下安装JDK
- tomcat7.0 处理问题
- Winform跨线程操作界面的策略
- 【转】17种常用的JS正则表达式 非负浮点数 非负正数.
- linux开关机命令
- Udacity调试课笔记之断言异常
- 使用jsonEditor打造一个复杂json编辑器
- Dom4j和Xpath(转)
- php 基础篇 php 进阶篇
- Android之layout_weight属性详解
- Unity跨平台原理
- 华为OJ之自动售货系统
- PHP删除文件夹及其文件
- CF739E Gosha is hunting DP+wqs二分
- 重写&重载