设计算法实现下列问题:⑴ 对给定的一组无序序列,建立一棵二叉排序树; ⑵ 对建立的二叉排序树实现查找操作。
时间: 2023-12-21 08:11:27 浏览: 108
分别对无序数组和有序数组建立二叉树,实现遍历和查找
5星 · 资源好评率100%
算法实现如下:
⑴ 对给定的一组无序序列,建立一棵二叉排序树:
1. 定义二叉排序树结构体,包含数据域和左右子节点指针;
2. 对于每个元素,从根节点开始遍历二叉排序树,如果节点为空则插入节点,否则比较元素大小,小于当前节点则往左子树递归,大于则往右子树递归,直到找到空节点插入为止;
3. 插入完成后,返回根节点即为建立的二叉排序树。
⑵ 对建立的二叉排序树实现查找操作:
1. 从根节点开始遍历二叉排序树,如果节点为空则返回 NULL;
2. 比较要查找的元素与当前节点的大小,小于当前节点则往左子树递归,大于则往右子树递归,等于则返回当前节点;
3. 如果遍历完整棵树都没有找到对应元素,则返回 NULL。
代码实现如下(C语言):
```c
// 定义二叉排序树结构体
typedef struct BSTNode {
int data;
struct BSTNode* left;
struct BSTNode* right;
} BSTNode;
// 插入元素到二叉排序树
BSTNode* insertBST(BSTNode* root, int data) {
if (root == NULL) {
// 如果节点为空则直接插入
root = (BSTNode*)malloc(sizeof(BSTNode));
root->data = data;
root->left = root->right = NULL;
} else if (data < root->data) {
// 如果比当前节点小则递归插入到左子树
root->left = insertBST(root->left, data);
} else if (data > root->data) {
// 如果比当前节点大则递归插入到右子树
root->right = insertBST(root->right, data);
}
// 返回当前节点
return root;
}
// 查找元素在二叉排序树中的节点
BSTNode* searchBST(BSTNode* root, int data) {
if (root == NULL || root->data == data) {
// 如果节点为空或者找到对应元素则返回当前节点
return root;
} else if (data < root->data) {
// 如果比当前节点小则递归查找左子树
return searchBST(root->left, data);
} else {
// 如果比当前节点大则递归查找右子树
return searchBST(root->right, data);
}
}
```
阅读全文