C语言数据结构之二叉链表创建二叉树

介绍

二叉链表是一种常用的二叉树存储结构，它利用链表的形式来存储二叉树。其中每个节点包含指向左子树和右子树的两个指针，有助于我们快速地进行二叉树的遍历或操作。接下来，我们将介绍如何使用C语言通过二叉链表方式来创建二叉树。

算法步骤

创建二叉链表的过程通常分为三个步骤：

1. 初始化根节点；
2. 创建左子树；
3. 创建右子树。

代码实现

下面是使用C语言创建二叉链表的示例代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct _Node {
    int data;
    struct _Node *leftChild;
    struct _Node *rightChild;
} Node;

// 创建二叉树
Node *createBinaryTree(Node *root) {
    int value;
    scanf("%d", &value);
    if(value == -1) {
        root = NULL;
    }
    else {
        root = (Node *) malloc(sizeof(Node));
        root->data = value;
        root->leftChild = createBinaryTree(root->leftChild);
        root->rightChild = createBinaryTree(root->rightChild);
    }
    return root;
}

// 中序遍历二叉树
void inOrderTraversal(Node *root) {
    if(root == NULL) {
        return;
    }
    inOrderTraversal(root->leftChild);
    printf("%d ", root->data);
    inOrderTraversal(root->rightChild);
}

int main() {
    Node *root = NULL;
    printf("请输入二叉树的节点，每个节点用空格隔开，-1表示空节点：\n");
    root = createBinaryTree(root);
    printf("中序遍历二叉树结果为：\n");
    inOrderTraversal(root);
    return 0;
}

在上面的代码中，我们首先定义了一个节点结构体，其中包含data、leftChild和rightChild三个成员。然后我们通过createBinaryTree函数来创建二叉树，并通过递归方式，在左右子树进行二叉树的创建。最后，我们通过inOrderTraversal函数来进行中序遍历二叉树，输出节点数据。

示例说明

示例一：

请输入二叉树的节点，每个节点用空格隔开，-1表示空节点：
1 2 3 -1 -1 4 -1 -1 5 6 -1 -1 7 -1 -1
中序遍历二叉树结果为：
2 1 4 3 6 5 7

在上述示例中，我们输入了一个二叉树的节点集合，通过递归方式创建出二叉树，并对其进行了中序遍历。

示例二：

请输入二叉树的节点，每个节点用空格隔开，-1表示空节点：
1 -1 -1
中序遍历二叉树结果为：
1

在上述示例中，我们仅输入了一个节点，也就构成了一棵只有一个根节点的二叉树。通过中序遍历，我们可以输出该节点的数据。

结语

本文介绍了如何利用C语言通过二叉链表方式创建二叉树。通过上述示例，我们更清晰地了解了二叉链表的存储方式以及二叉树的遍历方式。二叉树是许多数据结构和算法的基础，在日常编程中也很常见。所以，了解和掌握二叉树的相关知识是很有必要的。