用C语言,用先序遍历创建一个二叉树,用0表示空指针
时间: 2024-12-18 20:30:48 浏览: 4
根据带空指针的先序遍历结果建立二叉树
在C语言中,使用先序遍历创建一个二叉树可以通过递归的方法实现。先序遍历的顺序是:访问根节点 -> 遍历左子树 -> 遍历右子树。
下面是一个简单的示例代码,展示如何使用先序遍历来创建二叉树,并用0表示空指针:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建新节点的函数
TreeNode* createNode(int value) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
if (!newNode) {
printf("内存分配失败\n");
exit(1);
}
newNode->val = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 先序遍历创建二叉树的函数
TreeNode* createBinaryTree() {
int value;
scanf("%d", &value);
if (value == 0) { // 用0表示空指针
return NULL;
}
TreeNode* root = createNode(value);
root->left = createBinaryTree(); // 创建左子树
root->right = createBinaryTree(); // 创建右子树
return root;
}
// 先序遍历打印二叉树的函数
void preOrderTraversal(TreeNode* root) {
if (root == NULL) {
printf("0 "); // 用0表示空指针
return;
}
printf("%d ", root->val);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
int main() {
printf("请输入先序遍历的节点值(用0表示空指针):\n");
TreeNode* root = createBinaryTree();
printf("创建的二叉树先序遍历结果为:\n");
preOrderTraversal(root);
printf("\n");
return 0;
}
```
### 代码说明:
1. **TreeNode结构体**:定义了二叉树节点的结构,包括节点的值、左子节点和右子节点。
2. **createNode函数**:用于创建一个新的二叉树节点。
3. **createBinaryTree函数**:通过先序遍历的方式创建二叉树。如果输入值为0,则返回NULL表示空指针。
4. **preOrderTraversal函数**:用于先序遍历并打印二叉树的节点值,遇到空指针时打印0。
5. **main函数**:读取用户输入的先序遍历序列,创建二叉树并打印其先序遍历结果。
运行程序后,用户需要按照先序遍历的顺序输入节点值,用0表示空指针。例如,输入`1 2 0 0 3 0 0`将创建一个如下结构的二叉树:
```
1
/ \
2 3
```
阅读全文