【代码】求二叉树叶子结点的个数、递归方式 |
您所在的位置：网站首页 › 二叉树怎么计算叶子结点数 › 【代码】求二叉树叶子结点的个数、递归方式 |
【代码】求二叉树叶子结点的个数、递归方式
|
编写算法，求二叉树叶子结点的个数
题目分析：
求二叉树的叶子结点，就是求二叉树上左右孩子结点都是空的结点，还记得二叉树的三种遍历方式吗？前序遍历、中序遍历和后序遍历，在递归遍历算法中，无论采取哪种遍历方式，我们只需要添加一个条件就可以求得树的叶子结点啦
判断是否是叶子结点的条件是：
题中我采用的前序遍历，我们看代码吧 建立的二叉树形状：
注：此代码除《Domain.h》里面的算法之外，其余代码皆为二叉树的基本操作内容，若有不明白的地方可参考文章：树的基本操作 BiTree.h: #pragma once #include #include //结点的结构体 struct BiTreeNode { char data; //数据域 BiTreeNode *LeftChild; //左指针域 BiTreeNode *RightChild;//右指针域 }; typedef BiTreeNode DataType; //初始化 void initiate(BiTreeNode **root) { (*root) = (BiTreeNode*)malloc(sizeof(BiTreeNode)); (*root)->LeftChild = NULL; (*root)->RightChild = NULL; } //在结点的左孩子结点插入新的数据结点 BiTreeNode *LeftInsert(BiTreeNode *root, char data) { if (root == NULL) { printf("未找到当前结点，插入失败！\n"); return NULL; } BiTreeNode *q = (BiTreeNode*)malloc(sizeof(BiTreeNode)); q->data = data; q->RightChild = NULL; q->LeftChild = root->LeftChild; root->LeftChild = q; return q; } //在结点的右孩子结点插入新的数据结点 BiTreeNode *RightInsert(BiTreeNode *root, char data) { if (root == NULL) { printf("未找到当前结点，插入失败！\n"); return NULL; } BiTreeNode *q = (BiTreeNode*)malloc(sizeof(BiTreeNode)); q->data = data; q->LeftChild = NULL; q->RightChild = root->RightChild; root->RightChild = q; return q; } //访问数据域 void Visit(char data) { printf("%c ", data); } //二叉树的前序遍历 void PreOrder(BiTreeNode *root) { if (root != NULL) { Visit(root->data); PreOrder(root->LeftChild); PreOrder(root->RightChild); } } Domain.h: #pragma once #include"BiTree.h" /*求二叉树叶子结点个数，采用前序遍历*/ int NumOfLeff(DataType *root) { //采用static,每次进入函数的时候number不会被重新置0 static int number = 0; if (root != NULL) { /*判断为叶子结点的条件——没有左右孩子结点*/ if (root->LeftChild == NULL && root->RightChild == NULL) number++; NumOfLeff(root->LeftChild); NumOfLeff(root->RightChild); } return number; } main.c: #include"Domain.h" int main() { DataType *root,*p; initiate(&root); p = root; p = LeftInsert(p, 'A'); p = LeftInsert(p, 'B'); p = LeftInsert(p, 'D'); LeftInsert(p, 'H'); RightInsert(p, 'G'); p = RightInsert(root->LeftChild , 'C'); LeftInsert(p, 'E'); RightInsert(p, 'F'); //以上为创建一颗二叉树 printf("前序遍历：\n"); PreOrder(root->LeftChild); //测试叶子结点个数 printf("\n叶子结点个数："); printf("%d \n", NumOfLeff(root->LeftChild)); system("pause"); return 0; }有需要非递归解法的小伙伴私信我~ 代码编译器：Visual Studio 2017 ok |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |