摘自：数据结构——计算节点个数和二叉树高度（C语言版）
作者：正弦定理
发布时间：2020-12-12 23:27:09
网址：https://blog.csdn.net/chinesekobe/article/details/111086664
数据结构——计算节点个数、二叉树高度
一、计算各种节点
二叉树结构体如下：
// 二叉树结构体
typedef struct TreeLink{
int Data;
struct TreeLink *LChild;
struct TreeLink *RChild;
}T_LINK,*TLINK;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
（1）计算总节点：
让根节点指针开始，进行二叉树的遍历，遍历树节点中不为NULL下，及存在节点，遍历次数相加之和 + 根节点 及为总节点
// 计算二叉树总节点
int Calc_AllJieDian(TLINK p)
{
if(p == NULL) // 二叉树为空树 或者 该节点下没有子树
{
return 0;
}
return 1+Calc_AllJieDian(p->LChild)+Calc_AllJieDian(p->RChild); // 遍历该节点的左右子树，再加上根节点
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
（2）计算单分支节点：
遍历二叉树途中，只记录遍历树节点中遇到（左边子树存在，右边子树为NULL ）或者 （右边子树存在，左边子树为NULL）这种节点，才让递归 返回值 +1，依次累加
// 计算单分支节点
int Signal_Node(TLINK p)
{
if(p==NULL){
return 0;
// 当前节点左右子树其中一个为NULL，单支点数+1
}else if((p->LChild==NULL&&p->RChild!=NULL)||(p->LChild!=NULL&&p->RChild==NULL)){
return Signal_Node(p->LChild)+Signal_Node(p->RChild)+1;
}else{
// 双分支都存在，继续向下遍历
return Signal_Node(p->LChild)+Signal_Node(p->RChild);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
（3）计算双分支节点：
计算双分支节点思路 和 计算单支点相反 为： 遍历 二叉树 只记录 节点指针指向的节点中 左右子树都存在 的时候，递归返回值＋1，累加最后返回 就是双分支节点的个数
// 计算双分支节点
int Calc_DoubleNode(TLINK p)
{
if(p==NULL){
return 0;
}else if(p->LChild!=NULL&&p->RChild!=NULL){ // 当节点左右子树都存在时，双分支数+1
return Calc_DoubleNode(p->LChild)+Calc_DoubleNode(p->RChild)+1; // 继续遍历左右子树
}else{ // 否则只继续向下遍历左右子树
return Calc_DoubleNode(p->LChild)+Calc_DoubleNode(p->RChild);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
总代码:
#include<stdio.h>
#include<stdlib.h>
// 二叉树结构体
typedef struct TreeLink{
int Data;
struct TreeLink *LChild;
struct TreeLink *RChild;
}T_LINK,*TLINK;
// 创建二叉树
TLINK Create_TreeLink()
{
TLINK T;
int data;
int temp;
scanf("%d",&data);
temp = getchar(); // 吸收scanf带来的回车
if(data == -1){ // 输入-1表示该节点下左树或者右树下不存数据,返回到上一级节点
return NULL;
}else{
T = (TLINK)malloc(sizeof(T_LINK)); // 每个节点开辟空间
T->Data = data;
printf("请输入%d节点下左节点数据: ",data);
T->LChild = Create_TreeLink();
printf("请输入%d节点下右节点数据: ",data);
T->RChild = Create_TreeLink();
return T;
}
}
// 计算二叉树总节点
int Calc_AllJieDian(TLINK p)
{
if(p == NULL)
{
return 0;
}
return 1+Calc_AllJieDian(p->LChild)+Calc_AllJieDian(p->RChild); // 遍历该节点的左右子树，再加上根节点
}
// 计算双分支节点
int Calc_DoubleNode(TLINK p)
{
if(p==NULL){
return 0;
}else if(p->LChild!=NULL&&p->RChild!=NULL){ // 当节点左右子树都存在时，双分支数+1
return Calc_DoubleNode(p->LChild)+Calc_DoubleNode(p->RChild)+1; // 继续遍历左右子树
}else{ // 否则只继续向下遍历左右子树
return Calc_DoubleNode(p->LChild)+Calc_DoubleNode(p->RChild);
}
}
// 计算单分支节点
int Signal_Node(TLINK p)
{
if(p==NULL){
return 0;
// 当前节点左右子树其中一个为NULL，单支点数+1
}else if((p->LChild==NULL&&p->RChild!=NULL)||(p->LChild!=NULL&&p->RChild==NULL)){
return Signal_Node(p->LChild)+Signal_Node(p->RChild)+1;
}else{
// 双分支都存在，继续向下遍历
return Signal_Node(p->LChild)+Signal_Node(p->RChild);
}
}
int main()
{
TLINK T; // 创建二叉树指针
printf("输入第一个节点:\n");
T = Create_TreeLink();
int count = Calc_AllJieDian(T);
int SignalNode = Signal_Node(T);
int DoubleNode = Calc_DoubleNode(T);
printf("总节点个数为: %d\n",count);
printf("叶子节点个数为: %d\n",count-1);
printf("单支节点个数为: %d\n",SignalNode);
printf("双支节点个数为: %d\n",DoubleNode);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
运行结果：
二、计算二叉树高度
思路 ：
递归遍历二叉树，除去根节点下，比较节点左右子树的遍历次数大小，最后大的结果 加上 根节点 1 ，就是二叉树的高度
代码实现：
// 计算二叉树的高度
int Calc_Hight(TLINK p)
{
int left ; // 计算左子树 节点
int right; // 计算右子树节点
int Max;
if(p != NULL){
left = Calc_Hight(p->LChild); // 遍历该节点的左子树
right= Calc_Hight(p->RChild); // 遍历该节点的右子树
Max = left>right?left:right; // 比较左右子树的高度
return Max+1;
}else{
return 0;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22