实验二 编写具体函数实现以下四种具体操作: (1)二叉排序树的递归查找 (2)二叉排序树的插入 (3)二叉排序树的创建 (4)二叉排序树的删除
时间: 2024-06-19 17:02:07 浏览: 16
好的,实验二主要是针对二叉排序树的相关操作进行编写,包括递归查找、插入、创建和删除四种具体操作。
1. 二叉排序树的递归查找:通过递归遍历二叉排序树,判断要查找的值是否等于当前节点的值,如果等于则返回该节点,否则判断要查找的值是在当前节点的左子树还是右子树,然后继续递归查找。
2. 二叉排序树的插入:从根节点开始遍历,找到要插入的位置,如果该位置为空,则新建一个节点并插入到该位置,否则继续遍历到下一层。
3. 二叉排序树的创建:通过读入一组数据,依次插入到二叉排序树中来创建一个二叉排序树。
4. 二叉排序树的删除:首先在二叉排序树中查找要删除的节点,如果该节点有两个子节点,则将其右子树中最小的节点(即右子树中最左边的节点)替换该节点,并将该节点删除。如果该节点只有一个子节点,则将该子节点替换该节点,并将该节点删除。如果该节点没有子节点,则直接删除该节点。
相关问题
编写程序实现二叉排序树的查找c语言
以下是一个简单的二叉排序树的查找程序,C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉排序树的节点结构体
struct BSTNode {
int data; // 节点的数据
struct BSTNode *left; // 左子树指针
struct BSTNode *right; // 右子树指针
};
// 创建一个新节点
struct BSTNode *createNode(int data) {
struct BSTNode *newNode = (struct BSTNode *)malloc(sizeof(struct BSTNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 将一个节点插入到二叉排序树中
void insertNode(struct BSTNode **root, int data) {
if (*root == NULL) {
*root = createNode(data);
return;
}
if (data < (*root)->data) {
insertNode(&((*root)->left), data);
} else if (data > (*root)->data) {
insertNode(&((*root)->right), data);
}
}
// 在二叉排序树中查找某个节点
struct BSTNode *findNode(struct BSTNode *root, int data) {
if (root == NULL) {
return NULL;
}
if (root->data == data) {
return root;
} else if (data < root->data) {
return findNode(root->left, data);
} else {
return findNode(root->right, data);
}
}
int main() {
struct BSTNode *root = NULL;
insertNode(&root, 50);
insertNode(&root, 30);
insertNode(&root, 70);
insertNode(&root, 20);
insertNode(&root, 40);
insertNode(&root, 60);
insertNode(&root, 80);
printf("Enter a value to search: ");
int value;
scanf("%d", &value);
struct BSTNode *result = findNode(root, value);
if (result == NULL) {
printf("Value not found\n");
} else {
printf("Value found: %d\n", result->data);
}
return 0;
}
```
在这个程序中,我们首先定义了一个二叉排序树的节点结构体 `BSTNode`,其中包含了节点的数据 `data`,以及左右子树的指针 `left` 和 `right`。
然后,我们实现了两个函数。`createNode` 函数用于创建一个新的节点,`insertNode` 函数用于将一个节点插入到二叉排序树中。这两个函数都是递归实现的。
最后,我们实现了 `findNode` 函数,用于在二叉排序树中查找某个节点。这个函数也是递归实现的。
在 `main` 函数中,我们首先创建了一个二叉排序树,并插入了一些节点。然后,从用户输入中读取一个值,调用 `findNode` 函数查找这个值是否在二叉排序树中存在。如果存在,就输出节点的数据;否则,输出“Value not found”。
编写二叉排序树的操作函数,并在main主函数中依次调用基本操作函数。①建立二叉排序树。②二叉排序树的插入。③二叉排序树的查找。④树的遍历。注意什么
好的,这是一个关于二叉排序树的问题。我会尽力回答你的问题。
首先,二叉排序树是一种特殊的二叉树,它的每个节点都包含一个关键字,且满足左子树的关键字都小于根节点的关键字,右子树的关键字都大于根节点的关键字。二叉排序树具有以下性质:
1. 对于二叉排序树中的任意节点,它的左子树中的所有节点的关键字都小于该节点的关键字,右子树中的所有节点的关键字都大于该节点的关键字;
2. 对于二叉排序树中的任意节点,它的左子树和右子树也是二叉排序树。
接下来,我们来分别实现建立二叉排序树、二叉排序树的插入、二叉排序树的查找和树的遍历。
建立二叉排序树的函数实现:
```
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* createBST(vector<int>& nums) {
if (nums.empty()) {
return NULL;
}
TreeNode* root = new TreeNode(nums[0]);
for (int i = 1; i < nums.size(); i++) {
TreeNode* cur = root;
while (cur) {
if (nums[i] < cur->val) {
if (cur->left) {
cur = cur->left;
} else {
cur->left = new TreeNode(nums[i]);
break;
}
} else {
if (cur->right) {
cur = cur->right;
} else {
cur->right = new TreeNode(nums[i]);
break;
}
}
}
}
return root;
}
```
二叉排序树的插入函数实现:
```
TreeNode* insertBST(TreeNode* root, int val) {
if (!root) {
return new TreeNode(val);
}
if (val < root->val) {
root->left = insertBST(root->left, val);
} else if (val > root->val) {
root->right = insertBST(root->right, val);
}
return root;
}
```
二叉排序树的查找函数实现:
```
bool searchBST(TreeNode* root, int val) {
if (!root) {
return false;
}
if (root->val == val) {
return true;
} else if (root->val > val) {
return searchBST(root->left, val);
} else {
return searchBST(root->right, val);
}
}
```
树的遍历函数实现:
```
void inorderTraversal(TreeNode* root) {
if (root) {
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
}
void preorderTraversal(TreeNode* root) {
if (root) {
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
void postorderTraversal(TreeNode* root) {
if (root) {
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
}
```
在 main 函数中调用这些函数:
```
int main() {
vector<int> nums = {5, 3, 7, 2, 4, 6, 8};
TreeNode* root = createBST(nums);
inorderTraversal(root);
cout << endl;
preorderTraversal(root);
cout << endl;
postorderTraversal(root);
cout << endl;
insertBST(root, 1);
inorderTraversal(root);
cout << endl;
insertBST(root, 9);
inorderTraversal(root);
cout << endl;
cout << searchBST(root, 4) << endl;
cout << searchBST(root, 10) << endl;
return 0;
}
```
需要注意以下几点:
1. 建立二叉排序树时,需要注意处理 nums 为空的情况。
2. 插入元素时,需要递归寻找插入位置。
3. 查找时,需要递归查找。
4. 遍历时,需要注意遍历顺序。
以上是关于二叉排序树的基本操作函数的实现和使用方法,希望能对你有所帮助。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)