数据结构——计算节点个数、二叉树高度
- 一、计算各种节点
-
- （1）计算总节点：
- （2）计算单分支节点：
- （3）计算双分支节点：
- 二、计算二叉树高度
-
- 代码实现：
一、计算各种节点
二叉树结构体如下：
// 二叉树结构体
typedef struct TreeLink{
int Data;
struct TreeLink *LChild;
struct TreeLink *RChild;
}T_LINK,*TLINK;
（1）计算总节点：
让根节点指针开始，进行二叉树的遍历，遍历树节点中不为NULL下，及存在节点，遍历次数相加之和 + 根节点 及为总节点
// 计算二叉树总节点
int Calc_AllJieDian(TLINK p)
{
if(p == NULL) // 二叉树为空树 或者 该节点下没有子树
{
return 0;
}
return 1+Calc_AllJieDian(p->LChild)+Calc_AllJieDian(p->RChild); // 遍历该节点的左右子树，再加上根节点
}
（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);
}
}
（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);
}
}
总代码:
#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 ，就是二叉树的高度
代码实现：
// 计算二叉树的高度
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;
}
}
</div>
