二叉排序树构造查找完整代码
时间: 2023-08-14 08:38:31 浏览: 55
下面是一个简单的二叉排序树的构造和查找的完整代码示例:
```c++
#include <iostream>
using namespace std;
// 二叉排序树的节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 向二叉排序树中插入一个节点
void insert(TreeNode* &root, int val) {
if (!root) {
root = new TreeNode(val);
return;
}
if (val < root->val) {
insert(root->left, val);
} else {
insert(root->right, val);
}
}
// 在二叉排序树中查找一个节点
bool search(TreeNode* root, int val) {
if (!root) {
return false;
}
if (val == root->val) {
return true;
} else if (val < root->val) {
return search(root->left, val);
} else {
return search(root->right, val);
}
}
int main() {
TreeNode* root = NULL;
insert(root, 5);
insert(root, 3);
insert(root, 7);
insert(root, 1);
insert(root, 4);
insert(root, 6);
insert(root, 8);
if (search(root, 4)) {
cout << "Found!" << endl;
} else {
cout << "Not found!" << endl;
}
if (search(root, 2)) {
cout << "Found!" << endl;
} else {
cout << "Not found!" << endl;
}
return 0;
}
```
这段代码中,我们定义了一个二叉排序树的节点结构体 `TreeNode`,包含一个整数值 `val`,以及左右子节点指针 `left` 和 `right`。我们还定义了两个函数:`insert` 用于向二叉排序树中插入一个节点,`search` 用于在二叉排序树中查找一个节点。在 `main` 函数中,我们创建了一个二叉排序树,并向其中插入一些节点,然后分别在其中查找一个存在的节点和一个不存在的节点。