数据结构 | c++编程实现求二叉树的叶节点的个数。(递归非递归)

目录

非递归

递归

非递归

#include<iostream>
#include<stack>
using namespace std;
struct BTNode
{int data;BTNode* left, * right;BTNode(int val) :data(val), left(NULL), right(NULL) {}};
//递归的方式求二叉树的叶子结点数
int  countnode(BTNode* t)  //采用int类型而非bool类型 bool类型最后只有0和1
{if (t == NULL)return 0;stack<BTNode*>s1, s2; //两个栈一个存放临时节点，一个存放应经找到的叶子结点s1.push(t);  //将根节点放入栈中bool flag = false;  //用来标识有无叶子结点while (!s1.empty()){BTNode* node = s1.top();//取栈顶元素s1.pop();if (node->left == NULL && node->right == NULL){s2.push(node);flag = true; //有叶子结点 标识变true}else{if (node->left != NULL) //根节点的哪边不为空就把它塞到s1这个栈里面 {s1.push(node->left);}if (node->right != NULL){s1.push(node->right);}}}int count = 0;while (!s2.empty()){count++;s2.pop();}return flag ? count : 0;
}
int main()
{BTNode* root = new BTNode(1);root->left = new BTNode(2);root->right = new BTNode(3);root->left->left = new BTNode(4);root->left->right = new BTNode(5);root->right->left = new BTNode(6);root->right->right = new BTNode(7);cout << "叶子结点个数:" << countnode(root) << endl;return 0;
}

递归

#include<iostream>
#include<stack>
using namespace std;
struct BTNode
{int data;BTNode* left, * right;BTNode(int val):data(val),left(NULL),right(NULL){}};
//递归的方式求二叉树的叶子结点数int  countnode( BTNode* t)  //采用int类型而非bool类型 bool类型最后只有0和1
{if (t == NULL)return 0;if (t->left == NULL && t->right == NULL){return 1;}return (countnode(t->left) + countnode(t->right));  //递归调用函数求解根节点左孩子的叶子结点和右孩子的叶子结点
}
int main()
{BTNode* root = new BTNode(1);root->left = new BTNode(2);root->right = new BTNode(3);root->left->left = new BTNode(4);root->left->right = new BTNode(5);root->right->left = new BTNode(6);root->right->right = new BTNode(7);cout << "叶子结点个数:" << countnode(root) << endl;return 0;
}