4 / \ 2 7 / \ / \ 1 3 6 9用c语言实现这棵树
时间: 2024-09-24 07:04:35 浏览: 17
这是一个典型的二叉搜索树的结构,我们可以使用C语言的结构体来表示节点,并利用递归的方式来实现节点的添加和遍历。下面是一个简单的C语言实现,包括节点结构体的定义、插入节点和前序遍历的功能:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉搜索树节点结构体
struct TreeNode {
int val; // 节点值
struct TreeNode* left; // 左子节点指针
struct TreeNode* right; // 右子节点指针
};
// 插入节点到二叉搜索树
struct TreeNode* insertNode(struct TreeNode* node, int val) {
if (node == NULL) { // 如果节点为空,创建新的节点
return (struct TreeNode*)malloc(sizeof(struct TreeNode));
}
if (val < node->val) { // 如果值小于当前节点,向左子树递归
node->left = insertNode(node->left, val);
} else { // 否则,向右子树递归
node->right = insertNode(node->right, val);
}
return node;
}
// 前序遍历(根-左-右)
void preOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
printf("%d ", root->val); // 输出节点值
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
int main() {
// 初始化二叉搜索树
struct TreeNode* root = NULL;
root = insertNode(root, 4); // 根节点插入4
insertNode(root, 2); // 插入2
insertNode(root->left, 1); // 为2插入1
insertNode(root->left, 3); // 为2插入3
insertNode(root, 7); // 插入7
insertNode(root->right, 6); // 为7插入6
insertNode(root->right, 9); // 为7插入9
// 打印前序遍历的结果
printf("Preorder traversal of the tree: ");
preOrderTraversal(root);
printf("\n");
return 0;
}
```
当你运行这段代码,它会输出二叉搜索树的前序遍历结果:“4 2 1 3 7 6 9”。这是根据给定的节点值结构创建的树。如果你想查看其他类型的遍历(如中序或后序遍历),只需修改`preOrderTraversal`函数即可。