设计一个读入一串整数,然后构造二叉排序树,进行查找。
时间: 2023-04-27 18:04:08 浏览: 326
这是一个程序设计问题,需要使用编程语言来实现。具体步骤如下:
1. 读入一串整数,可以使用数组或者链表来存储。
2. 构造二叉排序树,可以使用递归或者循环来实现。具体步骤如下:
a. 如果树为空,将第一个整数作为根节点。
b. 如果树不为空,将下一个整数插入到树中。比较当前节点的值和插入值的大小,如果插入值小于当前节点的值,则将插入值插入到当前节点的左子树中;如果插入值大于当前节点的值,则将插入值插入到当前节点的右子树中。
3. 进行查找,可以使用递归或者循环来实现。具体步骤如下:
a. 如果树为空,返回空。
b. 如果树不为空,比较当前节点的值和查找值的大小,如果查找值等于当前节点的值,则返回当前节点;如果查找值小于当前节点的值,则在当前节点的左子树中查找;如果查找值大于当前节点的值,则在当前节点的右子树中查找。
以上就是设计一个读入一串整数,然后构造二叉排序树,进行查找的基本步骤。
相关问题
实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作
以下是实现读入一串字符创建一棵二叉排序树,然后分别实现二叉排序树的查找、插入、删除等操作的Python代码:
```python
# 定义二叉排序树的节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 定义二叉排序树类
class BST:
def __init__(self):
self.root = None
# 插入节点
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
return
cur = self.root
while cur:
if val < cur.val:
if not cur.left:
cur.left = TreeNode(val)
return
cur = cur.left
else:
if not cur.right:
cur.right = TreeNode(val)
return
cur = cur.right
# 查找节点
def search(self, val):
cur = self.root
while cur:
if cur.val == val:
return True
elif cur.val > val:
cur = cur.left
else:
cur = cur.right
return False
# 删除节点
def delete(self, val):
def find_min(root):
while root.left:
root = root.left
return root
def delete_node(root, val):
if not root:
return None
if root.val == val:
if not root.left and not root.right:
return None
if not root.left:
return root.right
if not root.right:
return root.left
min_node = find_min(root.right)
root.val = min_node.val
root.right = delete_node(root.right, min_node.val)
elif root.val > val:
root.left = delete_node(root.left, val)
else:
root.right = delete_node(root.right, val)
return root
self.root = delete_node(self.root, val)
# 读入一串字符
s = input()
# 创建二叉排序树
bst = BST()
for c in s:
bst.insert(c)
# 查找节点
print(bst.search('a'))
# 插入节点
bst.insert('b')
# 删除节点
bst.delete('a')
```
首先编程实现读入一串字符创建一棵二叉排序树,然后分别实现:二叉排序树的查找;二叉排序树的插入;二叉排序树的删除等操作。C++写
以下是C++实现读入一串字符创建一棵二叉排序树,并实现二叉排序树的查找、插入、删除等操作的代码:
```cpp
#include <iostream>
using namespace std;
// 二叉排序树结点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 二叉排序树的查找
bool searchBST(TreeNode* root, int val) {
if (root == NULL) {
return false;
}
if (root->val == val) {
return true;
} else if (root->val > val) {
return searchBST(root->left, val);
} else {
return searchBST(root->right, val);
}
}
// 二叉排序树的插入
TreeNode* insertBST(TreeNode* root, int val) {
if (root == NULL) {
return new TreeNode(val);
}
if (root->val > val) {
root->left = insertBST(root->left, val);
} else {
root->right = insertBST(root->right, val);
}
return root;
}
// 二叉排序树的删除
TreeNode* deleteBST(TreeNode* root, int val) {
if (root == NULL) {
return NULL;
}
if (root->val == val) {
if (root->left == NULL) {
return root->right;
} else if (root->right == NULL) {
return root->left;
} else {
TreeNode* p = root->right;
while (p->left != NULL) {
p = p->left;
}
root->val = p->val;
root->right = deleteBST(root->right, p->val);
}
} else if (root->val > val) {
root->left = deleteBST(root->left, val);
} else {
root->right = deleteBST(root->right, val);
}
return root;
}
// 读入一串字符创建一棵二叉排序树
TreeNode* createBST() {
TreeNode* root = NULL;
int val;
while (cin >> val) {
root = insertBST(root, val);
}
return root;
}
int main() {
// 创建二叉排序树
TreeNode* root = createBST();
// 查找二叉排序树
int val1;
cout << "请输入要查找的值:";
cin >> val1;
if (searchBST(root, val1)) {
cout << "查找成功!" << endl;
} else {
cout << "查找失败!" << endl;
}
// 插入二叉排序树
int val2;
cout << "请输入要插入的值:";
cin >> val2;
root = insertBST(root, val2);
cout << "插入成功!" << endl;
// 删除二叉排序树
int val3;
cout << "请输入要删除的值:";
cin >> val3;
root = deleteBST(root, val3);
cout << "删除成功!" << endl;
return 0;
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)