C语言构建折半查找树的代码
时间: 2023-05-27 11:05:08 浏览: 55
下面是C语言构建折半查找树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int value;
struct node *left;
struct node *right;
} Node;
Node *createNode(int value);
void insertNode(Node **root, int value);
void printTree(Node *root);
int main() {
Node *root = NULL;
insertNode(&root, 10);
insertNode(&root, 5);
insertNode(&root, 15);
insertNode(&root, 3);
insertNode(&root, 7);
insertNode(&root, 12);
insertNode(&root, 17);
printTree(root);
return 0;
}
Node *createNode(int value) {
Node *node = malloc(sizeof(Node));
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
void insertNode(Node **root, int value) {
if (*root == NULL) {
*root = createNode(value);
} else if (value < (*root)->value) {
insertNode(&(*root)->left, value);
} else {
insertNode(&(*root)->right, value);
}
}
void printTree(Node *root) {
if (root != NULL) {
printTree(root->left);
printf("%d ", root->value);
printTree(root->right);
}
}
```
这段代码定义了一个结构体`Node`,表示树的节点。每个节点包含一个整数`value`和两个指向左右子节点的指针`left`和`right`。然后定义了三个函数:
- `createNode`:创建一个新节点,并初始化其值和指针为NULL。
- `insertNode`:插入一个新值到树中。如果树为空,则创建一个新节点。否则,如果新值小于当前节点的值,则继续在左子树中插入;否则,在右子树中插入。
- `printTree`:按中序遍历的顺序打印整个树。
在`main`函数中,我们构建了一个折半查找树,并将其打印出来。
注意,这里使用了双重指针来修改根节点的指针。这是因为在函数内部需要修改根节点指针的值,而如果直接传递指针,则只能修改指针指向的值,而不能修改指针本身的值。因此,我们需要传递指向指针的指针,以便在函数内部修改指针本身的值。