求二叉树中的(叶子/单分支/双分支)结点个数
时间: 2023-08-09 10:12:34 浏览: 304
好的,针对你的问题,我来简单介绍一下:
二叉树是由结点(Node)组成的,每个结点最多有两个子节点(左子节点和右子节点)。根据子节点个数的不同,可以将二叉树的结点分为三类:叶子结点、单分支结点和双分支结点。
- 叶子结点:没有子节点的结点称为叶子结点,也称为终端结点。叶子结点是二叉树的最底层结点,它们没有子节点,只有父节点。叶子结点的个数就是二叉树的度为0的结点个数。
- 单分支结点:只有一个子节点的结点称为单分支结点,也称为度为1的结点。单分支结点的个数就是二叉树的度为1的结点个数。
- 双分支结点:同时拥有左右两个子节点的结点称为双分支结点,也称为度为2的结点。双分支结点的个数就是二叉树的度为2的结点个数。
需要注意的是,一个二叉树的总结点个数等于叶子结点个数加上单分支结点个数加上双分支结点个数。
希望这个回答能够帮到你!
相关问题
用c语言写份求二叉树中的(叶子/单分支/双分支)结点个数的代码
以下是用C语言实现求二叉树中叶子、单分支、双分支结点个数的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 结点结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 构造二叉树
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = createTree();
root->right = createTree();
return root;
}
// 计算叶子结点个数
int countLeafNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
// 计算单分支结点个数
int countSingleBranchNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 0;
}
if (root->left == NULL && root->right != NULL) {
return 1 + countSingleBranchNodes(root->right);
}
if (root->left != NULL && root->right == NULL) {
return 1 + countSingleBranchNodes(root->left);
}
return countSingleBranchNodes(root->left) + countSingleBranchNodes(root->right);
}
// 计算双分支结点个数
int countDoubleBranchNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 0;
}
if (root->left != NULL && root->right != NULL) {
return 1 + countDoubleBranchNodes(root->left) + countDoubleBranchNodes(root->right);
}
return countDoubleBranchNodes(root->left) + countDoubleBranchNodes(root->right);
}
int main() {
TreeNode* root = createTree();
printf("叶子结点个数:%d\n", countLeafNodes(root));
printf("单分支结点个数:%d\n", countSingleBranchNodes(root));
printf("双分支结点个数:%d\n", countDoubleBranchNodes(root));
return 0;
}
```
这里我们通过递归的方式来实现计算各种类型结点的个数。其中,countLeafNodes函数用来计算叶子结点个数,countSingleBranchNodes函数用来计算单分支结点个数,countDoubleBranchNodes函数用来计算双分支结点个数。在计算单分支结点和双分支结点的时候,我们通过判断结点的左右子树是否为空来进行区分。
二叉树双分支结点个数
二叉树的双分支结点个数是指具有左右孩子的结点个数。根据给出的算法思想,可以通过递归的方式来计算二叉树的双分支结点个数。算法的实现如下:
```c++
typedef struct BiTree{
char data;
BiTree *lchild;
BiTree *rchild;
}BiTree;
int DsonNodes(BiTree *T){
if(!T){
return 0;
}
if(T->rchild!=NULL && T->lchild!=NULL){ //若结点的左右孩子存在
return 1 + DsonNodes(T->rchild) + DsonNodes(T->lchild);
}
else{
return DsonNodes(T->rchild) + DsonNodes(T->lchild);
}
}
```
通过给定的测试数据,我们可以调用该函数来计算二叉树的双分支结点个数。例如:
```c++
char pre[13]={'#','A','B','D','F','H','J','M','N','C','E','K','G'};
char in[13]={'#','D','B','J','H','M','N','F','A','E','K','C','G'};
cout<<"The number of double-branch nodes is: "<<DsonNodes(PreInCreate(pre,in,1,12,1,12))<<endl;
```
这将输出二叉树的双分支结点个数。