有没学做早餐的网站,wordpress 开源吗,上海工商网上公示系统,网站开发程序流程图文章目录 题目C代码详解 题目 在二叉树T中#xff0c;其度为1的结点是指某结点只有左孩子或只有右孩子。利用递归方法求二叉树T的度为1的结点个数。 1#xff09;如果TNULL#xff0c;则是空树#xff0c;度为1的结点个数为0#xff0c;返回值为0#xff1b; 2#xff0… 文章目录 题目C代码详解 题目 在二叉树T中其度为1的结点是指某结点只有左孩子或只有右孩子。利用递归方法求二叉树T的度为1的结点个数。 1如果TNULL则是空树度为1的结点个数为0返回值为0 2如果T-lchildNULL或T-rchildNULL注意左右孩子同时为NULL时则是叶子结点而不是度为1的结点则是度为1的结点返回值为1 3利用递归方法求其左右子树中的度为1的结点个数并输出二叉树T的度为1的结点个数。 函数接口定义 在这里描述函数接口。例如
int DegreeOne(BiTree T);裁判测试程序样例 裁判测试程序样例如下
#includestdio.h
#includestdlib.h
typedef struct node
{char data;struct node *lchild;struct node *rchild;
}BiNode, *BiTree;// 先序建立二叉树 输入时按先序次序输入二叉树中结点的值,以 # 字符表示空树
BiTree createBiTree()
{BiTree T;char c;scanf(%c, c);if (c #)T NULL;else{T (BiTree)malloc(sizeof(BiNode));T-data c;T-lchild createBiTree();//先序创建左子树T-rchild createBiTree();//先序创建右子树}return T;
}// 递归方法求二叉树中度为1的结点个数
/* 请在这里填写答案 */int main( ) {BiTree T createBiTree(); // 建立二叉树printf(%d\n,DegreeOne(T));return 0;
}输入样例1 在这里给出一组输入。例如 #输出样例1 在这里给出相应的输出。例如 0输入样例2 在这里给出一组输入。例如 ab###输出样例2 在这里给出相应的输出。例如 1输入样例3 在这里给出一组输入。例如 abc##de#g##f###输出样例3 在这里给出相应的输出。例如 2C代码 int DegreeOne(BiTree T){if(TNULL){return 0;}if(T-lchild ! NULL T-rchild ! NULL){//某结点有左右子树return DegreeOne(T-lchild)DegreeOne(T-rchild);}else if(T-lchild ! NULL T-rchild NULL){//某结点只有左子树return 1DegreeOne(T-lchild);}else if(T-lchild NULL T-rchild ! NULL){//某结点只有右子树return 1DegreeOne(T-rchild);}return 0;
}详解
这个问题要求使用递归方法求二叉树中度为1的结点个数。度为1的结点是指某结点只有左孩子或只有右孩子。
首先让我们来看看提供的C代码
int DegreeOne(BiTree T){if(TNULL){return 0;}if(T-lchild ! NULL T-rchild ! NULL){ // 某结点有左右子树return DegreeOne(T-lchild) DegreeOne(T-rchild);}else if(T-lchild ! NULL T-rchild NULL){ // 某结点只有左子树return 1 DegreeOne(T-lchild);}else if(T-lchild NULL T-rchild ! NULL){ // 某结点只有右子树return 1 DegreeOne(T-rchild);}return 0;
}现在让我们一步步解释这段代码
递归终止条件
如果传入的二叉树结点 T 为 NULL说明是空树度为1的结点个数为0返回值为0。
递归调用
如果某结点 T 有左右子树说明这是一个度为2的结点递归调用 DegreeOne 函数分别计算其左右子树中度为1的结点个数并将它们相加。
度为1的结点情况 如果某结点 T 只有左子树而没有右子树说明这是一个度为1的结点。递归调用 DegreeOne 函数计算其左子树中度为1的结点个数并在结果上加1。 如果某结点 T 只有右子树而没有左子树同样说明这是一个度为1的结点。递归调用 DegreeOne 函数计算其右子树中度为1的结点个数并在结果上加1。
返回结果
返回递归调用的结果即度为1的结点个数。
现在我们来分析一下以输入样例为例
abc##de#g##f###对应的二叉树结构如下 通过计算可以得到度为1的结点个数为2。这是因为结点 e 和结点 f 是度为1的结点。函数 DegreeOne 在这个例子中应该返回 2。
