二叉树：度为2的结点个数、叶子结点的个数、结点的个数

文章目录

• • • • 度数为2的点
      • 叶子节点的个数
      • 结点的个数

度数为2的点

思路分析

• 通过函数的返回值来传递变量，从而获得最终的结果
• 首先，在当前结点不为空的情况下
  • 判定是否为度数为2的结点
  • 度数 = 左子结点的度数 + 右子结点的度数（采用递归的方式）
  • 全部递归完了，在返回最终的值

伪码

int BinaryTree::CountDegreeTwo( BinaryTreeNode *T ) const{
    int num = 0;
    if(T)
    {
        if(T->GetLChild() && T->GetRChild())
        {
            num = 1;
        }
        num = num + CountDegreeTwo(T->GetLChild()) + CountDegreeTwo(T->GetRChild())；
    }
    return num；
}

• 上述过程是递归完整个的过程之后的，最终的值已经彼此相互叠加，然后再将最终的值返回

叶子节点的个数

思路分析

• 通过函数的返回值来传递变量，从而获得最终的结果
• 首先，在当前结点不为空的情况下
  • 判定是否为叶子结点
    • 叶子节点已经在最底层了，直接返回值
    • 不是叶子节点，最终的结果为两个的左右两个子树的叶子结点之和，然后求和，直接返回值
  • 全部递归完了，在返回最终的值

实现伪码

int BinaryTree::CountDegreeZero( BinaryTreeNode *T ) const {
    int num = 0,numleft = 0,numright = 0;

   // cout<<"正在计数"<<endl;

    if(T) {
        //在判定当前的结点不为空的情况下
        if(!T->GetLChild() && !T->GetRChild()) {
            num = 1；
        }

        //递归往上进行叶子节点的相加
        else {
            numleft = CountDegreeZero(T->GetLChild())；
            numright = CountDegreeZero(T->GetRChild())；
            num = numleft + numright;           
        }
    }
    return num；

}

• 类似的题目思路是相同的，都是通过递归来实现的，前提都是该节点不为空的情况下。

结点的个数

思路分析

任意顺序完整的遍历一次，直接返回最终的结果

实现伪码

template<class ElemType>
int BinaryTree<ElemType>::BinaryTreeSize( BinaryTreeNode<ElemType> *T ) const {
    int num = 0,numleft = 0,numright = 0;
    if(T) {
        numleft = BinaryTreeSize(T->GetLChild());
        numright = BinaryTreeSize(T->GetRChild());
        num = numleft + numright + 1;
    }
    return num;
}