二叉查找树c语言实现
时间: 2023-11-25 15:06:27 浏览: 38
二叉查找树(Binary Search Tree,简称BST)是一种基于二分查找思想的数据结构,它的每个节点最多有两个子节点,且左子节点的值小于等于父节点的值,右子节点的值大于等于父节点的值。以下是一个简单的二叉查找树的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
void insert(TreeNode** root, int val) {
if (*root == NULL) {
*root = createNode(val);
return;
}
if (val < (*root)->val) {
insert(&((*root)->left), val);
} else {
insert(&((*root)->right), val);
}
}
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
int main() {
TreeNode* root = NULL;
insert(&root, 5);
insert(&root, 3);
insert(&root, 7);
insert(&root, 1);
insert(&root, 9);
inorderTraversal(root); // 输出:1 3 5 7 9
return 0;
}
```
以上代码实现了二叉查找树的插入和中序遍历操作。在插入时,如果当前节点为空,则创建一个新节点;否则,根据大小关系递归地插入到左子树或右子树中。在中序遍历时,先遍历左子树,再输出当前节点的值,最后遍历右子树。