二叉树的建立与遍历(c语言实现)

二叉树是常见的数据结构之一，它有很多应用，比如文件系统、编译器、人工智能等领域。在C语言中，我们可以通过链表的方式来实现二叉树，下面简单介绍二叉树的建立和遍历。

1、二叉树的建立

二叉树的建立可以通过递归的方式来实现。首先，我们定义二叉树的结构体：

typedef struct BinaryTree
{
    int data;  // 数据
    struct BinaryTree *lchild; // 左孩子指针
    struct BinaryTree *rchild; // 右孩子指针
}BinaryTree;

其中，data表示节点存储的数据，lchild表示左孩子指针，rchild表示右孩子指针。然后，我们可以通过递归的方式来建立二叉树：

BinaryTree *CreateBinaryTree()
{
    int data;
    scanf("%d", &data);
    if(data == -1)  // -1表示空节点
    {
        return NULL;
    }
    BinaryTree *root = (BinaryTree*)malloc(sizeof(BinaryTree));
    root->data = data;
    root->lchild = CreateBinaryTree(); // 递归建立左子树
    root->rchild = CreateBinaryTree(); // 递归建立右子树
    return root;
}

在建立二叉树的过程中，如果输入的数据为-1，表示这个节点为空，直接返回NULL；否则，用malloc动态分配一个节点，存储数据并分别递归地建立左右子树，最终返回根节点。建立完二叉树后，我们就可以进行遍历操作了。

2、二叉树的遍历

二叉树的遍历分为三种：前序遍历、中序遍历和后序遍历。它们分别对应着节点的访问顺序：先访问根节点，然后访问左子树、右子树；先访问左子树，然后访问根节点、右子树；先访问左右子树，然后访问根节点。

在C语言中，我们可以通过递归的方式来实现二叉树的遍历。以前序遍历为例：

void PreorderTraversal(BinaryTree *root)
{
    if(root == NULL)
    {
        return;
    }
    printf("%d ", root->data);
    PreorderTraversal(root->lchild);
    PreorderTraversal(root->rchild);
}

在前序遍历中，首先访问根节点并打印出它的数值，然后递归访问左子树和右子树。中序遍历和后序遍历的实现和前序遍历类似，这里不再赘述。

以上就是二叉树的建立和遍历的C语言实现方法，通过动态分配内存和递归的方式，可以高效地实现二叉树的操作。