C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

2024-02-23 21:03:02 182

/*求二叉树叶子节点个数--采用递归和非递归方法经调试可运行源码及分析如下： ***/ #include #include #include usingstd::cout; usingstd::cin; usingstd::endl; usingstd::stack; /*二叉树结点定义*/ typedefstructBTreeNode { charelem; structBTreeNode*pleft; structBTreeNode*pright; }BTreeNode; /* 求二叉树叶子节点数叶子节点：即没有左右子树的结点递归方式步骤：如果给定节点proot为NULL，则是空树，叶子节点为0，返回0；如果给定节点proot左右子树均为NULL，则是叶子节点，且叶子节点数为1，返回1；如果给定节点proot左右子树不都为NULL，则不是叶子节点，以proot为根节点的子树叶子节点数=proot左子树叶子节点数+proot右子树叶子节点数。 /*递归实现求叶子节点个数*/ intget_leaf_number(BTreeNode*proot) { if(proot==NULL) return0; if(proot->pleft==NULL&&proot->pright==NULL) return1; return(get_leaf_number(proot->pleft)+get_leaf_number(proot->pright)); } /*非递归：本例采用先序遍历计算判断当前访问的节点是不是叶子节点，然后对叶子节点求和即可。 **/ intpreorder_get_leaf_number(BTreeNode*proot) { if(proot==NULL) return0; intnum=0; stackst; while(proot!=NULL||!st.empty()) { while(proot!=NULL) { cout<<"节点："<elem<pleft; } if(!st.empty()) { proot=st.top(); st.pop(); if(proot->pleft==NULL&&proot->pright==NULL) num++; proot=proot->pright; } } returnnum; } /*初始化二叉树根节点*/ BTreeNode*btree_init(BTreeNode*&bt) { bt=NULL; returnbt; } /*先序创建二叉树*/ voidpre_crt_tree(BTreeNode*&bt) { charch; cin>>ch; if(ch=='#') { bt=NULL; } else { bt=newBTreeNode; bt->elem=ch; pre_crt_tree(bt->pleft); pre_crt_tree(bt->pright); } } intmain() { inttree_leaf_number=0; BTreeNode*bt; btree_init(bt);//初始化根节点 pre_crt_tree(bt);//创建二叉树 tree_leaf_number=get_leaf_number(bt);//递归 cout<<"二叉树叶子节点个数为:"<

希望本文所述对大家C++程序设计有所帮助。

C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

热门推荐

随机推荐