设计算法并用c语言实现以下问题:⑴ 对给定的一组无序序列,建立一棵二叉排序树; ⑵ 对建立的二叉排序树实现查找操作。
时间: 2024-02-18 07:58:52 浏览: 100
以下是用C语言实现的算法:
```
#include<stdio.h>
#include<stdlib.h>
//定义二叉排序树节点
typedef struct BSTNode{
int data;
struct BSTNode *left;
struct BSTNode *right;
}BSTNode, *BSTree;
//创建新节点
BSTNode *createNode(int data){
BSTNode *newNode = (BSTNode*)malloc(sizeof(BSTNode));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
//插入节点
void insertNode(BSTree *root, int data){
if(!(*root)){ //如果根节点为空,直接插入
*root = createNode(data);
return;
}
if(data < (*root)->data) //如果插入的值小于当前节点的值,向左子树插入
insertNode(&((*root)->left), data);
else if(data > (*root)->data) //如果插入的值大于当前节点的值,向右子树插入
insertNode(&((*root)->right), data);
}
//查找节点
BSTNode *searchNode(BSTree root, int data){
if(!root) //如果当前节点为空,返回NULL
return NULL;
if(data == root->data) //如果当前节点的值与查找值相等,返回当前节点
return root;
else if(data < root->data) //如果查找值小于当前节点的值,向左子树查找
return searchNode(root->left, data);
else //如果查找值大于当前节点的值,向右子树查找
return searchNode(root->right, data);
}
//中序遍历二叉排序树
void inorderTraversal(BSTree root){
if(root){
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main(){
BSTree root = NULL;
int n, data, i;
printf("请输入序列长度:");
scanf("%d", &n);
printf("请输入无序序列:");
for(i = 0; i < n; ++i){
scanf("%d", &data);
insertNode(&root, data);
}
printf("中序遍历二叉排序树:");
inorderTraversal(root);
printf("\n");
printf("请输入要查找的值:");
scanf("%d", &data);
BSTNode *node = searchNode(root, data);
if(node)
printf("找到了!\n");
else
printf("没找到!\n");
return 0;
}
```
该算法首先定义了二叉排序树节点的结构体,包含节点的值和左右子节点指针。然后定义了创建新节点的函数,用于创建新的二叉排序树节点。接着定义了插入节点函数,用于向二叉排序树中插入新的节点。插入节点函数会先判断根节点是否为空,如果为空,则直接插入,如果不为空,则根据节点的值与当前节点的值的大小关系,向左子树或右子树插入新的节点。然后定义了查找节点函数,用于在二叉排序树中查找指定值的节点。查找节点函数会先判断当前节点是否为空,如果为空,则返回NULL,如果不为空,则根据查找值与当前节点的值的大小关系,向左子树或右子树查找节点。最后定义了中序遍历函数,用于中序遍历二叉排序树,并在主函数中调用上述函数,实现了对给定的一组无序序列建立一棵二叉排序树,并对建立的二叉排序树实现查找操作。
阅读全文