按照教材中关于二叉树的抽象数据类型定义,采用二叉链表存储结构,编程实现二叉树的各种基本操作,并通过主函数调用,简单测试各基本函数的正确性。代码
时间: 2024-05-13 16:17:27 浏览: 75
以下是二叉树的基本操作的代码实现:
```c++
#include <iostream>
#include <queue>
using namespace std;
// 二叉树结点
template <typename T>
struct TreeNode {
T data;
TreeNode<T>* left;
TreeNode<T>* right;
TreeNode(T val) : data(val), left(NULL), right(NULL) {}
};
// 二叉树类
template <typename T>
class BinaryTree {
private:
TreeNode<T>* root; // 根结点
public:
// 构造函数
BinaryTree() : root(NULL) {}
// 析构函数
~BinaryTree() {
destroy(root);
}
// 销毁二叉树
void destroy(TreeNode<T>* node) {
if (node != NULL) {
destroy(node->left);
destroy(node->right);
delete node;
}
}
// 获取根结点
TreeNode<T>* getRoot() const {
return root;
}
// 创建二叉树
void create() {
if (root != NULL) {
return;
}
T val;
cout << "请输入根结点的值: ";
cin >> val;
root = new TreeNode<T>(val);
create(root);
}
// 前序遍历
void preOrder(TreeNode<T>* node) {
if (node != NULL) {
cout << node->data << " ";
preOrder(node->left);
preOrder(node->right);
}
}
// 中序遍历
void inOrder(TreeNode<T>* node) {
if (node != NULL) {
inOrder(node->left);
cout << node->data << " ";
inOrder(node->right);
}
}
// 后序遍历
void postOrder(TreeNode<T>* node) {
if (node != NULL) {
postOrder(node->left);
postOrder(node->right);
cout << node->data << " ";
}
}
// 层次遍历
void levelOrder(TreeNode<T>* node) {
queue<TreeNode<T>*> q;
if (node != NULL) {
q.push(node);
}
while (!q.empty()) {
TreeNode<T>* front = q.front();
q.pop();
cout << front->data << " ";
if (front->left != NULL) {
q.push(front->left);
}
if (front->right != NULL) {
q.push(front->right);
}
}
}
private:
// 创建二叉树
void create(TreeNode<T>* node) {
T val;
cout << "请输入 " << node->data << " 的左孩子的值: ";
cin >> val;
if (val != -1) {
node->left = new TreeNode<T>(val);
create(node->left);
}
cout << "请输入 " << node->data << " 的右孩子的值: ";
cin >> val;
if (val != -1) {
node->right = new TreeNode<T>(val);
create(node->right);
}
}
};
int main() {
BinaryTree<int> tree;
tree.create();
cout << "前序遍历: ";
tree.preOrder(tree.getRoot());
cout << endl;
cout << "中序遍历: ";
tree.inOrder(tree.getRoot());
cout << endl;
cout << "后序遍历: ";
tree.postOrder(tree.getRoot());
cout << endl;
cout << "层次遍历: ";
tree.levelOrder(tree.getRoot());
cout << endl;
return 0;
}
```
其中,为了方便起见,我们采用了模板类,可以存储任意类型的数据。在主函数中,我们首先调用 `create()` 函数创建二叉树,接着调用 `preOrder()`、`inOrder()`、`postOrder()` 和 `levelOrder()` 函数分别进行前序遍历、中序遍历、后序遍历和层次遍历,并输出结果。
阅读全文