统计二叉树中结点个数的递归算法

题目

给出二叉树的二叉链表存储结构
并设计一个在链式存储结构上统计二叉树中结点个数的递归算法

代码

#include <iostream>
using namespace std;
typedef char ElemType;
//定义二叉树的链式存储
typedef struct TNode{
    ElemType data;
    struct TNode *lchild,*rchild;
}TNode,*BiTree;
//前序遍历创建二叉树
void createBiTree(BiTree &T){
    ElemType e;
    cin>>e;
    if(e=='#')
        T=NULL;
    else{
        T=(TNode *)malloc(sizeof(TNode));
        T->data=e;
        createBiTree(T->lchild);
        createBiTree(T->rchild);
    }
}
//打印输出二叉树
void dispBiTree(BiTree T){
    if(T==NULL)
        return;
    else{
        cout<<T->data<<" ";
        dispBiTree(T->lchild);
        dispBiTree(T->rchild);
    }
}
/**
* 算法主体
* 统计结点个数的递归算法
**/
int countTNode(BiTree T){
    if(T==NULL)
        return 0;
    else{
        return 1+countTNode(T->lchild)+countTNode(T->rchild);
    }
}
int main() {
    //ABD##EF###CG###
    BiTree T;
    createBiTree(T);
    dispBiTree(T);
    cout<<endl;
    cout<<"二叉树结点个数为："<<countTNode(T);

    return 0;
}

总结

该题目主要是要找到递归出口，当结点不为空时递归调用函数统计它的左右子树的结点个数，最终的结点个数是左右子树结点个数+1，因为还要包括子树的双亲的一个结点

最后

以上就是贤惠百合为你收集整理的统计二叉树中结点个数的递归算法的全部内容，希望文章能够帮你解决统计二叉树中结点个数的递归算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。