c语言,实现二叉排序树结点创建和数据插入函数。并完成中序和先序遍历函数,通过输出结果验证二叉排序树是否正确创建。
时间: 2024-12-16 07:24:58 浏览: 6
在C语言中,我们可以创建一个结构体表示二叉树的节点,包含一个值、左子节点和右子节点。首先,我们需要创建二叉树节点的结构体:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
// 创建新节点
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode != NULL) {
newNode->data = value;
newNode->left = newNode->right = NULL;
}
return newNode;
}
```
接下来,我们实现数据插入函数,保证按照二叉搜索树的规则插入:
```c
// 插入节点到二叉搜索树
Node* insertNode(Node* root, int value) {
if (root == NULL) {
return createNode(value);
} else if (value < root->data) {
root->left = insertNode(root->left, value);
} else {
root->right = insertNode(root->right, value);
}
return root;
}
// 中序遍历(根-左-右)
void inorderTraversal(Node* root, void (*print)(int)) {
if (root != NULL) {
inorderTraversal(root->left, print);
print(root->data);
inorderTraversal(root->right, print);
}
}
// 先序遍历(根-左-右)
void preorderTraversal(Node* root, void (*print)(int)) {
if (root != NULL) {
print(root->data);
inorderTraversal(root->left, print);
inorderTraversal(root->right, print);
}
}
```
为了验证二叉排序树是否正确创建,你可以先输入一些值,然后分别调用中序遍历和先序遍历,并输出结果。如果得到的结果是有序的,那么就说明二叉树创建成功。
例如,创建一个树并插入几个元素后:
```c
int main() {
Node* root = NULL;
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
// 输出中序遍历结果
printf("Inorder traversal: ");
inorderTraversal(root, printf);
printf("\n");
// 输出先序遍历结果
printf("Preorder traversal: ");
preorderTraversal(root, printf);
printf("\n");
return 0;
}
```
运行上述代码,你会看到二叉排序树的正确顺序。注意,这里省略了中序和先序遍历的具体打印函数`print()`,实际应用中需要提供这个函数以便于输出数字。
阅读全文