好的,以下是一个完整的二叉树功能代码,包括前序、中序、后序、层序的创建二叉树、遍历,销毁,输出方法
时间: 2024-05-11 19:18:36 浏览: 112
好的,以下是一个完整的二叉树功能代码,包括前序、中序、后序、层序的创建二叉树、遍历,销毁,输出方法。代码如下:
```cpp
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class BinaryTree {
public:
TreeNode* createTree() {
int x;
cin >> x;
if (x == -1) return NULL;
TreeNode* root = new TreeNode(x);
root->left = createTree();
root->right = createTree();
return root;
}
void preOrder(TreeNode* root) {
if (root == NULL) return;
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
void inOrder(TreeNode* root) {
if (root == NULL) return;
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
void postOrder(TreeNode* root) {
if (root == NULL) return;
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
void levelOrder(TreeNode* root) {
if (root == NULL) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
cout << endl;
}
}
void destroyTree(TreeNode* root) {
if (root == NULL) return;
destroyTree(root->left);
destroyTree(root->right);
delete root;
}
};
int main() {
BinaryTree bt;
TreeNode* root = bt.createTree();
cout << "Pre-Order: ";
bt.preOrder(root);
cout << endl;
cout << "In-Order: ";
bt.inOrder(root);
cout << endl;
cout << "Post-Order: ";
bt.postOrder(root);
cout << endl;
cout << "Level-Order: " << endl;
bt.levelOrder(root);
bt.destroyTree(root);
return 0;
}
```
在这个代码中,我们定义了一个 `TreeNode` 结构体,表示二叉树的节点。然后定义了一个 `BinaryTree` 类,包含了二叉树的创建、遍历、销毁、输出等方法。其中,创建方法使用递归的方式实现,遍历方法分别为前序、中序、后序和层序遍历,都使用递归和队列的方式实现。
在 `main` 函数中,我们首先通过 `createTree` 方法创建了一个二叉树,并打印了四种遍历方式的结果。最后,我们调用了 `destroyTree` 方法销毁了这个二叉树。
这个代码可以运行在 C++11 或更高版本的编译器上,如果需要在更低版本的编译器上运行,可以将 `TreeNode` 结构体中的初始化方式改为 `TreeNode(int x) { val = x; left = NULL; right = NULL; }`。
阅读全文