C++用二叉链表存储二叉树并用递归和非递归两种方式求叶子数的主函数的源代码
时间: 2024-02-12 16:06:03 浏览: 83
好的,以下是您需要的 C++ 代码:
```c++
#include<iostream>
#include<stack>
using namespace std;
// 定义二叉树结点
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 二叉树的类
class BinaryTree {
public:
// 构造函数
BinaryTree() {
root = NULL;
}
// 插入结点
void insertNode(int val) {
if (root == NULL) {
root = new TreeNode(val);
return;
}
TreeNode *p = root;
while (p) {
if (val < p->val) {
if (p->left == NULL) {
p->left = new TreeNode(val);
return;
} else {
p = p->left;
}
} else {
if (p->right == NULL) {
p->right = new TreeNode(val);
return;
} else {
p = p->right;
}
}
}
}
// 递归计算叶子结点数目
int countLeaf1() {
return countLeaf1(root);
}
// 非递归计算叶子结点数目
int countLeaf2() {
if (root == NULL) {
return 0;
}
stack<TreeNode*> s;
s.push(root);
int count = 0;
while (!s.empty()) {
TreeNode *p = s.top();
s.pop();
if (p->left == NULL && p->right == NULL) {
count++;
}
if (p->left) {
s.push(p->left);
}
if (p->right) {
s.push(p->right);
}
}
return count;
}
private:
// 计算以p为根的子树中叶子结点的个数
int countLeaf1(TreeNode *p) {
if (p == NULL) {
return 0;
}
if (p->left == NULL && p->right == NULL) {
return 1;
}
return countLeaf1(p->left) + countLeaf1(p->right);
}
// 根结点
TreeNode *root;
};
int main() {
BinaryTree bt;
bt.insertNode(5);
bt.insertNode(3);
bt.insertNode(7);
bt.insertNode(1);
bt.insertNode(4);
bt.insertNode(6);
bt.insertNode(8);
cout << "The number of leaf nodes (recursive): " << bt.countLeaf1() << endl;
cout << "The number of leaf nodes (non-recursive): " << bt.countLeaf2() << endl;
return 0;
}
```
在上述代码中,我们用二叉链表存储二叉树,定义了二叉树的结点结构体 `TreeNode`,并定义了二叉树的类 `BinaryTree`。其中,插入结点采用了二叉查找树的方式,递归和非递归的两种方式分别实现了计算叶子结点数目的函数 `countLeaf1` 和 `countLeaf2`。在主函数中,我们构建了一棵二叉查找树,并使用这两个函数分别计算了叶子结点的数目。
阅读全文