用C语言先依次输入元素为简单类型(int、char)或自定义结构体类型(如订单信息或学生信息或员工信息)的数个数据元素建立二叉链表存储的二叉排序树;然后在此二叉排序树上进行元素查找。
时间: 2024-03-18 11:40:19 浏览: 87
C语言实现数据结构 二叉排序树
好的,我可以帮你解答这个问题。
首先,我们需要定义二叉树的结点结构体,包括数据元素和左右孩子指针。对于简单类型的数据元素,我们可以直接用 int 或 char 类型定义,对于自定义结构体类型,我们需要先定义结构体。
以学生信息为例,我们可以定义如下的结构体:
```c
typedef struct student {
int id;
char name[20];
int age;
struct student *left;
struct student *right;
} Student;
```
接下来,我们可以编写函数来创建二叉排序树。对于每个输入的数据元素,我们先创建一个新的结点,然后将其插入到二叉排序树中。如果当前结点为空,说明该结点是树的根,直接将新结点插入即可;如果当前结点不为空,我们就比较新结点的数据元素和当前结点的数据元素的大小关系,如果小于当前结点的数据元素,就继续递归左子树,否则递归右子树,直到找到合适的位置。
下面是创建二叉排序树的代码实现:
```c
void insertNode(Student **root, int id, char *name, int age) {
Student *new_node = (Student *)malloc(sizeof(Student));
new_node->id = id;
strcpy(new_node->name, name);
new_node->age = age;
new_node->left = NULL;
new_node->right = NULL;
if (*root == NULL) {
*root = new_node;
return;
}
Student *p = *root;
while (p != NULL) {
if (id < p->id) {
if (p->left == NULL) {
p->left = new_node;
break;
} else {
p = p->left;
}
} else {
if (p->right == NULL) {
p->right = new_node;
break;
} else {
p = p->right;
}
}
}
}
```
接下来,我们可以编写函数来在二叉排序树中查找指定的数据元素。同样地,我们可以递归地比较当前结点的数据元素和目标数据元素的大小关系,如果相等,就返回当前结点;否则,如果目标数据元素小于当前结点的数据元素,就递归左子树,否则递归右子树。
下面是在二叉排序树中查找指定数据元素的代码实现:
```c
Student *searchNode(Student *root, int id) {
if (root == NULL) {
return NULL;
}
if (id == root->id) {
return root;
} else if (id < root->id) {
return searchNode(root->left, id);
} else {
return searchNode(root->right, id);
}
}
```
最后,我们可以编写一个 main 函数来测试我们的代码。在 main 函数中,我们可以先输入若干个学生信息,然后根据学生 ID 查找指定学生的信息。
下面是完整的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct student {
int id;
char name[20];
int age;
struct student *left;
struct student *right;
} Student;
void insertNode(Student **root, int id, char *name, int age) {
Student *new_node = (Student *)malloc(sizeof(Student));
new_node->id = id;
strcpy(new_node->name, name);
new_node->age = age;
new_node->left = NULL;
new_node->right = NULL;
if (*root == NULL) {
*root = new_node;
return;
}
Student *p = *root;
while (p != NULL) {
if (id < p->id) {
if (p->left == NULL) {
p->left = new_node;
break;
} else {
p = p->left;
}
} else {
if (p->right == NULL) {
p->right = new_node;
break;
} else {
p = p->right;
}
}
}
}
Student *searchNode(Student *root, int id) {
if (root == NULL) {
return NULL;
}
if (id == root->id) {
return root;
} else if (id < root->id) {
return searchNode(root->left, id);
} else {
return searchNode(root->right, id);
}
}
int main() {
Student *root = NULL;
// 输入学生信息
insertNode(&root, 1001, "Tom", 20);
insertNode(&root, 1002, "Jerry", 21);
insertNode(&root, 1003, "Alice", 22);
insertNode(&root, 1004, "Bob", 23);
insertNode(&root, 1005, "Cathy", 24);
// 查找学生信息
Student *p = searchNode(root, 1003);
if (p != NULL) {
printf("ID: %d\n", p->id);
printf("Name: %s\n", p->name);
printf("Age: %d\n", p->age);
} else {
printf("Student not found!\n");
}
return 0;
}
```
希望这个例子能够帮助你理解如何用 C 语言实现二叉排序树的创建和查找。如果还有问题,请随时提出。
阅读全文