c语言二叉树的创建与遍历

二叉树是一种重要的数据结构，使用C语言可以很方便地实现二叉树的创建和遍历。

### 二叉树的结构定义

在C语言中，我们可以使用结构体来定义二叉树的节点，每个节点包括左右子树指针和节点值。

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

### 二叉树的创建

二叉树的创建有两种方式，分别是递归创建和非递归创建。

#### 递归创建

递归创建二叉树是比较简单的，只需要按照先序遍历的方式输入节点的值即可。当输入的值为-1时，表示该节点为NULL。

struct TreeNode* create() {
    int val;
    scanf("%d", &val);
    if (val == -1) {
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = val;
    root->left = create();
    root->right = create();
    return root;
}

#### 非递归创建

非递归创建二叉树需要使用栈来保存节点信息，具体步骤如下：

1. 创建一个栈，将根节点入栈。
2. 循环遍历栈，每次取出栈顶元素作为当前节点。
3. 输入当前节点的左子树和右子树的值，如果值不为-1，则创建新节点并将新节点入栈。
4. 将新节点挂到当前节点的左子树或右子树上。
5. 重复步骤2-4，直到栈为空。

struct TreeNode* create() {
    int val;
    scanf("%d", &val);
    if (val == -1) {
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = val;
    root->left = NULL;
    root->right = NULL;
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * MAX_SIZE);
    int top = -1;
    stack[++top] = root;
    while (top >= 0) {
        struct TreeNode* cur = stack[top--];
        scanf("%d", &val);
        if (val != -1) {
            struct TreeNode* child = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            child->val = val;
            child->left = NULL;
            child->right = NULL;
            cur->left = child;
            stack[++top] = child;
        }
        scanf("%d", &val);
        if (val != -1) {
            struct TreeNode* child = (struct TreeNode*)malloc(sizeof(struct TreeNode));
            child->val = val;
            child->left = NULL;
            child->right = NULL;
            cur->right = child;
            stack[++top] = child;
        }
    }
    free(stack);
    return root;
}

### 二叉树的遍历

二叉树的遍历有三种方式，分别是先序遍历、中序遍历和后序遍历。

#### 先序遍历

先序遍历的顺序是：根节点 -> 左子树 -> 右子树。

void preorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->val);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

#### 中序遍历

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

#### 后序遍历

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

void postorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->val);
}

### 总结

以上就是C语言实现二叉树的创建和遍历的方法。在实际应用中，我们可以根据需要选择递归或非递归的方式来创建二叉树，并根据不同的遍历顺序来访问二叉树中的节点。