【数据结构】计算二叉树的所有单,双分支结点个数,叶节点个数
·
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MaxSize 50
//算法思想:递归
//一棵树总的双分支结点数 = 左子树双分支结点数 + 右子树双分支结点数 + 1(如果T也是双分支结点)
//运用递归,求出树的左子树中双分支结点个数,再求出右子树中双分支结点个数
//再判断根结点是否是双分支结点
//是的话return 左 + 右 + 1, 不是的话return 左 + 右
void getDoubleBranch(BiTree T,int &count){
if(T->lchild && T->rchild) //如果是双分支结点
count++;
getDoubleBranch(T->lchild,count);
getDoubleBranch(T->rchild,count);
}
//求单分支结点个数
void getSingleBranch(BiTree T,int &count){
if(!T->lchild && T->rchild || T->lchild && !T->rchild)
count++;
getSingleBranch(T->lchild,count);
getSingleBranch(T->rchild,count);
}
//求一棵树的叶子结点数
void getLeafBranch(BiTree T,int &count){
if(!T->lchild && !T->rchild)
count++;
getLeafBranch(T->lchild,count);
getLeafBranch(T->rchild,count);
}
int getDoubleBranchByR(BiTree T){
if(!T)
return 0;
else if(T->lchild && T->rchild) //如果T为双分支结点
return getDoubleBranchByR(T->lchild) + getDoubleBranchByR(T->rchild) + 1;
else
return getDoubleBranchByR(T->lchild) + getDoubleBranchByR(T->rchild);
}
int getSingleBranchByR(BiTree T){
if(!T)
return 0;
else if(!T->lchild && T->rchild || T->lchild && !T->rchild)
return getSingleBranchByR(T->lchild) + getSingleBranchByR(T->rchild) +1;
else
return getSingleBranchByR(T->lchild) + getSingleBranchByR(T->rchild);
}
int getLeafBranchByR(BiTree T){
if(!T)
return 0;
else if(!T->lchild && !T->rchild)
return getLeafBranchByR(T->lchild) + getLeafBranchByR(T->rchild) + 1;
else
return getLeafBranchByR(T->lchild) + getLeafBranchByR(T->rchild);
}
更多推荐
所有评论(0)