二叉排序树c++
时间: 2023-08-03 19:13:49 浏览: 47
下面是一个简单的二叉排序树的 C++ 实现:
```
#include <iostream>
using namespace std;
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
};
void insert(TreeNode*& node, int data) {
if (!node) {
node = new TreeNode{ data, nullptr, nullptr };
}
else if (data < node->data) {
insert(node->left, data);
}
else if (data > node->data) {
insert(node->right, data);
}
}
void inorder(TreeNode* node) {
if (node) {
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
}
void preorder(TreeNode* node) {
if (node) {
cout << node->data << " ";
preorder(node->left);
preorder(node->right);
}
}
void postorder(TreeNode* node) {
if (node) {
postorder(node->left);
postorder(node->right);
cout << node->data << " ";
}
}
int main() {
TreeNode* root = nullptr;
int arr[] = { 5, 3, 7, 1, 9, 4, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < n; i++) {
insert(root, arr[i]);
}
cout << "Inorder traversal: ";
inorder(root);
cout << endl;
cout << "Preorder traversal: ";
preorder(root);
cout << endl;
cout << "Postorder traversal: ";
postorder(root);
cout << endl;
return 0;
}
```
上面的代码实现了二叉排序树的插入和三种遍历方式(中序遍历、先序遍历和后序遍历)。在 `insert` 函数中,如果当前节点为空,就新建一个节点并把数据插入该节点;否则,根据数据大小递归向左或向右子树插入数据。
在 `main` 函数中,创建了一个二叉排序树并插入了一些数据。然后分别对该树进行了三种遍历,并输出结果。