校园网站系统建设需求,编程软件scratch免费下载,应用软件下载大全,杭州建站平台摘自#xff1a;数据结构——计算节点个数和二叉树高度#xff08;C语言版#xff09; 作者#xff1a;正弦定理 发布时间#xff1a;2020-12-12 23:27:09 网址#xff1a;https://blog.csdn.net/chinesekobe/article/details/111086664 数据结构——计算节点个数、二叉树… 摘自数据结构——计算节点个数和二叉树高度C语言版 作者正弦定理 发布时间2020-12-12 23:27:09 网址https://blog.csdn.net/chinesekobe/article/details/111086664 数据结构——计算节点个数、二叉树高度 一、计算各种节点1计算总节点2计算单分支节点3计算双分支节点 二、计算二叉树高度代码实现 一、计算各种节点 二叉树结构体如下 // 二叉树结构体
typedef struct TreeLink{int Data;struct TreeLink *LChild;struct TreeLink *RChild;
}T_LINK,*TLINK; 1234567
1计算总节点 让根节点指针开始进行二叉树的遍历遍历树节点中不为NULL下及存在节点遍历次数相加之和 根节点 及为总节点 // 计算二叉树总节点
int Calc_AllJieDian(TLINK p)
{if(p NULL) // 二叉树为空树 或者 该节点下没有子树{return 0;}return 1Calc_AllJieDian(p-LChild)Calc_AllJieDian(p-RChild); // 遍历该节点的左右子树再加上根节点
}
12345678910
2计算单分支节点 遍历二叉树途中只记录遍历树节点中遇到左边子树存在右边子树为NULL 或者 右边子树存在左边子树为NULL这种节点才让递归 返回值 1依次累加 // 计算单分支节点
int Signal_Node(TLINK p)
{if(pNULL){return 0;// 当前节点左右子树其中一个为NULL单支点数1 }else if((p-LChildNULLp-RChild!NULL)||(p-LChild!NULLp-RChildNULL)){return Signal_Node(p-LChild)Signal_Node(p-RChild)1;}else{// 双分支都存在继续向下遍历 return Signal_Node(p-LChild)Signal_Node(p-RChild);}
}
1234567891011121314151617
3计算双分支节点 计算双分支节点思路 和 计算单支点相反 为 遍历 二叉树 只记录 节点指针指向的节点中 左右子树都存在 的时候递归返回值1累加最后返回 就是双分支节点的个数 // 计算双分支节点
int Calc_DoubleNode(TLINK p)
{ if(pNULL){return 0;}else if(p-LChild!NULLp-RChild!NULL){ // 当节点左右子树都存在时双分支数1return Calc_DoubleNode(p-LChild)Calc_DoubleNode(p-RChild)1; // 继续遍历左右子树 }else{ // 否则只继续向下遍历左右子树 return Calc_DoubleNode(p-LChild)Calc_DoubleNode(p-RChild);} }
123456789101112131415161718
总代码:
#includestdio.h
#includestdlib.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 1Calc_AllJieDian(p-LChild)Calc_AllJieDian(p-RChild); // 遍历该节点的左右子树再加上根节点
}
// 计算双分支节点
int Calc_DoubleNode(TLINK p)
{ if(pNULL){return 0;}else if(p-LChild!NULLp-RChild!NULL){ // 当节点左右子树都存在时双分支数1return 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(pNULL){return 0;// 当前节点左右子树其中一个为NULL单支点数1 }else if((p-LChildNULLp-RChild!NULL)||(p-LChild!NULLp-RChildNULL)){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); }123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
运行结果
二、计算二叉树高度
思路 递归遍历二叉树除去根节点下比较节点左右子树的遍历次数大小最后大的结果 加上 根节点 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 leftright?left:right; // 比较左右子树的高度return Max1; }else{return 0;}
}
12345678910111213141516171819202122
