c++的二叉树算法实现
时间: 2023-08-06 17:08:39 浏览: 48
好的,下面是 C++ 的二叉树实现示例代码,包括二叉树的遍历和查找算法:
```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:
BinaryTree() : root(NULL) {}
void insert(int val) {
TreeNode* node = new TreeNode(val);
if (!root) {
root = node;
return;
}
TreeNode* curr = root;
while (true) {
if (val < curr->val) {
if (!curr->left) {
curr->left = node;
break;
}
curr = curr->left;
} else {
if (!curr->right) {
curr->right = node;
break;
}
curr = curr->right;
}
}
}
bool search(int val) {
TreeNode* curr = root;
while (curr) {
if (val == curr->val) {
return true;
} else if (val < curr->val) {
curr = curr->left;
} else {
curr = curr->right;
}
}
return false;
}
void preOrderTraversal() {
preOrderTraversal(root);
}
void inOrderTraversal() {
inOrderTraversal(root);
}
void postOrderTraversal() {
postOrderTraversal(root);
}
void levelOrderTraversal() {
if (!root) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
private:
TreeNode* root;
void preOrderTraversal(TreeNode* node) {
if (!node) return;
cout << node->val << " ";
preOrderTraversal(node->left);
preOrderTraversal(node->right);
}
void inOrderTraversal(TreeNode* node) {
if (!node) return;
inOrderTraversal(node->left);
cout << node->val << " ";
inOrderTraversal(node->right);
}
void postOrderTraversal(TreeNode* node) {
if (!node) return;
postOrderTraversal(node->left);
postOrderTraversal(node->right);
cout << node->val << " ";
}
};
int main() {
BinaryTree tree;
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(2);
tree.insert(4);
tree.insert(6);
tree.insert(8);
cout << "Pre-order traversal: ";
tree.preOrderTraversal();
cout << endl;
cout << "In-order traversal: ";
tree.inOrderTraversal();
cout << endl;
cout << "Post-order traversal: ";
tree.postOrderTraversal();
cout << endl;
cout << "Level-order traversal: ";
tree.levelOrderTraversal();
cout << endl;
cout << "Search 5: " << tree.search(5) << endl;
cout << "Search 9: " << tree.search(9) << endl;
return 0;
}
```
这个示例代码实现了二叉树的插入、查找、前序遍历、中序遍历、后序遍历和层序遍历算法。你可以根据自己的需要修改代码实现其他算法。