C++代码要求:1、用模版类建立一个二叉树。 2、对建立的二叉树进行遍历。 3、求二叉树叶子数和深度等应用。
时间: 2023-06-18 22:06:58 浏览: 73
以下是符合您要求的C++代码:
```cpp
#include <iostream>
using namespace std;
template <typename T>
struct TreeNode {
T val;
TreeNode<T>* left;
TreeNode<T>* right;
TreeNode(T x) : val(x), left(nullptr), right(nullptr) {}
};
template <typename T>
class BinaryTree {
private:
TreeNode<T>* root;
int countLeaves(TreeNode<T>* node);
int maxDepth(TreeNode<T>* node);
void preorderTraversal(TreeNode<T>* node);
void inorderTraversal(TreeNode<T>* node);
void postorderTraversal(TreeNode<T>* node);
public:
BinaryTree() : root(nullptr) {}
void insert(T x);
int countLeaves();
int maxDepth();
void preorderTraversal();
void inorderTraversal();
void postorderTraversal();
};
template <typename T>
void BinaryTree<T>::insert(T x) {
TreeNode<T>* newNode = new TreeNode<T>(x);
if (root == nullptr) {
root = newNode;
} else {
TreeNode<T>* current = root;
while (current != nullptr) {
if (x < current->val) {
if (current->left == nullptr) {
current->left = newNode;
break;
} else {
current = current->left;
}
} else {
if (current->right == nullptr) {
current->right = newNode;
break;
} else {
current = current->right;
}
}
}
}
}
template <typename T>
int BinaryTree<T>::countLeaves(TreeNode<T>* node) {
if (node == nullptr) {
return 0;
} else if (node->left == nullptr && node->right == nullptr) {
return 1;
} else {
return countLeaves(node->left) + countLeaves(node->right);
}
}
template <typename T>
int BinaryTree<T>::countLeaves() {
return countLeaves(root);
}
template <typename T>
int BinaryTree<T>::maxDepth(TreeNode<T>* node) {
if (node == nullptr) {
return 0;
} else {
int leftDepth = maxDepth(node->left);
int rightDepth = maxDepth(node->right);
return max(leftDepth, rightDepth) + 1;
}
}
template <typename T>
int BinaryTree<T>::maxDepth() {
return maxDepth(root);
}
template <typename T>
void BinaryTree<T>::preorderTraversal(TreeNode<T>* node) {
if (node != nullptr) {
cout << node->val << " ";
preorderTraversal(node->left);
preorderTraversal(node->right);
}
}
template <typename T>
void BinaryTree<T>::preorderTraversal() {
preorderTraversal(root);
}
template <typename T>
void BinaryTree<T>::inorderTraversal(TreeNode<T>* node) {
if (node != nullptr) {
inorderTraversal(node->left);
cout << node->val << " ";
inorderTraversal(node->right);
}
}
template <typename T>
void BinaryTree<T>::inorderTraversal() {
inorderTraversal(root);
}
template <typename T>
void BinaryTree<T>::postorderTraversal(TreeNode<T>* node) {
if (node != nullptr) {
postorderTraversal(node->left);
postorderTraversal(node->right);
cout << node->val << " ";
}
}
template <typename T>
void BinaryTree<T>::postorderTraversal() {
postorderTraversal(root);
}
int main() {
BinaryTree<int> tree;
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(2);
tree.insert(4);
tree.insert(6);
tree.insert(8);
cout << "Preorder Traversal: ";
tree.preorderTraversal();
cout << endl;
cout << "Inorder Traversal: ";
tree.inorderTraversal();
cout << endl;
cout << "Postorder Traversal: ";
tree.postorderTraversal();
cout << endl;
cout << "Number of Leaves: " << tree.countLeaves() << endl;
cout << "Max Depth: " << tree.maxDepth() << endl;
return 0;
}
```
上述代码使用模版类实现了一个二叉树,并提供了以下功能:
- 插入节点:使用insert()方法向二叉树中插入一个节点。
- 遍历二叉树:使用preorderTraversal()、inorderTraversal()和postorderTraversal()方法分别进行先序、中序和后序遍历。
- 计算叶子数和深度:使用countLeaves()和maxDepth()方法分别计算二叉树的叶子数和深度。
在main()函数中,我们创建了一个整型的二叉树,并对其进行了遍历和计算叶子数和深度的操作。
阅读全文